자료구조12 자료구조(12) 이진 탐색 트리 이진 트리의 구조를 보면, 트리는 탐색에 효율적이라는 사실을 알 수 있다. 이진 트리에 저장된 데이터의 수가 10억 개 수준에 이른다해도, 트리의 높이는 30을 넘지 않기 때문이다. 그렇다면 이것이 탐색에 있어서 어떤 의미를 지니겠는가? 예를 들어서 '연결 리스트'에 10억 개의 데이터가 저장되어 있다고 가정해보자. 그리고 찾는 데이터가 이 리스트의 정중앙에 위치한다는 정보를 얻었다고 가정하자. 하지만 이러한 정보를 가지고 있음에도 불구하고 데이터에 이르기 위해서는 약 5억 개의 노드를 지나야 한다. 반면 이진 트리의 경우에는 위치를 알고 있다면, 다시 말해 데이터에 이르는 길을 알고 있다면 루트노드에서 단말 노드에 이르기까지 총 30개의 노드를 지나는 과정에서 원하는 데이터를 찾을 수 .. 2022. 3. 17. 자료구조(11) 보간 탐색 트리 탐색은 데이터를 찾는 방법이다. 탐색 1은(보간 탐색과 이진 탐색 트리) 트리의 뒷이야기에 해당합니다. 굳이 따지지면 탐색은 알고리즘보다 자료구조에 더 가까운 주제이다. 이유는 다음과 같다 "효율적인 탐색을 위해서 "어떻게 찾을까"만을 고민해서는 안된다. 그보다는 "효율적인 탐색을 위한 저장방법이 무엇일까"를 우선 고민해야 한다. 그리고 효율적인 탐색이 가능한 대표적인 저장방법은 '트리'이다. 때문에 탐색에 관한 이야기의 대부분은 트리의 연장선상에 놓여있다. 보간 탐색 (간단하게 설명) 이진 탐색처럼 값에 상관없이 그냥 중앙에서 탐색을 시작하지만, 보간 탐색은 그 값이 상대적으로 앞에 위치한다고 판단을 하면 앞쪽에서 탐색을 시작한다. 단번에 찾지 못하더라도 탐색의 위치가, 찾는 데이터와 가깝기 때문에 탐.. 2022. 3. 17. 자료구조(10) 정렬의 7가지 방법 알고리즘을 코드 레벨에서 분석만 한다면 지루할 수 있다. 이보다는 각각의 알고리즘이 갖는 특징에 관심을 두고 공부하는 것이 기억에도 오래 남고 더 의미가 있을것이다. 1-1 버블 정렬 : 이해와 구현 이해하기도 구현하기도 쉽다. 물론 이해와 구현이 쉬운 만큼 성능에는 아쉬움이 있다. 버블 정렬을 구성는 두 개의 for문의 반복조건이 핵심이다. 따라서 바깥쪽 for문의 반복조건과 안쪽 for문의 반복 조건에 대해서 대략적인 이해가 아니라 정확한 이해가 필요하다 1-2 버블 정렬 : 성능 평가 정렬 알고리즘의 성능은 다음 두 가지 근거로 판단하는 것이 일반적이다. "비교연산"과 데이터의 이동을 위한 "대입연산"이 정렬과정의 핵심연산이기 때문이다. 비교의 횟수 : 두 데이터간의 비교연산의 횟수 이동의 횟수 :.. 2022. 3. 16. 자료구조(9) 우선순위 큐와 힙 우선순위 큐는 그 이름이 의미하듯 큐와 관련이 있다. 하지만 공부하다보면 그 관계가 깊지 않다고 느낄지도 모르겠다. 제목만 봐서는 앞서 구현한 "큐"를 확장하는 수준에서 마무리가 될 것 같지만 "큐"의 구현과 "우선순위 큐"의 구현에는 많은 차이가 있다. 큐의 핵심 연산 두가지 enqueue : 큐에 데이터를 삽입하는 행위 dequeue : 큐에서 데이터를 꺼내는 행위 우선순위 큐의 핵심 연산 두가지 enqueue : 우선순위 큐에 데이터를 삽입하는 행위 dequeue : 우선순위 큐에서 데이터를 꺼내는 행위 반면 연산의 결과에는 차이가 있다. 큐의 연산 결과로, 먼저 들어간 데이터가 먼저 나오지만, 우선순위 큐의 연산결과는 다음과 같다. "들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다" .. 2022. 3. 16. 자료구조(8) 트리 "트리"는 고급 자료구조로 구분이 된다. 그만큼 학습에 있어서 집중을 요한다. 특히 비선형 자료구조이기때문에 많이 다르게 느껴질 수도 있다!" 트리는 계층적 관계를 표현하는 자료구조이다! 자료구조! 하면 보통은 무엇인가를 저장하고 꺼내는 것이 전부인 것으로 이해하는 경우가 많다. 앞서 보인 선형 자료구조들은 이에 초점이 맞춰져 있었으니 무리도 아니다. 하지만 자료구조는 근본적으로 무엇인가를 "표현" 하는 도구이다. 트리는 데이터의 저과 삭제가 아닌 "표현"에 초점이 맞춰져 있다. 때문에 트리의 ADT를 다음과 같이 바라보면 안된다. "데이터의 저장, 검색 및 삭제가 용이하게 정의되어 있나요?" 대신 다음과 같이 바라봐야 한다. "트리의 구조로 이뤄진 무엇인가를 표현하기에 적절히 정의되어 있나요?" 노드(.. 2022. 3. 16. 이전 1 2 3 다음
