본문 바로가기

개발새발 개발자/자료 구조

 (37)
[자료구조] 9-3. 이진 탐색 트리의 연산 (2) 이진 탐색 트리의 추가 연산은 저장할 노드를 생성하는 과정을 통해 수행된다. 새로 추가되는 노드는 반드시 leaf node이다. 먼저 다른 자료구조에서 시간 복잡도가 어떻게 나오는지 복습해보자. - 정렬된 배열일 때7을 추가하려면 추가할만한 위치를 찾는데 O(log n) + 그 다음 원소들을 한 칸씩 밀어내야 하므로 O(n)이 걸린다. - 정렬된 연결 리스트삽입하고자 하는 원소보다 큰 원소 바로 앞을 찾는데에 O(n) + 포인터를 조작해 원소를 추가하는 데에 O(1)이 걸린다. 이진 탐색 트리에서는 O(n)보다 더 빠른 시간에 추가하도록 구현한다. 내가 추가하려는 값 x와 현재 저장되어있는 key를 비교하는데 두 값이 같은 것은 안 된다. 이진 탐색 트리는 서로 다른 값을 저장하고 있어야 하기 때문이다...
[자료구조] 9-2. 이진 탐색 트리의 연산 (1) 이진 탐색 트리의 자료구조는 이진 트리의 자료구조와 같다. 코드를 보면 모든 트리의 노드는 자신이 저장하기로 한 타입의 key값과 왼쪽, 오른쪽 차일드에 대한 포인터를 가지고 있다. 이진 탐색 트리를 만드는 과정에서 루트 노드를 선언했을 때, 아직 저장된 값이 없을 경우 원소로 사용되지 않을 값으로 초기화 한다. 만약 양의 정수만 넣는 트리라면 -1이 될 수 있다. 그런데 이진 탐색 트리를 만들 때 어려운 점이 있다. 아마 대부분의 사람들은 왼쪽의 모습을 기대할 것이다. 하지만 이것은 현실에 존재하지 않는다. 실제로 코드상에서는 key, lchild, rchild라는 말이 나오지만 그림상에 표현되어있는 것은 아니다. 우리의 개념과 실제 프로그래밍 언어 사이의 갭이 존재하는 것이다. 그 갭을 줄이기 위해,..
[자료구조] 9-1. 이진 탐색 트리의 개념 자료구조는 자료를 효율적으로 관리하는 기법이다. 특히 자료를 관리한다는 것은 추가, 검색, 제거 등을 의미한다. 검색 연산은 다시 세 가지로 나눌 수 있다.1. 임의의 원소 찾기2. 가장 먼저/늦게 온 원소 찾기3. 가장 큰/작은 원소 찾기가 있다. 그 중에서 우리는 임의의 원소를 찾는 연산에 집중할 것이다. 자료가 저장된 자료 구조에서 임의의 원소를 찾기 위해서는 먼저 자료구조를 정의해야 한다. 우리가 배운 것에는 크게 두 가지가 있다.1. 정렬되지 않은 배열추가: 맨 뒤에 그냥 쓰면 되니까 O(1)검색: 처음부터 내가 원하는 원소를 찾아야 하므로 O(n)제거: 제거하면 뒤에 있는 원소가 한 씩 이동해야 하므로 O(n) 2. 정렬된 배열추가: 적절한 위치에만 들어갈 수 있기 때문에 O(n)검색: 이진 ..
[자료구조] 7-2. 이진 트리 이진 트리는 degree가 2인 트리를 말한다. 디그리는 각 노드의 최댓값이다. 따라서 자식 노드를 '최대' 2개 가진다는 것이지, 하나도 없거나 1개만 있어도 다 이진 트리가 될 수 있다. 코드로 구현하면 왼쪽 child인 lchild와 오른쪽 child인 rchild에 대한 포인터를 함께 정의한다. 오른쪽의 그림의 트리는 A B C라는 노드를 가지고 있으므로 각각 메모리 공간에 저장된다. 그리고 자식이 있는 A는 lchild와 rchild에 대한 공간을 가지고 있다. 기존 트리와 달리 차일드의 개수를 저장하지 않고 있다. 이진 트리에는 3가지의 성질이 있다. 첫째, i번째 레벨은 최대 2의 (i-1)승 개의 노드를 가질 수 있다. 예를 들어, 맨 위부터 레빌 1 2 3 4인 그림을 보자. 2번째 레벨..
[자료구조] 7-1. 트리의 개념 지금까지 배운 자료구조는 배열, 연결 리스트, 스택, 큐 등이 있었다. 공통점은 다들 리스트형, 선형 자료 구조였다는 것이다. 따라서 모든 원소는 인덱스에 대응되어 순서대로 찾아나갈 수 있다. 선형 자료구조는 항상 그 순서를 유지한다. i-1과 i의 관계가 i와 i+1의 관계와도 동일하다. 가나다 순이거나 123 순이거나. 이것이 바로 선형 자료 구조의 한계이다. 2개 이상의 관계를 표현하기가 어렵다. 만약 위의 데이터를 아래처럼 한 줄로 정렬한다면 어떤 관계는 부자고 어떤 관계는 형제인 것처럼 관계가 일정하지 않은 것을 볼 수 있다. 이렇게 일정하지 않은 관계를 족보식으로 표현하면 부모-자식 관계라는 일정한 관계로 만들 수 있다. 일차원적으로 늘어놓지 않고 이차원적으로 구성을 가져오면 단일한 관계로 모..
[자료구조] 6-3. 쾌속(Quick) 정렬 퀵 소트는 분할 정복 알고리즘에서 결합을 요구하지 않는 2단계 짜리 분할 정복 알고리즘이다. 분할을 잘 하면 결합이 필요하지 않다는 것이 기본 아이디어다. 퀵 정렬은 결합을 요구하지 않도록 리스트를 적절하게 분할하겠다고 하는 것이다. 리스트를 분할할 때 기준이 되는 값을 pivot이라고 부른다. pivot을 기준으로 왼쪽은 pivot보다 작은 수, 오른쪽에는 pivot보다 큰 수만 오도록 분할한다. 이것을 split 혹은 partition이라고 부른다. 합병 정렬이 좌우의 요구 조건 없이 그냥 반으로 쪼개는 것이라면, 퀵 정렬의 split은 pivot을 기준으로 왼쪽에는 pivot보다 작은 수, 오른쪽에는 pivot보다 큰 수가 오도록 분할한다. 따라서 퀵 정렬에서는 split 알고리즘이 매우 중요하다...
[자료구조] 6-2. 합병(merge) 정렬 O(n²) 정렬 알고리즘의 핵심은 이동이든 교환이든 원소들을 하나씩 비교하는 것이었다. O(n log n)정렬은 이것을 지양하는 알고리즘이다. 분할 정복 방식을 추구하는 합병 정렬(머지 정렬)과 쾌속 정렬(퀵 정렬)이 있고 트리 구조를 이용하는 힙 정렬이 있다. 분할 정복은 적절한 크기의 부분 집합으로 분할한 다음 문제를 해결하고 그 부분 집합의 해를 결합해서 최종값을 내는 과정을 거친다. 위의 리스트를 아래로 정렬해보자. 먼저, 주어진 리스트를 반으로 분할한다. 각각의 부분 집합을 정렬하는 정복 단계를 수행한다. 정렬한 두 개의 집합을 합친다. 정복은 그 안에서 또 분할, 정복, 결합의 과정을 거친다. 더 이상 쪼개지지 않을 만큼 작은 걸 만나서 예외처리를 하기 전까지는 재귀적으로 연산을 수행한다. 정..
[자료구조] 6-1. O(n²) 정렬- 삽입 정렬, 버블 정렬, 선택 정렬 지금까지 우리가 배워온 연산들의 공통점은 정렬된 리스트를 요구했다는 것이다. 그렇다면 정렬되지 않은 리스트는 어떻게 정렬해야 할까? 데이터를 정해진 key에 따라서 크기 순으로 배열하는 것을 정렬 알고리즘이라고 한다. 오름차순과 내림차순 두 가지의 기준이 있다. 이 두 가지는 서로 호환되기 때문에 우리는 오름차순 정렬만 언급할 것이다. 정렬 알고리즘의 성능은 데이터의 개수(크기)를 가지고 측정한다. 크게 보면 두 가지의 성능이 있다. 1. O(n²) 정렬 알고리즘버블, 삽입, 선택 2. O(n log n) 정렬 알고리즘합병, 쾌속 O(n²) 정렬 알고리즘은 n개의 데이터를 정렬하려고 할 때 걸리는 시간이 n²에 가깝다고 하는 것이다. 삽입 정렬은 이동에 기반한 정렬이고 버블, 선택 정렬은 교환에 기반하고..

티스토리툴바