자료구조11 자료구조(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. 자료구조(8) 트리 "트리"는 고급 자료구조로 구분이 된다. 그만큼 학습에 있어서 집중을 요한다. 특히 비선형 자료구조이기때문에 많이 다르게 느껴질 수도 있다!" 트리는 계층적 관계를 표현하는 자료구조이다! 자료구조! 하면 보통은 무엇인가를 저장하고 꺼내는 것이 전부인 것으로 이해하는 경우가 많다. 앞서 보인 선형 자료구조들은 이에 초점이 맞춰져 있었으니 무리도 아니다. 하지만 자료구조는 근본적으로 무엇인가를 "표현" 하는 도구이다. 트리는 데이터의 저과 삭제가 아닌 "표현"에 초점이 맞춰져 있다. 때문에 트리의 ADT를 다음과 같이 바라보면 안된다. "데이터의 저장, 검색 및 삭제가 용이하게 정의되어 있나요?" 대신 다음과 같이 바라봐야 한다. "트리의 구조로 이뤄진 무엇인가를 표현하기에 적절히 정의되어 있나요?" 노드(.. 2022. 3. 16. 자료구조(7) 덱 덱은 앞으로도 뒤로도 넣을 수 있고, 앞으로도 뒤로도 뺄 수 있는 자료구조! 덱은 양방향으로 넣고, 양방향으로 뺄 수 있는 자료구조이기에 스택과 큐의 특성을 모두 갖는, 혹은 스택과 큐를 조합한 형태의 자료구조로 이해되고 있다. 덱도 배열을 기반으로, 그리고 연결 리스트 기반으로도 구현이 가능하다. 하지만 우리는 덱의 구현에 가장 어울린다고 알려진 "양방향 연결 리스트"를 기반으로 덱을 구현할 것이다. 그 이유는 다음 함수와 관련이 있다. "Data DQRemoveLast(Deque * pdeq); // 꼬리에 위치한 데이터(노드) 삭제 위 함수는 꼬리에 위치한 노드를 삭제하는 함수인데, 노드가 양방향으로 연결되어 있지 않으면, 꼬리에 위치한 노드의 삭제는 간단하지 않다. 때문에 덱의 구현에 있어서 양방.. 2022. 3. 16. 이전 1 2 3 다음
