Alex-Moon Alex-Moon

그래프는 로봇이 최단 경로를 계산해서 움직일 때나 내비게이션에서 경로를 안내할 때, 지하철역을 어디에 건설해야 가장 효율적인지 계산하는 등 매우 폭넓게 사용됩니다. 게다가 최근에 가장 중요한 이슈인 머신 러닝도 그래프를 활용합니다. 이 장에서는 그래프에 대한 이론적인 내용과 실제로 구현할 때 표현(representation), 모든 정점을 방문하는 방법인 순회(traversal) 등 그래프의 기본 내용을 다루어 보겠습니다. 1.1 그래프 용어 정리 자료구조 - 그래프 정의 그래프(graph)는 연결된 객체들 사이의 관계를 표현할 수 있는 자료구조이다. 지하철 노선도나 전기회로 같이 다양한 객체들이 서로 복잡하게 연결되어 있는 구조를 표현할 수 있는 논리적 edwardmoon.tistory.com self..

1.1 스택 스택(stack)은 접시 쌓기를 떠올리면 됩니다. 데이터가 들어오면 차곡차곡 쌓이고 나갈 때는 맨 위에 있는 데이터부터 나갑니다. 즉, 맨 마지막에 들어온 데이터가 맨 처음 나가게 되지요. 이를 LIFO(Last In First Out)라고 합니다. 스택의 ADT를 정의한 후 어떻게 객체를 표현하고 연산을 구현할지 고민해 보겠습니다. Stack - Object : LIFO 객체 - Operation 1. empty( ) -> Boolean: 스택이 비어 있으면 TRUE, 아니면 FALSE 반환 2. push(data): data를 스택의 맨 위에 삽입 3. pop( ) -> element: 스택의 맨 위에 있는 데이터를 삭제하며 반환 4. peek( ) -> element: 스택의 맨 위에 ..

1. 연결리스트 동적 배열은 탐색 기능이 막강하며 배열 마지막에서 삽입 및 삭제 연산 속도가 빨라 프로그램을 처음 작성할 때 가장 먼저 사용을 고려하는 자료 구조입니다. 하지만 데이터를 배열 중간에 삽입하거나 삭제해야 할 때는 원소들을 옮겨야 하는 부담이 있지요. O(n) 정도면 성능이 훌륭하지 않나 하고 생각할 수도 있습니다. 그래도 중간에 삽입과 삭제가 자주 일어나는 상황에서 좀 더 나은 삽입 및 삭제 연산을 제공하는 자료 구조가 있다면 배열보다 그것을 선택하는 것이 나을 수 있습니다. 연결 리스트(linked list)는 이런 고민에서 만들어진 자료 구조입니다. 연결 리스트는 그 자체만으로는 동적 배열에 비해 쓰임새가 적은 편입니다. 삽입과 삭제가 빈번한 경우에 사용을 고민해 볼 수 있겠지요. 연결..

1. 동적 배열 초기 배열은 같은 데이터 타입을 가진 변수 집합이었습니다. 아직도 많은 언어에서 배열은 같은 타입 변수들을 저장합니다. 하지만 C 언어를 제외한 거의 대부분의 언어가 초기 형태의 배열이 아닌 동적 배열을 지원합니다. 동적 배열은 기존 배열이 가지는 장점은 유지하면서 여러 단점은 보완한 형태로 구현되었습니다. 메모리에 데이터를 저장하는 영역은 세 군데인데, 그중 스택과 힙 영역이 있습니다. 스택은 실제 스택 프레임(파이썬의 스택 프레임과 개념은 같지만 실제 할당되는 공간은 다름)이 쌓이는 메모리 공간이고, 힙은 변수의 생성 시기와 소멸 시기를 프로그래머가 결정할 수 있는 메모리가 동적으로 할당되는 영역입니다. 동적 배열 개념을 이해하려면 스택과 힙 차이를 알아야 합니다. 스택 프레임을 할당..

트리의 구조와 관련 용어 트리는 아래의 사진과 같이 노드(node)와 가지(edge)로 구성된다. 각 노드는 가지를 통해 다른 노드와 연결된다. 루트 : 트리의 가장 위쪽에 있는 노드를 루트라고 한다. 루트는 트리 하나에 1개만 존재한다. 리프 : 가장 아래쪽에 있는 노드를 의미한다. 단말 노드(terminal node), 외부 노드(external node)라고도 한다. 물리적으로 가장 밑에 위치한다는 의미가 아니라 가지가 더 이상 뻗어나갈 수 없는 마지막에 노드가 있다는 뜻이다. 비단말 노드(non-terminal node) : 리프를 제외한 노드. 내부 노드(internal node)라고도 한다. 자식 : 어떤 노드와 가지가 연결되었을 때 아래쪽 노드. 노드는 자식을 몇개라도 가질 수 있다. 부모 ..

검색의 종류로는 배열 검색, 연결 리스트 검색, 이진 검색 트리 알고리즘이 있다. 배열 검색의 종류로는 선형 검색 : 무작위로 늘어놓은 데이터 집합에서 검색을 수행한다. 이진 검색 : 일정한 규칙으로 늘어놓은 데이터 집합에서 빠른 검색을 수행한다. 해시법 : 추가-삭제가 자주 일어나는 데이터 집합에서 빠른 검색을 수행한다. 체인법 : 같은 해시값 데이터를 연결 리스트로 연결하는 방법이다. 오픈 주소법 : 데이터를 위한 해시값이 충돌할 때 재해시하는 방법이다. 해시법 hashing 검색과 더불어 데이터의 추가와 삭제도 효율적이다. 해시법은 '데이터를 저장할 위치 = 인덱스'를 간단한 연산으로 구하는 것을 말한다. 배열의 키들은 해시함수를 거쳐서 해시값(Hash Table)을 만들어 낸다. Hash Tabl..

병합 정렬 merge sort 노이만이 고안한 분할 정복 알고리즘. 퀵 정렬과 반대로 안정 정렬에 속한다. 배열을 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘이다. 과정 i) 리스트의 길이가 0또는 1이면 이미 정렬된 것으로 본다. ii) 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. iii) 각 부분 리스트를 재귀적으로 병합 정렬을 이용해 정렬한다. iv) 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 장점 - 안정적인 정렬 방법 - 레코드를 linked list로 구성하면, 데이터의 이동은 무시할 수 있을 정도로 작아진다. (퀵 정렬을 포함한 다른 정렬 방법보다 효율적이다.) 단점 - 레코드를 배열로 구성하면 임시 ..

복잡도 복잡도(complexity)는 알고리즘의 성능을 나타내는 척도다. 복잡도는 시간 복잡도와 공간 복잡도로 나눌 수 있다. 시간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미하고, 공간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미한다. 동일한 기능을 수행하는 알고리즘이 있다면 일반적으로 복잡도가 낮을수록 좋은 알고리즘이다. 시간 복잡도 : 알고리즘을 위해 필요한 연산의 횟수 공간 복잡도 : 알고리즘을 위해 필요한 메모리의 양 효율적인 알고리즘을 사용한다고 했을 때 보통 시간 복잡도와 공간 복잡도는 일종의 거래 관계(trade-off)가 성립한다. 메모리를 조금 더 많이 사용하는 대신에 연산을 생략하거나 더 많은 정보를 관리하면서..