야곰야곰's S/W 공부

최단 경로 문제를 푸는 알고리즘 중에 하나인 데이크스트라의 알고리즘은 에드거 데이크스트라가 만들었다. 데이크스트라 알고리즘 규칙은 다음과 같다. 시작 정점을 현재 정점으로 한다. 현재 정점에 인접한 모든 정점을 확인해서 시작 정점으로부터 알려진 모든 위치까지의 가중치를 계산하고 기록한다. 다음 현재 정점을 결정하려면 시작 정점으로부터 도달할 수 있는 방문하지 않은 가장 저렴한 알려진 정점을 찾는다. 그래프 내 모든 정점을 방문할 때까지 1~3단계를 반복한다. 애틀랜타부터 다른 도시까지의 가장 저렴한 경로를 찾아보자. 시작 정점은 아틀랜타가 된다. 다음으로 인접한 정점을 모두 확인해서 가중치를 기록한다. Atlanta Boston Chicago Denver El Paso $100 ? $160 ? 현재로서는..

가중 그래프는 일반적인 그래프와 비슷하지만 그래프 간선에 추가적인 정보를 포함한다. 위 그래프의 간선에는 간선이 연결하는 도시 간 항공료가 표시되어 있다. 그래프에 가중치를 추가하려면 배열 대신 해시 테이블을 사용해야 한다. 클래스로 간단하게 표현해 보자. #include #include #include #include using namespace std; class CCity { public: CCity(string _name) : name(_name) {} void add_route(CCity* city, int _price) { price.insert(pair(city, _price)); } int get_price(CCity* city) { auto p = price.find(city); retu..

그래프는 데이터가 어떻게 연결되는지 쉽게 이해시키므로 관계에 특화된 자료구조다. 한 사람은 한 노드로, 사람 간 관계는 각 선으로 표현한다. 그래프 용어로 각 노드를 정점이라 부르고, 각 선은 간선이라 한다. 간선으로 연결된 정점들은 서로 인접한다고 말한다. 그래프를 구현하는 방법은 많지만 가장 간단한 방법 중 하나는 해시 테이블을 사용하는 것이다. 해시 테이블의 모든 키 값은 한 단계로 찾을 수 있으므로 그래프를 쓰면 앨리스의 친구를 O(1)에 찾을 수 있다. SNS의 팔로우를 본다면 관계가 상호적이지 않다. 앨리스는 밥을 팔로우할 수 있지만, 밥이 반드시 앨리스를 팔로우하지는 않는다. 화살표의 방향은 관계의 방향을 나타낸다. 위 둘 예제는 서로 비슷하지만 각각 관계의 본질이 다르다. 관계의 방향성을 ..

단순 연결 리스트는 각 노드마다 그 노드와 다른 한 노드를 연결하는 링크를 포함한다. 트리 역시 노드 기반 자료 구조이지만 트리의 각 노드는 여러 노드로의 링크를 포함할 수 있다. 다음은 간단한 트리를 그림으로 표현한 것이다. 예제의 각 노드에는 다른 두 노드로 이어지는 링크가 있다. 실제 링크를 모두 표시하지 않고도 간결하게 트리를 그림으로 표현할 수 있다. 트리에는 세 가지 고유한 용어가 있다. 가장 상위 노드("j")를 root라고 부른다. 루트는 트리의 꼭대기다. "j"를 "m"과 "b"의 부모라고 하고, 반대로 "j"의 자식이라고 한다. 트리에는 레벨이 있다. 위 트리는 세 레벨이다. 트리 기반 자료 구조는 종류가 다양하지만 우선 이진트리는 다음의 규칙을 따른다. 각 노드의 자식은 0개나 1개,..

연결 리스트는 배열과 마찬가지로 항목의 리스트를 표현하는 자료 구조다. 사용자가 어떤 애플리케이션에서 배열을 사용 중이라면 아마도 배열 대신 연결 리스트를 쓰고 있을 가능성이 크다. 연결 리스트는 나란히 이어진 메모리 셀 묶음이 아니다. 서로 인접하지 않음 메모리 셀 묶음으로 이뤄진다. 컴퓨터 메모리 전체에 걸쳐 여러 셀에 퍼져 있을 수 있다. 서로 인접하지 않은 이러한 셀을 노드라 부른다. 각 노드는 노드에 저장된 데이터뿐만 아니라 연결 리스트 내에 다음 노드의 메모리 주소도 저장해야 한다. 위 그림을 보면 연결 리스트에 "a", "b", "c", "d", 4개의 데이터가 있다. 하지만 데이터를 저장하는 데 각 노드마다 메모리 셀 두 개씩, 총 메모리 셀 여덟 개를 사용한다. 연결 리스트를 다루는 코드..

무작위로 정렬된 배열이 있을 때, 정렬은 안 해도 되지만 배열에서 열 번째로 작은 값 혹은 열다섯 번째로 큰 값을 알고 싶다고 하자. 가령 수많은 시험 점수가 있을 때 25번째 백분위수나 중간 점수를 알고 싶을 때 도움이 될 것이다. 전체 배열을 정렬한 후 적절한 셀을 바로 찾아보면 확실히 문제를 해결할 수 있지만 퀵 셀렉트라고 알려진 뛰어난 작은 알고리즘으로 훨씬 더 나은 성능을 낼 수 있다. 퀵 셀렉트도 퀵 정렬처럼 분할에 기반하며, 퀵 정렬과 이진 검색의 하이브리드 정도로 생각할 수 있다. 값이 8개인 배열이 있을 때 이 배열 내에서 두 번째로 작은 값을 찾고 싶다고 하자. 먼저 전체 배열을 분할한다. 분할 후 피벗은 배열의 중간 부분에 있을 것이다. 이제 피벗은 올바른 위치며, 다섯 번째 셀이므로..

퀵 정렬 알고리즘에서 분할은 매우 중요하다. 분할 배열을 분할한다는 것은 배열로부터 임의의 수를 가져와(이 수를 피벗이라고 부름) 피벗보다 작은 모든 수는 피벗의 왼쪽에, 피벗보다 큰 모든 수는 피벗의 오른쪽에 두는 것이다. 아래와 같은 stormpy.tistory.com 퀵 정렬 알고리즘은 아래와 같이 동작한다. 배열을 분할한다. 피벗은 이제 올바른 위치에 있다. 피벗의 왼쪽과 오른쪽에 있는 하위 배열을 각각 또 다른 배열로 보고 1단계와 2단계를 재귀적으로 반복한다. 하위 배열이 원소를 0개 또는 1개 포함하면 기저 조건이므로 아무것도 하지 않는다. #include #include using namespace std; class CSortArray { public: CSortArray() = defa..

배열을 분할한다는 것은 배열로부터 임의의 수를 가져와(이 수를 피벗이라고 부름) 피벗보다 작은 모든 수는 피벗의 왼쪽에, 피벗보다 큰 모든 수는 피벗의 오른쪽에 두는 것이다. 아래와 같은 배열이 있다고 하자. 일관된 설명을 위해 가장 오른쪽에 있는 값을 항상 피벗으로 하고 3을 이용해 분할해 보자. 두 개의 포인터를 사용해 하나는 배열 가장 왼쪽에 있는 값에, 다른 하나는 가장 오른쪽 있는 값에 할당한다. 분할은 다음의 단계를 따라 실제 분할한다. 왼쪽 포인터를 한 셀씩 계속 오른쪽으로 옮기면서 피벗보다 크거나 같은 값에 도달하면 멈춘다. 오른쪽 포인터를 한 셀씩 계속 왼쪽으로 옮기면서 피벗보다 작거나 같은 값에 도달하면 멈춘다. 왼쪽 포인터와 오른쪽 포인터가 가리키고 있는 값을 교환한다. 두 포인터가 ..

재귀는 함수가 자기 자신을 호출할 때를 말하는 공식 명칭이다. 일반적으로 무한 함수 호출은 쓸모가 없고 위험하기까지 하지만 재귀는 활동 가능성이 큰 강력한 도구다. 10에서 0까지 카운트 다운하는 함수를 만들어 보자. #include using namespace std; void countdown(int number) { for (int i = number; i >= 0; i--) cout

T, T*은 T의 포인터의 표현이다. 즉, T*의 변수는 T 객체의 주소를 가질 수 있다. char c = 'a'; char∗ p = &c; // p holds the address of c; & is the address-of operato 포인터에 대한 기본 연산은 역참조, 즉 가리키는 객체를 참조하는 것이다. 이 작업을 간접 참조라고도 한다. 역참조 연산자는 접두사로 '*'을 사용한다. char c = 'a'; char∗ p = &c; // p holds the address of c; & is the address-of operator char c2 = ∗p; // c2 == ’a’; * is the dereference operator p가 가리키는 객체는 c이고, c에 저장된 값은 'a'이므로..

삽입 정렬의 수행 순서는 다음과 같다. 1. 첫 번째 패스스루에서 임시로 인덱스 1(두 번째 셀)의 값을 삭제하고 이 값을 임시 변수에 저장한다. 인덱스 1에 값이 없으므로 공백이 생긴다. 이후 각 패스스루마다 다음 인덱스의 값을 삭제한다. 2. 다음으로 공백 왼쪽에 있는 각 값을 가져와 임시 변수에 있는 값과 비교하는 시프트 단계를 시작한다. 공백 왼쪽에 있는 값이 임시 변수에 있는 값보다 크면 그 값을 오른쪽으로 시프트 한다. 값을 오른쪽으로 시프트 했으므로 자연히 공백이 왼쪽으로 옮겨진다. 임시로 삭제한 값보다 작은 값을 만나거나 배열의 왼쪽 끝에 도달해야 시프트 단계가 끝난다. 3. 이제 임시로 제거한 값을 현재 공백에 삽입한다. 4. 배열이 완전히 정렬될 때까지 1단계부터 3단계를 반복한다. #..

때로는 유형에 대한 새로운 이름이 필요하다. 이유는 다음과 같다. 원래 이름이 너무 길거나 복잡하거나 보기 흉할 때 (프로그래머의 취향) 프로그래밍 기술은 Context에서 동일한 이름을 가진 다른 유형을 요구하기도 한다. 특정 유형은 유지 관리를 단순화하기 위해 한 곳에서만 언급된다. using Pchar = char∗; // pointer to character using PF = int(∗)(double); // pointer to function taking a double and returning an int 유사한 유형은 멤버 별칭과 동일한 이름을 정의할 수 있다. template class vector { using value_type = T; // every container has a v..

우리는 이름이 없는 객체를 할당하고 사용할 수 있다. (eg. new를 사용하여 생성) 이상하게 보이는 표현식에 할당하는 것도 가능하다. . 이것은 대상에 대한 가장 단순하고 기본적인 개념이다. 즉, 객체는 연속적인 저장 영역이다. lvalue는 객체를 참조하는 표현식이다. "lvalue"라는 단어는 원래 '할당의 왼쪽에 있을 수 있는 것'을 의미하기 위해 만들어졌다. 그러나 모든 lvalue가 할당의 왼쪽에 사용될 수 있는 것은 아니다. lvalue 유형과 선언은 상수를 참조할 수 있다. const로 선언되지 않은 lvalue는 종종 수정 가능한 lvalue라고 한다. 객체에 대한 단순하고 낮은 수준의 이 개념은 클래스 객체 및 다형성 유형의 객체 개념과 혼동되어서는 안 된다. Lvalues and R..

적절한 생성자가 있다면 auto를 사용할 수 있다. 그러나 때로는 초기화된 변수를 정의하지 않고 유형을 추론하고 싶을 때가 있다. 그런 다음 유형 지정자를 사용할 수 있다. decltype(expr)은 expr의 선언된 유형이다. 이것은 genetic programming에서 주로 유용하다. 내부적으로 다른 요소 유형을 가진 두 개의 행렬을 추가하는 함수를 작성할 때 더하기의 결과의 유형은 무엇이어야 할까? 행렬이지만 요소의 유형은 무엇일까? 명백한 대답은 합계의 요소 유형이 요소의 합계 유형과 같다는 것이다. 따라서 다음과 같이 선언할 수 있다. template auto operator+(const Matrix& a, const Matrix& b) −> Matrix; 반환 유형을 인수 측면에서 표현할 ..

생성자가 있는 변수를 선언할 때는 명시적으로 지정하지 않아도 된다. 대신 변수가 초기화 유형을 가지게 할 수 있다. int a1 = 123; char a2 = 123; auto a3 = 123; // a3의 유형은 int가 된다. 정수 literal 타입인 123은 int 다. 그래서 a3은 int가 된다. auto는 초기화되는 유형의 자리 표시자가 된다. 물론 int와 같은 간단한 표현식에서 auto를 사용하는 것은 이점이 없다. 유형이 복잡하고 사용하기 어려울수록 auto는 유용해진다. template void f1(vector& arg) { for (vector::iterator p = arg.begin(); p!=arg.end(); ++p) ∗p = 7; for (auto p = arg.begin..

bool Boolean : true or false 의 두 가지 값 char Character : 글자 혹은 글을 사용 char : default type signed char : like char. +/- 값을 가질 수 있다. unsigned char : like char. - 값을 가질 수 없다. wchar_t : unicode를 위한 larger character set. char16_t : 16bit character set (UTF-16) char32_t : 32bit character set (UTF-32) Literals int Integer : like char int, signed int, unsigned int, short int, long int, long long int ... in..

VS 프로젝트를 진행할 때, 여러 Lib 프로젝트를 만든 후 가져다 사용하는 경우가 많다. 그럴 경우 컴파일 실행 순서가 뒤죽박죽이면 여러 번 컴파일해야 한다. 왜냐면 가져 다 사용해야 할 Lib이 컴파일이 끝난 상태가 되었을 때 그것을 이용하는 프로젝트가 컴파일이 완료될 수 있기 때문이다. 이런 작업을 위해 컴파일을 순서를 정해주기 위해서는 프로젝트의 종속성을 설정해 줘야 한다. Visual Studio에서는 종속성을 설정하는 기능을 지원한다. 솔루션 이름에서 우클릭(1)하여 속성(2)을 클릭하면 솔루션의 속성을 볼 수 있다. 항목 중에 Project Dependencies를 선택(3)하고 종속성을 설정할 프로젝트를 선택(4) 한다. 해당 프로젝트를 선택하면 이 프로젝트를 제외한 프로젝트들이 나타난다...

namespace 사용 시, cpp 파일의 활용을 편하기 하기 위해서 namespace를 정확하게 작성하지 않고 using namespace를 사용 시 link 에러가 발생할 수 있다. //header file namespace file_c { void open_file(); } using namespace file_c void open_file() { // ... } 이라고 했을 때, open_file()을 여러 단계를 거치다 보면 2019 LNK ERROR가 발생하는데, 헤드 파일 라이브러리 링크 등 보통의 경우를 모두 체크하더라도 에러가 발생한다. 그렇기 때문에 헤드 파일과 cpp파일 모두에 제대로 된 네임스페이스 형식으로 구현하도록 하자. namespace file_c { void open_fil..