Always Be Wise

해시 테이블(Hash Table)은 키(Key)를 값(Value)에 매핑할 수 있는 자료구조를 의미한다. 해시 테이블의 가장 큰 특징은 대부분의 연산이 분할 상환 분석에 따른 시간 복잡도가 O(1)이라는 점이다. 덕분에 데이터 양에 관계 없이 빠른 성능을 기대할 수 있다. 해시 함수(Hash Function) 해시 테이블의 핵심은 해시 함수이다. 해시 함수란 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수를 의미한다. 예를 들어, 입력값 ABC, 1324BC, AF32B로 각각 3글자, 6글자, 5글자를 2바이트의 고정 크기 값으로 매핑하는 함수를 해시 함수라고 한다. 해시 테이블을 인덱싱하기 위해 이처럼 해시 함수를 사용하는 것을 해싱이라고 하며, 해싱은 정보를 가능한 빠르게 저..

레드-블랙 트리(Red-Black Tree)에 대한 설명과 구현 코드는 아래 깃허브 링크에 작성하였다. ▶ 관련 링크 https://github.com/bewisesh91/rbtree-lab/blob/main/README.md GitHub - bewisesh91/rbtree-lab Contribute to bewisesh91/rbtree-lab development by creating an account on GitHub. github.com

최대 차수가 2인 트리, 즉 노드가 왼쪽 자식과 오른쪽 자식만을 갖는 트리를 이진 트리라고 한다. 두 자식 가운데 하나 또는 둘 다 존재하지 않는 노드가 있어도 상관 없다. 완전 이진 트리(Complete Binary Tree) 루트부터 아래쪽 레벨로 노드가 가득 차 있고, 같은 레벨 안에서 왼쪽부터 오른쪽으로 노드가 채워져 있는 이진 트리를 완전 이진 트리(Complete Binary Tree)라고 한다. 높이가 K인 완전 이진 트리가 가질 수 있는 노드의 수는 2의 K+1승 -1개 이다(ex 높이가 3일 때, 최대 15개). 균형 이진 트리(Balacned Binary Tree) 균형 이진 트리(Balanced Binary Tree)란 트리 내부 모든 노드의 왼쪽 서브 트리와 오른쪽 서브 트리의 높이..

그리디 알고리즘(Greedy Algorithm)이란 문제를 해결하는 과정에서 순간 순간마다 최선이라고 생각하는 것을 선택하여 최종 해답에 도달하는 알고리즘을 의미한다. 계산 과정이 굉장히 빠른 알고리즘이지만, 순간 순간 마다의 최선의 선택이 언제나 전체 결과의 최선의 해결책을 보장하지는 않는다는 단점이 있다. 그리디 알고리즘을 사용하기 위해서는 다음의 두 가지 조건을 만족해야 한다. 1. 최적 부분 구조(Optimal Substructure) : 부분 문제의 최적 결과를 전체에 그대로 적용할 수 있다. 2. 탐욕적 선택 속성(Greedy Choice Property) : 이전의 선택이 이후 선택에 영향을 주지 않는다.

동적 프로그래밍(Dynamic Programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 해결하는 방법을 의미한다. 여러 개의 문제로 나누어 해결한다는 점에서 분할 정복(Divide and Conquer)과 유사해 보이지만, 동적 프로그래밍의 경우, 간단한 문제들이 반복적으로 일어난다는 점에서 차이가 있다. 즉, 동적 프로그래밍은 간단한 문제들을 한 번만 해결하고 그보다 복잡한 문제를 풀어나갈 때 똑같은 간단한 문제가 다시 나타나면 그 결과 값을 이용해해결하는 방법이다. 이때, 간단한 문제의 결과 값을 기억하여 반복 수행을 제거하는 과정을 메모이제이션(Memoization)이라고 한다. 동적 프로그래밍을 사용하려면 아래 두 가지 조건을 만족해야 한다. 1. 부분 문제 반복(Overlapp..

플로이드 워셜 알고리즘(Floyed-Warshall Algorithm)은 모든 정점에서 모든 정점 사이의 최단 경로를 찾는 알고리즘이다. 다익스트라 알고리즘이 하나의 정점에서 모든 정점 사이의 최단 경로를 찾는 것과는 차이가 있다. 또한 가중치를 음수와 양수 모두 가질 수 있다는 점도 다르다. 플로이드 워셜 알고리즘의 기본 동작 원리는 다음과 같다. 1. 최단 거리 테이블을 만든다. 이때, 초기 주어진 조건으로 하나의 정점에서 다른 정점으로 바로 갈 수 있는 경우 그 값으로, 갈 수 없는 경우 무한대로 테이블을 초기화한다. 2. 모든 정점에 대하여 해당 정점을 지나 다른 정점으로 이동할 때의 거리를 구하고, 기존의 거리와 비교하여 그 거리가 더 짧다면 테이블의 값을 갱신한다. 점화식으로 표현하자면 다음과..

위상 정렬은 사이클이 없는 방향 그래프의 정점들을 방향성을 거스르지 않고 순서대로 나열하는 것을 의미한다. 정렬 알고리즘의 일종으로, 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다. 위 그림과 같이 수강해야 할 과목이 세 가지 있다고 가정하자. 세 과목을 정상적으로 수강하기 위해서는 화살표의 방향대로 [자료구조 - 알고리즘 - 고급 알고리즘] 순으로 들어야 한다. 만약 [자료구조 - 고급 알고리즘 - 알고리즘] 순으로 듣고자 한다면, 해당 순서는 화살표의 방향을 거스르기 때문에 올바른 수강 순서가 아니다. 위상 정렬 알고리즘을 이해하기 위해서는 진입차수와 진출차수에 대한 개념을 알아야 한다. 진입차수(Indegree)는 특정한 정점으로 들어오는 간선의 개수를 의미..

이분 그래프는 아래 그림 처럼 그래프의 정점들이 두개의 그룹(빨간색 정점으로 이루어진 그룹, 파란색 정점으로 이루어진 그룹)으로 나뉘고, 같은 그룹의 정점들끼리는 서로 간선으로 이어지지 않는 경우를 의미한다. 간선이 없고 정점만 있는 경우도 이분 그래프이다.

다익스트라 알고리즘(Dijkstra Algorithm)은 그래프 내 하나의 정점에서 다른 모든 정점까지의 최단 거리/경로를 구하는 알고리즘이다. BFS와 다른 점은 가중치 그래프에서도 사용 가능하다는 것이다. 다만, 그래프 내 엣지들은 모두 양수여야 한다. 다익스트라 알고리즘의 기본 동작 원리는 다음과 같다. 1. 출발 정점을 설정한다. 2. 최단 거리 테이블을 초기화한다. 이때, 초기 값은 출발 정점을 제외하고 모두 무한대 값을 가진다. 3. 출발 정점과 연결된 정점 가운데 방문하지 않는 정점들을 찾는다. 4. 그중 최단 거리가 가장 짧은 정점을선택한다. 이때, 최단 거리란 갱신하기 전 최단 거리를 의미하며 2번에서 초기화한 테이블의 값과는 다르다. 5. 해당 정점을 거쳐 다른 정점으로 가는 거리를 ..

크루스칼 알고리즘(Kruskal Algorithm)이란 무방향의 가중치 그래프의 모든 정점을 최소 가중치로 연결하는 방법을 의미한다. 최소 스패닝 트리를 찾을 때 대표적으로 사용하는 알고리즘이다. 크루스칼 알고리즘은 무언가를 결정해야 할 때마다 그 순간에 가장 좋다고 생각하는 것을 선택하는 탐욕적인(Greedy) 방법을 따른다. 구체적인 동작 과정은 아래와 같다. 1) 모든 엣지들을 끊어 놓는다. 2) 엣지들을 가중치 순으로 오름차순 정렬한다. 3) 정렬된 엣지들을 순서대로 선택한다(가장 낮은 가중치를 먼저 선택). 4) 선택한 엣지가 사이클을 형성하지 않는지 확인한다. 5) 사이클을 형성하지 않는다면, 해당 엣지를 최소 스패닝 트리에 포함시킨다. 엣지들을 가중치 순으로 오름차순 정렬한다. B-C D-E..