📚 Computer Science/Algorithm

[Algorithm] C++ DFS & BFS 이해 및 구현

DFS : Depth First Search (깊이 우선 탐색) 이동할 수 있는 모든 노드를 이동하다가 더이상 이동할 수 없으면 뒤로 다시 돌아와 탐색 스택이나 재귀함수로 구현가능 노드 방문 시, 해당 노드의 방문 여부를 체크해야만 한다. (isVisited) DFS로 구현한 경로가 최단 경로인지 확인은 불가능하다. DFS의 시간복잡도 DFS(idx)는 해당되는 idx에 방문하는 함수이다. 그렇기에 해당 트리의 차수만큼 함수가 호출된다. 즉 DFS는 시간복잡도 * 차수가 DFS 알고리즘의 시간복잡도이다. 하지만 구현 방법에 따라 시간복잡도가 달라지며, 재귀함수로 구현하였을 경우 별도의 자료구조를 필요로 하지않기에 메모리를 아낄 수가 있다. 아래는 DFS의 진행되는 이미지이다. Code ( C++ ) - ..

[Algorithm] C++ Queue (큐) 클래스 구현

큐 ( Queue ) FIFO(First In First Out) - 선입선출 이라고 불린다. 삽입연산을 Push라고 하고, 삭제연산을 Pop이라 한다. 보통 BFS (너비 우선 탐색)에 쓰인다. 나중에 집어넣은 원소가 먼저나오는 스택 (Stack)과는 반대되는 개념이다. 예시 가장 쉽게 이해되는 구문이 위키백과에 잘 설명이 되어있다. " 영어 단어 queue는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다. " 아래는 큐의 이해를 돕기위한 예시이다. 은행 업무 너비 우선 탐색(BFS, Breadth-First Search) 캐시(Cache) 구현 프로세스 관리 Code #include using namespace std; ..

[Algorithm] C++ Stack (스택) 클래스 구현

스택 (Stack) 자료구조에서 무언가를 쌓는다는 의미로 쓰인다. LIFO(Last In First Out) - 후입선출 이라고 불린다. 삽입연산을 Push라고 하고, 삭제연산을 Pop이라 한다. 보통 DFS (깊이 우선 탐색)에 쓰인다. 예시 웹 브라우저 (뒤로 가기) : 가장 나중에 열린 페이지부터 다시 보여준다. 실행 취소 (undo) : 가장 나중에 실행된 것부터 실행을 취소한다. 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사) Code #include using namespace std; class Stack { private: int _count; int _size; short* m_data; public : // 생성자 Stack() { _size = 0; _count = 0; ..

[Algorithm] C++ Merge Sort (병합정렬)

병합정렬 List를 반으로 더이상 나눌 수 없을때까지 반으로 나누고(Divide - 분할), 나누어진 부분 List들을 두개씩 짝지어 정렬(Conquer - 정복)하며 합치는(Combine - 결합)과정을 반복하는 방법 병합정렬 알고리즘 하나의 List를 더 이상 나눠질 수 없을 때 까지 반으로 분할한다. 더 이상 나눌 수 있는 List가 없을 경우, 반복적으로 나뉘어진 부분 List들을 정렬하며 합친다. 예시 병합정렬의 알고리즘은 기본적으로 분할정복을 사용한다. 원소들의 List를 계속하여 나뉘어지지 않을때 까지 반으로 나누는 재귀 알고리즘을 이용한다. 원소 List에 둘 이상의 원소가 있는 경우 List를 분할하고, 양쪽 절반에 대해 병합정렬을 재귀적으로 호출하여 진행한다. 아래의 그림은 분할한 원소..

[Algorithm] C++ Quick Sort (퀵정렬)

퀵정렬 List에서 하나의 피벗을 정하고 이를 기준으로 피벗보다 작은 요소들, 큰 요소들로 두개의 부분 List를 만들어(Divide 분할) 정렬 후 다시 결합(Conquer 정복)을 재귀적으로 반복하는 방법 퀵정렬 알고리즘 1. 리스트 안에 있는 한 요소를 피벗(Pivot)으로 설정한다. 2. 피벗을 기준으로 왼쪽에서부터는 피벗보다 큰 값(a)을 찾고, 오른쪽에서부터는 피벗보다 작은 값(b)을 찾는다. 3. a와 b를 교한한다. 4. 왼쪽에서부터 찾은 a값의 위치와 오른쪽에서부터 찾은 b값의 위치가 엇갈리지 않을 때까지 2~3번 과정을 반복한다. 5. 엇갈린 경우에는 오른쪽에서부터 찾은 피벗보다 작은 값(b)과 피벗값을 교환한다. 6. 위의 과정에서 한 번의 분할이 이루어졌고, 두 개의 부분리스트에 대..

[Algorithm] C++ Insertion Sort (삽입정렬)

삽입정렬 앞의 원소들이 정렬되어 있다는 가정 하에 적절한 위치에 삽입하는 방법 삽입정렬 알고리즘 i번째 원소를 1부터 k - 1번째 까지와 비교하여 적절한 위치에 끼워넣고 그 뒤의 자료를 한 칸씩 뒤로 밀어내는 방식 1. 각 패스에서 1부터 각 원소에 대해 하나씩 (n - 1) 비교한다. 2. 현재 원소는 이미 정렬된 하위 목록에 있는 원소와 비교하여 확인된다. 3. 이미 정렬된 하위 목록들을 살펴보면서 더 큰 원소를 오른쪽으로 이동한다. 예시 아래 예시는 위의 예시의 다섯 번째 패스를 자세히 보여준다. 알고리즘의 이 지점에서 17, 26, 54, 77, 93으로 구성된 5개 원소의 정렬된 하위 원소들이 존재한다. 이때 이미 정렬된 항목에 31을 다시 삽입하려고 할 경우, 93에 대한 첫 번째 비교시 다..

[Algorithm] C++ Bubble Sort (거품정렬)

거품정렬 두개의 인접한 원소를 비교하는 정렬이다. 선택정렬과 유사하나, 다른점은 앞에서부터 차례로 정렬하기때문에 '안정정렬' 이라고도 한다. 정렬 방식중 가장 간단하며 쉬우나, 다른 정렬보다 원소의 교환이 많아, 소요되는 시간이 길다. 원소들의 정렬과정에서 원소의 이동이 거품처럼 수면위로 올라온다는 뜻으로 거품 정렬이라는 이름이 붙기도하였다. 거품정렬 알고리즘 앞에서부터 현재 원소와 바로 다음 원소를 비교한다. 현재 원소가 바로 다음의 원소보다 클 경우 교환한다. (오름차순 기준) 그 이후 바로 다음 원소로 이동하여, 해당 원소와 다음 원소를 비교한다. 예시 원소들 정렬 흐름은 아래 gif 파일로 확인할 수 있다. 거품정렬 특징 추가적인 메모리 소비가 적다. 구현이 매우 간단하다. 안정정렬이 가능하다. ..

[Algorithm] C++ Selection Sort (선택정렬)

선택정렬 주어진 리스트에서 최솟값을 맨 앞으로 보내는 방법이다. 원소들을 큰순이나, 작은순으로 정렬하는 알고리즘 중 하나이다. 선택정렬 알고리즘 Selection Sort는 Bubble Sort와 유사한 알고리즘이다. 해당 순서에 원소를 넣을 위치는 정해져있고, 어떤 원소를 넣을지 선택하는 알고리즘이다. 진행 Process는 다음과 같다. 1. 주어진 배열 중 최소값을 찾는다. 2. 그 값을 맨 앞에 위치한 값과 교체한다. 3. 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다. 예시 선택정렬 특징 Bubble Sort와 마찬가지로 알고리즘이 단순하다. 정렬을 위한 비교 횟수는 많지만, Bubble Sort에 비해 실제로 교환횟수가 적기에 많은 교환이 일어나야하는 자료에서는 비효율적이다. 내부 배..