본문 바로가기

전체 글

 (97)
[알고리즘] 이진 탐색(Binary Search) - 코딩밥 이진 탐색이란? 정렬된 데이터에서 사용할 수 있는 '고속'탐색 알고리즘입니다. 이진 탐색이라는 이름은 이 알고리즘의 핵심이 탐색 범위를 1/2씩 줄여나가는 방식에 있기 때문에 붙여졌습니다. 알고리즘을 정리해보자면 다음과 같습니다. 데이터 중앙에 있는 요소를 고릅니다. 중앙 요소값과 찾고자 하는 목표값을 비교합니다. 목표값이 중앙 요소값보다 작으면 중앙을 기준으로 왼쪽, 중앙 요소값보다 크면 오른쪽에 대해 이진 탐색을 새로 수행합니다. 찾고자 하는 값을 찾을 때까지 위 과정을 반복합니다. 예를들어 다음과 같은 오름차순으로 정렬된 데이터에서 67을 찾는다고 가정해보면(요소가 짝수라면 중앙요소는 작은 값 mid = (left + right)/2) 1 7 11 12 14 23 67 139 672 871 => 중..
[알고리즘] 순차 탐색(Sequential Search) 순차 탐색이란? 처음부터 끝까지 차례대로 모든 요소를 비교하여 원하는 데이터를 찾는 탐색 알고리즘입니다. 순차 탐색은 어느 한쪽 방향으로만 탐색할 수 있는 알고리즘이므로 선형 탐색(Linear Search)라고 부르기도 합니다. 처음부터 끝까지 모든 요소를 검사하는 전략이기에 성능은 별로 좋지 않지만, 정렬되지 않은 데이터에서 원하는 항목을 찾을 수 있는 유일한 방법이며 구현이 간단해서 버그를 만들 가능성이 적습니다. 따라서 극적으로 높은 성능을 필요로 하지 않거나 데이터의 크기가 작은 상황에서 유용하게 활용됩니다. 간단한 코드 구현 Node* SLL_SequentialSearh(Node* Head, int Target){ Node* Current = Head; Node* Match = NULL; whi..
[알고리즘] 퀵 정렬(Quick Sort) - 코딩 밥상 퀵 정렬 이란? 이름 그대로 '빠른 정렬'이라고 할 만큼 앞서 배운 버블,삽입 정렬보다 월등히 좋은 성능을 갖습니다. '분할 정복'에 바탕을 둔 알고리즘으로서 동작을 한마디로 정리하면 기준 요소 선정 및 분할의 반복입니다. 기준이 될 요소를 임의로 선정하고 기준 보다 작은 값들은 왼쪽, 큰 값들은 오른쪽으로 옮김 왼쪽 그룹과 오른쪽 그룹을 분할하여 각 그룹에 대해 1번 과정을 수행 그룹의 크기가 1 이하여서 더 이상 분할 할 수 없을 때까지 1번과 2번 과정을 반복 예를들어 5 1 6 4 8 3 7 9 2 을 오름차순으로 퀵 정렬 한다면, 5를 기준) 5 1 6 4 8 3 7 9 2 -> 1 4 3 2 5 6 8 7 9 1을 기준) 1 4 3 2 5 6 8 7 9 -> 1 4 3 2 5 6 8 7 9 왼..
[알고리즘] 삽입 정렬(Insertion Sort) - 코딩밥상 삽입 정렬이란? 삽입 정렬은 책장에 꽂힌 책을 정리하는 과정과 비슷합니다. 예를들어 시리즈 만화를 순서에 맞게 정리하자고 생각해 봅시다. 일단 책장의 왼쪽부터 오른쪽 방향으로 각 권이 옳은 순서로 꽂혀 있는지 확인하고, 잘못된 위치에 꽂혀 있는 책은 뽑아서 올바른 위치에 삽입해나가면 됩니다. 즉 삽입 정렬은 자료구조를 순차적으로 순회하면서 순서에 어긋나는 요소를 찾고, 그 요소를 올바른 위치에 다시 삽입해나가는 정렬 알고리즘입니다. 범위는 첫 2개 요소로 시작하며 알고리즘 수행을 반복하면서 1씩 증가하고 최대 '자료구조의 크기 - 1'까지 수행한다. 범위 마지막에 있는 요소가 정렬 범위 안에서 가장 큰 값을 갖는지 점검하고, 가장 큰 값이 맞으면 그대로 두고 그렇지 않으면 정렬 범위에서 적절한 곳(첫 요..
[알고리즘] 버블 정렬(Bubble Sort) - 코딩밥상 버블 정렬이란? 버블 정렬이란 이름은 물 속 깊은 곳에서 수면을 향호 올라오는 거품들의 모습처럼 데이터를 정렬하기에 붙여진 이름입니다. 즉 자료구조를 순회하면서 이웃한 요소들끼리 데이터를 교환하며 정렬을 수행합니다. 이웃한 요소끼리 데이터를 교환하므로 교환 전에 먼저 이웃끼리 비교하여 바른 순서로 위치해 있는지 확인해야 합니다. 예를들어 5 1 6 4 2 3 을 오름차순으로 버블정렬 하면, 5 1 6 4 2 3 -> 1 5 6 4 2 3 -> 1 5 4 6 2 3 -> 1 5 4 2 6 3 -> 1 5 4 2 3 6 1 5 4 2 3 6 -> 1 4 5 2 3 6 -> 1 4 2 5 3 6 -> 1 4 2 3 5 6 1 4 2 3 5 6 -> 1 2 4 3 5 6 -> 1 2 3 4 5 6 1 2 3 4..
[자료구조] 분리 집합(Disjoint Set) - 코딩밥상 분리 집합이란? 집합의 정의는 특정 조건에 맞는 원소의 모입입니다. 그 중 분리 집합은 서로 공통된 원소를 갖지 않는, 즉 교집합을 갖지 않는 복수의 집합을 뜻합니다. 따라서 분리 집합에는 교집합이 존재 할 수 없습니다(공집합). 때문에 분리 집합은 소속 관계가 분명해야 하는 데이터를 다룰 때 아주 유용합니다. 예들들어 원소 또는 개체가 어느 집합에 소속되어 있는지 정보를 바탕으로 무언가를 하는 알고리즘에 유용합니다. 분리 집합 구현하기 앞 서 살펴본 분리 집합을 트리를 활용하여 구현해 보겠습니다. 주의할 점은 보통의 트리는 부모가 자식을 가리키는 포인터를 갖는 것과 다르게 반대로 자식이 부모를 가리키는 포인터를 갖습니다. 즉 뿌리 노드는 집합 그 자체이고, 뿌리 노드 자신을 포함한 트리 내의 모든 노드..
[자료구조] 수식 트리(Expression Tree) - 코딩밥 수식 트리란? 그 이름 그대로 수식을 표현하는 이진 트리이므로 수식 이진 트리라고 부르기도 합니다. 하나의 연산자당 2개의 피연산자가 필요하기 때문에 수식 트리는 다음 두 가지 규칙을 가집니다. 피연산자는 잎 노드이다. 연산자는 뿌리 노드 또는 가지 노드이다. 또한 이러한 방식으로 뿌리 노드를 연산자로, 왼쪽 서브 트리의 결과값과 오른쪽 서브 트리의 결과값을 파연산자로 하여 마지막 연산을 해주면 답이 됩니다. 즉 수식 트리는 하위 수식 트리의 계산 결과값을 피연산자로 삼아 계산하여 결과를 얻습니다. 이러한 수식 트리의 성질에 적합한 노드 순회 방법은 후위 순회입니다. 수식 트리 구현하기 -알고리즘 수식을 뒤에서부터 앞쪽으로 읽어나가며 토큰을 취한다. 수식에서 제일 마지막에 있는 토큰으로 뿌리 노드를 생성..
[자료구조] 이진 트리(Binary Tree) - 코딩밥상 이진 트리(Binary Tree)란? 앞서 트리에 대한 기본적인 이론을 공부했으니 가장 중요하게 쓰이는 특정 트리들을 정리해보겠습니다. 먼저 이진 트리입니다. 한 문장으로 정의하자면, 하나의 노드가 자식 노드를 최대 2개까지만 가질 수 있는 트리입니다. 즉 모든 노드의 자식 노드 수는 0,1,2 중 하나입니다. 이진 트리의 종류 -포화 이진 트리(Full Binary Tree) 잎 노드를 제외한 모든 노드가 자식을 둘씩 가진 이진 트리. 따라서 포화 이진 트리는 잎 노드들이 모두 같은 깊이에 위치합니다 -완전 이진 트리(Complete Binary Tree) 잎 노드들이 트리의 왼쪽부터 차곡차곡 채워진 트리. 직관적으로 설명하면, 포화 이진 트리가 되기 전 단계에서 노드가 왼쪽 순서로 차곡차곡 채워진 트..

티스토리툴바