이누의 개발성장기

그래프에서 어떤 노드에서 어떤 노드로 가는 경로 중 가장 짧은 경로를 찾는 알고리즘은 여러 조건에 따라 방법이 다양하다. 그 중 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 클래스는 주로 첫..

리스트 in 파이썬 파이썬 리스트는 C 배열을 기반으로 만들어졌다. c 배열 - 선언 시 타입과 크기를 선언하여 배열 크기가 고정되어 있고, - 같은 타입의 데이터만 담기 가능하다. - 배열이 사용할 공간을 미리 할당한다. - 각 메모리 공간에 데이터가 그 자체가 연속적으로 바로 할당되는 형식이다 파이썬 리스트 - 데이터 자체는 연속적인 공간에 할당되어 있지 않지만, - 각 연속적 공간에 각 레퍼런스가 할당되어있어, 그 레퍼런스가 데이터를 가리킨다. - 따라서 그에 따라 리스트 자체로도 다양한 타입의 값을 저장할 수 있다. - (물론 그 크기의 제한도 없다. 레퍼런스가 가리키는 타입에 상관없이 레퍼런스의 크기는 일정하므로, 추가 시 레퍼런스의 크기만큼 추가를 해주면 되기 때문이다. 이에 더해 파이썬 자체..

컴퓨터가 자료를 저장하는 방식은 2가지 스토리지 : 영구적 저장소 저장속도가 느리고 받아오는 것도 느리다. 정확히 언제 사용할지 모르는 데이터 저장한다. 메모리 : 임시 저장소 저장속도가 빠르고 받아오는 것도 빠르다. 지금 당장 사용할 데이터 저장한다. 두개로 나눠 사용하는 이유는 효율적인 작업을 위해서이다. 자료구조 공부시엔, 이 중 메모리에서 데이터를 잘 활용하는 방법을 익힌다. 메모리 메모리는 각 주소가 담긴 일종의 긴 띠라고 생각하면 편하다. 긴 띠가 구역별로 나누어져 각각의 구역에 데이터가 저장되는 것이다. - 우리가 사용할 메모리는 RAM(Random Access Meomory, 임의접근메모리)이기때문에 어떤 주소에 있던 데이터접근에는 일정한 시간이 소요된다. (O(1)) - 바이트란 컴퓨터 ..