이누의 개발성장기

특정 리스트를 정렬하는 방법에는 여러 가지가 있다. 그중에서도 대표적으로 분할 정복을 활용하여 리스트를 정렬하는 것이 합병 정렬, 퀵 정렬이다. 그 중 퀵정렬에 대해 알아보자 퀵 정렬 합병 정렬의 combine단계에서는 크기를 비교해가며 새로운 리스트를 생성했다. 즉, 합병 정렬은 combine단계에서 많은 과정을 수행한다. 하지만 퀵 정렬은 이와 다르게 divide에서 많은 과정을 수행한다. 퀵 정렬의 과정 퀵 정렬은 주로 기준점으로 삼을 임의의 성분을 필요로 한다. 주로 대상 리스트의 제일 마지막 성분을 사용한다. 이를 pivot이라고 부른다. 이 pivot을 기준으로 더 작은 성분은 모두 왼쪽으로, 더 큰 성분은 모두 오른쪽으로 이동한다. (divide) 그리고 왼쪽의 리스트와 오른쪽의 리스트를 각..

분할정복 (Divide and Conquer) 이는 재귀함수에 대한 명확한 이해가 필요한 파트이다. 재귀함수가 부족하다고 생각하면 좀 더 공부를 해놓고 학습을 하는 것이 좋겠다. 분할정복은 이름 그대로 문제를 분할하여 해결하는 것이다. 이는 총 3단계로 구성된다. 1. Divide : 문제를 나눈다. 2. Conquer : 나눠진 문제를 각각 해결한다. 3. Combine : 각각 해결한 두 문제의 답을 결합한다. 여기서 생각해야 될 것은 분명 우리는 어떤 문제를 해결하기 위해 분할정복을 시작했다. 그런데 여기서 2번단계를 보면 '나눠진 문제를 각각 해결한다' 라고 한다. 이 말은 결국 무엇이겠는가? 이 2번 단계에서 나눠진 문제에도 각각 분할정복을 적용할 수 있다는 뜻이다. 그리고 당연하게도 그렇게 2..

그래프에서 어떤 노드에서 어떤 노드로 가는 경로 중 가장 짧은 경로를 찾는 알고리즘은 여러 조건에 따라 방법이 다양하다. 그 중 BFS를 이용하는 방법과 Dijkstra에 대해 알아보자. BFS를 이용한 최단 경로 알고리즘 BFS에서 각 노드에 멤버변수로 predecessor를 추가한다. 해당 멤버변수에는 해당 노드가 어떤 노드로부터 왔는지 기록된다. 즉, Root노드를 제외한 모든 노드들은 BFS를 할 때 특정 노드에서부터 탐색되어져 나온 것이므로, 이를 기록하는 것이다. 이 결과로 특정 노드에서 predecessor를 따라 거꾸로 올라감으로서 특정 노드로 가는 최단의 경로를 알 수 있다. 이를 특별히 backtracking이라고 부르기도 한다. 단, 이는 주로 root노드를 출발점으로 보았을 때 사용..

그래프란 연결 관계를 가지는 자료구조이다. (연결구조의 예 : 지하철역들 사이의 연결여부, 거리수치) 링크드 리스트와 같이 노드를 성분으로 가진다. 그래프 기본 노드들 끼리 직접 연결되어 있을 경우 이 연결관계선을 '엣지'라고 한다. 예를 들어 A와 B사이에 연결관계가 존재하면 이는 'A와 B사이의 엣지'이며, (A,B) 혹은 (B,A)로 표기한다. 직접 연결된 두 노드는 '인접'했다고 한다. 한 노드에 연결된 노드의 개수를 '차수'라고 한다. 어떤 노드에서 어떤 노드까지 가는데에 필요한 엣지들을 '경로'라고 한다. 경로는 충분히 여러개일수 있는데, 그 중 제일 짧은 경로를 '최단 경로'라고 한다. (cf. 경로는 아예 존재하지 않을 수도 있다.) 방향 그래프 앞서 설명한 그래프에서 '엣지'는 방향이 존..

이진 탐색 트리 왼쪽 트리에는 자신보다 작은 크기의 데이터를 가지는 노드들만, 오른쪽 트리에는 자신보다 큰 크기의 데이터를 가지는 노드들만 저장하는 이진트리이다. 따라서 데이터를 찾을 때 데이터가 현재 노드의 데이터보다 작다면 왼쪽으로, 크다면 오른쪽으로 향하면 된다. 완전 이진트리는 아닐 수도 있기 때문에 배열이나 리스트를 활용할 수는 없다. 따라서 노드 정보를 가질 수 있는 node 클래스를 만들어서 사용한다. 이 클래스는 데이터정보,부모노드정보,좌측자식노드정보,우측좌식노드정보를 가져야 한다. 그리고 좀 더 쉬운 관리를 위해 root노드 정보를 가지고 있는 tree클래스도 만들어준다. 이전에 배운 in-order순회대로 이진 탐색트리를 출력하면 데이터의 크기 순서대로 데이터가 출력될 것임을 짐작할 수..

힙 힙은 트리의 일종이다. 단, 힙은 완전 이진트리여야만 한다.(형태 속성, 모든 노드가 2개의 자식을 갖고, 마지막 레벨에서만 왼쪽에서 오른쪽으로 노드가 순차적으로 채워져 있음) 따라서 노드의 개수가 n일 때힙의 높이는lg(n)이고, 리스트로 트리를 표현할 수 있다. 그리고 모든 노드의 데이터는 자식 노드의 데이터보다 크거나 같아야 한다. (힙 속성) 힙정렬 이러한 힙을 사용해서 데이터를 정렬할 수도 있는데, 이를 '힙정렬' 이라고 부른다. 힙은 일종의 완전 이진트리이므로, 리스트로 표현이 가능하다.(트리파트 참고) 이 말은 즉, 리스트를 힙으로 표현할 수도 있다는 것이다. 다만 힙은 부모노드의 데이터가 자식 노드의 데이터보다 커야 하므로, 이 조건을 만족시켜야 한다. 그렇지 않은 리스트를 힙 조건에 ..

트리 트리란 상하 관계가 존재하는 자료구조이다. 링크드 리스트와 비슷하게 트리도 노드들을 가진다. 단, 각 노드는 데이터 정보뿐만 아니라, 자식에 대한 레퍼런스를 가진다. 이를 통해 계층적 구조를 구현할 수 있게 되어 다양한 컴퓨터과학의 문제를 해결할 수 있다. 물론, 트리도 자료구조이기 때문에 여러 추상 자료형을 구현할 수 있다. 트리구조 용어 root 노드 : 가장 상위의, 즉 뿌리가 되는 노드 부모노드 : 어떤 노드의 직속 상위 노드 자식 노드 : 어떤 노드의 직속 하위 노드 형제 노드 : 같은 부모 노드를 가지는 노드 leaf노드 : 어떤 자식도 갖지 않는, 즉 잎이 되는 노드 깊이(레벨) : root노드로부터 떨어진 거리(레벨은 깊이+1) 높이 : 가장 깊이 있는 노드(leaf노드)의 깊이 부분..

기능 : '무엇'을 하는지 (자료구조마다 하는 일은 같다.) 구현 : 그 '무엇'을 어떻게 (자료구조마다 다르다.) 추상 자료형이란 자료구조를 추상화하여 표현한 것으로서, 구현보다는 기능에만 초점을 맞춘 것이다. ex) 리스트는 접근, 탐색, 삽입, 삭제의 기능이 있는 추상 자료형이다. 이를 '구현'하는 것에는 앞서 배운 동적 배열이나 링크드 리스트가 있다. 자료구조를 통해 복잡하게 생각하는 것보다는 기능에만 초점을 맞춘 추상화 자료를 떠올린다면, 보다 코드의 흐름을 이해하기 쉬워진다는 것이 추상자료형의 핵심가치이다. (물론 코드의 성능을 분석, 최적화할 때는 자료구조를 떠올려야 한다.) 구현할 때 동적 배열을 사용할 것인가? 링크드 리스트를 사용할 것인가? 동적 배열은 접근이 O(1)이지만 링크드 리스..

key-value 데이터를 어떻게 효율적으로 관리할 수 있을까? Direct Access Table을 활용해 각 주소를 key로 활용하여 각각의 주소에 value값을 저장한다면, O(1)으로 저장하고 O(1)으로 불러올 수도 있다. 하지만 이는 데이터공간의 낭비가 일어날 수 있다. (key를 숫자로 생각하면 1, 3, 20000의 key가 있다고 생각했을때, 19997의 낭비공간이 발생) 그에 따라 제시된 것이 Hash Table이다. 이는 '해시함수'를 활용하여 값을 저장한다. 해시함수 : 특정값을 원하는 범위의 자연수로 변경해주는 함수. 원하는 범위를 정하면, 해시함수를 활용하여 적절한 위치에 key값과 value값을 모두 저장한다. 해시함수의 조건 결정론적이어야 된다. 원하는 범위의 자연수 하나하나..

링크드 리스트 링크드 리스트는 데이터를 순서대로 저장해준다. 계속해서 새로운 요소를 추가할 수 있다. 배열과는 다르게 각 요소는 사실상 독립적인 레퍼런스에 위치해있다. 각 요소를 노드라고 하고, data 속성과 next 속성을 보유한다. next에는 다음 노드에 대한 레퍼런스가 들어있다. 따라서 실제 메모리에 각 노드들이 여기저기에 흩어져있어도 next속성을 통해 이어진 것처럼 활용할 수 있다. 링크드 리스트의 구성 따로 linked list클래스를 만들어서 활용한다. 그렇지만 이 linked list 클래스는 모든 노드를 멤버로 보유하지 않는다. 첫 노드 혹은 마지막 노드만을 보유하고 있다면 그에 연결된 나머지 노드들은 그를 통해 접근이 가능하기 때문이다. 따라서 linked list 클래스는 주로 첫..