야곰야곰'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

큐는 간결하게 임시 데이터를 다루며 제약이 있는 배열이라는 점에서 스택과 비슷하다. 다만 데이터를 처리하는 순서가 다르므로 작업 중인 애플리케이션의 요구에 따라 선택한다. 극장에 줄 서 있는 사람들을 큐처럼 생각할 수 있다. 줄 맨 앞에 있는 사람이 그 줄을 떠나 가장 먼저 극장에 들어간다. 큐 역시 큐에 첫 번째로 추가된 항목이 가장 먼저 제거된다. 그래서 컴퓨터 과학자는 큐를 FIFO(first in, first out)이라 한다. 큐는 다음과 같은 제약을 포함한다. 데이터는 큐의 끝에만 삽입할 수 있다. 데이터는 큐의 앞에서만 읽을 수 있다. 데이터는 큐의 앞에서만 삭제할 수 있다. 빈 큐로 시작해서 큐의 동작을 알아보자. 먼저 5를 삽입하자. ( 스택 삽입은 push라고 하지만 큐 삽입은 put,..

스택이 데이터를 저장하는 방법은 배열과 같다. 단순하게 얘기하면 원소들의 리스트다. 다만 스택에는 다음과 같은 제약이 있다. 데이터는 스택의 끝에만 삽입할 수 있다. 데이터는 스택의 끝에서만 읽을 수 있다. 데이터는 스택의 끝에서만 삭제할 수 있다. 접시를 스택이라고 생각해 보면 가장 위에 있는 접시를 제외하고는 다른 접시의 윗면을 볼 수 있다. 비슷하게 가장 위를 제외하고는 접시를 추가할 수도, 제거할 수도 없다(끼워넣기 안돼요). 실제로 대부분의 컴퓨터 과학책에서 스택의 끝을 top, 스택의 시작을 bottom이라고 부른다. 빈 스택부터 시작해서 스택의 동작을 알아보자. 스택에 새 값을 삽입하는 것을 스택에 푸시한다고 한다. 스택에 5를 푸시하자. 특별할 것은 없다. 그저 배열 끝에 데이터를 삽입하는..

대부분의 프로그래밍 언어는 해시 테이블(hash table)이라는 자료 구조를 포함하며, 해시 테이블에는 빠른 읽기라는 놀랍고 엄청난 능력이 있다. 해시 테이블은 다양한 프로그래밍 언어에서 서로 다른 이름으로 불린다. 해시, 맵, 해시 맵, 딕셔너리, 연관 배열 등의 이름을 갖는다. 해시 테이블은 쌍으로 이뤄진 값들의 리스트다. 첫 번째 항목을 키라 부르고, 두 번째 항목을 값이라 부른다. 해시 테이블에서 키와 값은 서로 중요한 관계다. 해시 테이블의 값 룩업은 딱 한 단계만 걸리므로 평균적으로 효율성이 O(1)이다. 해싱 문자를 가져와 숫자로 변환하는 이러한 과정을 해싱이라고 부른다. 또한, 글자를 특정 숫자로 변환하는 데 사용한 코드를 해시 함수라 부른다. 이밖에도 해시 함수는 많다. 또 다른 해시 ..

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

선택 정렬은 다음과 같은 단계를 따른다. 1. 배열의 각 셀을 왼쪽부터 오른쪽 방향으로 확인하면서 어떤 값이 최솟값인지 결정한다. 한 셀씩 이동하면서 현재까지 가장 작은 값을 변수에 저장한다. 변수에 들어 있는 값보다 작은 값이 들어 있는 셀을 만나면 변수가 새 인덱스를 가리키도록 값을 대체한다. 2. 이제 최솟값이 어느 인덱스에 들어 있는지 알았으므로 그 인덱스의 값과 패스스루를 처음 시작했을 때의 값을 교환한다. 패스스루를 시작했을 때 인덱스는 첫 패스스루에서 인덱스 0일 것이고, 두 번째 패스스루에서는 인덱스 1일 것이다. 3. 데이터가 모두 정렬될 때까지 1, 2단계를 반복한다. #include using namespace std; void selectionSort(vector& array) { ..

배열의 중복 값이 있는지 확인하는 함수를 만든다고 해보자. 가장 먼저 떠오리는 방법은 중첩 for문을 이용하는 것이 아닐까 싶다. bool hasDuplicateVal(int* list, unsigned int len) { for (int i=0; i

버블 정렬이란? 매우 기본적인 정렬 알고리즘인 버블 정렬(Bubble sort)은 이해하기 쉽기 때문에 단순 정렬(simple sort)이라 불린다. 다만 빠르다고 알려진 정렬 알고리즘보다는 비효율적이다. 버블 정렬은 다음과 같은 단계를 따른다. 1. 배열 내에서 연속된 두 항목을 가리킨다. 첫 번째 항목과 두 번째 항목을 비교한다. 2. 두 항목의 순서가 뒤바뀌어 있으면 (왼쪽 값이 오른쪽 값보다 크면) 두 항목을 교환(swap)한다. 순서가 올바르다면 아무것도 하지 않는다. 3. 비교 위치(포인터)를 오른쪽으로 한 셀씩 옮긴다. 4. 더 이상 교환하지 않을 때까지 1단계부터 3단계까지 반복한다. 더는 교환을 하지 않는다는 것은 배열이 정될된 상태라는 뜻이며 1 ~ 3 단계를 반복하는 것을 패스스루(p..

서로 간에 시간 복잡도를 쉽게 소통할 목적으로 자료 구조와 알고리즘의 효율성을 간결하고 일관된 언어로 설명하기 위해 수학적 개념을 차용했는데 이 개념을 형식화한 것이 빅 오 표기법이다. 빅 오 표기법은 알고리즘의 효율성을 쉽게 분류하고 이해시킬 수 있는 장점이 있다. 빅 오는 시간 단위가 아닌 알고리즘에 필요한 단계 수만을 고려함으로써 일관성을 유지한다. 1 단계만 필요한 알고리즘은 다음과 같이 표기한다. O (1) 일반적으로 "빅 오 1"이라고 발음한다. "차수 1"이라고도 한다. O (1)은 데이터의 크기에 상관없이 알고리즘에 필요한 단계 수가 일정하다는 의미다. 배열에 N개의 원소가 있을 때 선형 검색은 최대 N단계가 걸리는데 빅 오 표기법으로는 다음과 같다. O (N) 상수 시간과 선형 시간 O(..

정렬된 배열(ordered array)은 배열과 거의 같다. 단지 그 값이 항상 순서대로 있어야 한다는 점이다. 값을 추가할 때마다 배열의 값이 정렬된 상태가 되도록 한다. 하지만 이런 순서를 지키기 위해서는 여러 단계가 필요하다. 항상 실제 삽입 전에 검색을 먼저 수행해서 삽입할 정확한 위치를 알아내야 한다. 이것은 삽입에 있어서 효율을 많이 떨어트리게 된다. 하지만 정렬된 배열의 강력함은 검색 연산에서 드러난다. 배열과 정렬된 배열을 선형 검색으로 검색을 시도하면 정렬된 배열의 장점은 값이 없을 경우 더 빨리 멈출 수 있다는 점 밖에는 없다. 찾으려는 데이터가 발견되지 않고 더 큰 데이터가 나타날 때 정렬된 배열은 바로 멈출 수 있기 때문이다. 대단한 차이가 없어 보인다. 하지만 정렬된 배열에는 알고..