. 해싱(hashing)- 어떤 데이터셋을 앞으로 입력받아 메모리상에 저장해야 하는데, 그 데이터셋의 각 데이터가 길이가 일정하지 않을 것이라고 하자. 어떻게 저장해야 할까? 어떤 데이터가 들어올지 알 수 없으므로 각 길이마다 가능한 모든 형태의 데이터가 들어올 것이라고 가정하고 그에 해당하는 크기만큼의 메모리를 할당을 해두어야 할까? 이는 한 방법이 될 수 있지만, 지나치게 비효율적인 방법이다. 이때, 이보...

. 다익스트라 알고리즘- 간선의 가중치가 양수인 그래프에서, 그래프 상의 한 정점에서 출발해 나머지 모든 정점으로 도달하는 최단경로를 구하는 알고리즘이다. 다음과 같은 알고리즘으로 수행된다) ‘시작점에서 i번 정점에 도착하는 데 걸리는 최단거리’로 dist[i] 값이 정의되는 dist 배열을 두고, i번 정점이 시작점과 인접하면 그 간선의 가중치로, 인접하지 않다면 무한대로 dist 배열을 초기화한다.) di...

'''. 숫자들이 오름차순으로 정렬된 리스트와 타겟 넘버가 주어질 때, 리스트에서 타겟 넘버가 삽입될 인덱스를 구하는 문제.. 이진탐색을 구현할 때 주목해야 할 부분들) m = (s+e)//- 범위 내 수의 개수가 짝수 -> s에서 m까지의 개수와 m+부터 e까지의 개수가 같다. - 범위 내 수의 개수가 홀수 -> s에서 m까지의 개수가 m+부터 e까지의 개수보다 하나 많다.) while s ...

. 문제최대 무게 K까지 담을 수 있는 배낭에 무게 W[i], 가치 V[i]인 N개의 물건 중 가능한 많은 물건을 담아 가치의 총합을 최대로 하고자 할 때, 그 가치 총합의 최댓값을 구하는 문제.. 풀이배낭에 담을 수 있는 최대 무게 K가 아주 크지 않다면 간단한 다이나믹 프로그래밍으로 풀 수 있다.dp[i][j]: 배낭에 i번째 물건을 담아 무게가 j가 되었을 때 배낭에 담긴 물건들의 가치 총합의 최댓값위와...

. 개요- 이진트리의 개념을 활용하여 문자열을 매우 효율적으로 무손실 압축할 수 있다. 허프만 코딩은 주어진 문자열의 정보를 손실 없이 효율적으로 압축하는 대표적인 암호화 기법의 하나로, 그 과정에서 이진트리를 사용한다.- 간단히 설명하면, 어떤 문자열이 주어진다 할 때, 허프만 코딩은 이를 구성하는 각 문자들을 빈도순으로 정렬한 후 빈도가 가장 적은 문자들부터 이진트리를 구성한다. (문자들은 오로지 이진트리...

. 개요- BST는 최악의 경우 삽입/삭제/탐색에 O(n)의 시간이 걸리는 단점이 있어 여러 균형 BST가 제시되었다. 예를 들어 AVL 트리의 경우 이를 구성하는 모든 노드의 좌우 서브트리 높이차가 이하가 되도록 해 이러한 BST의 단점을 극복했는데, AVL 트리의 경우 삽입/삭제 때마다 ‘회전 연산’을 수행해야 하고 이 회전 연산의 수행 횟수가 (선형시간은 아니지만) 꽤 있을 수 있다는 단점이 있다.- ...

. 개요- BST의 단점이 최악의 경우 트리의 모든 노드들이 선형적으로 길게 늘어서는 경우가 있을 수 있다는 것이므로, 이를 극복하기 위해 여러 아이디어가 제시되었다. 각 노드들이 갖는 양 서브트리의 높이차가 이하여야 한다는 AVL 트리나 루트에서 모든 외부노드까지 경로의 노드수가 최댓값이 커봐야 최솟값의 두 배여야 한다는 레드블랙 트리 또한 그 사례들이다.- B트리는 ‘한 노드가 갖는 키값의 수가 각각 달...

#include <iostream>#include <queue>#include <vector>using namespace std;struct comp{ bool operator()(vector<int> a, vector<int> b) { return a[] > b[]; }};priority_queue<vector<...

. 스레드 이진트리- 연결리스트로 구현된 이진트리의 경우, 자식이 개 이하인 노드는 자식을 가리키는 메모리 주솟값이 하나 이상 null을 가리키게 된다. 예를 들어 노드수 n개인 이진트리가 있다 하면 여기서 자식을 가리키는 메모리 주솟값이 n개가 할당되게 되는데, 그 중 절반이 null을 가리키게 된다. 스레드 이진트리는 이처럼 null을 가리켜야 할 메모리 주솟값에 그 노드의 중위선행자/후속자(그 트리를 중...

. 그래프 관련 용어들 그래프: 개 이상의 노드와 각 노드 사이를 잇는 개 이상의 간선으로 구성돼있는 노드 사이 연결 관계 연결요소: 어떤 그래프의 부분그래프로서 이를 구성하는 모든 노드가 서로 연결(=노드와 노드 사이에 개 이상의 간선으로 이루어진 경로가 존재)되어 있는 부분그래프. 하나의 그래프는 서로 이어지지 않은 수개의  연결요소로 이루어진다. 단절점: 그래프의 어떤 ...

. 개요- AOE 네트워크는 그래프의 일종으로, 간선에 가중치가 있는 방향그래프이다. 간선은 작업, 간선의 가중치는 작업 수행 시간, 간선의 방향은 사건의 선후관계를 나타내며, 간선의 끝부분에 있는 노드는 그 작업의 수행의 결과로서 도달하게 되는 사건을 의미한다. 어떤 사건도 그 선행 작업이 종료되기 전에는 일어날 수 없다. - 수개의 작업을 동시에 수행할 수 있지만, 모든 작업을 다 수행해 최종 사건에 도달...

. \(O\) (big-O) 표기법) 정의어떤 알고리즘의 시간복잡도를 입력크기 \(n\) 에 관한 다항식 \( f(n) \) 으로 나타냈을 때,어떤 양수 \(n_\) 보다 큰 모든 \(n\) 에 대하여 \(f(n) \le k \cdot g(n) \) 을 만족하는 양수 \(k\) 와 \(n_\) 가 존재한다면 \(f(n) = O( g(n) )\) 으로 정의된다.) 이해- 알고리즘의 시간복잡도를 구체적으로 계산해...

. \(P = NP\) ?) 결정문제(decision problem)- 출력이 단순히 yes 또는 no인 문제를 결정문제라 한다. 최적해를 구하는 모든 문제는 그에 상응하는 결정문제가 있다. 예를 들어 TSP 문제는 ‘주어진 경로보다 더 짧은 여행경로가 있는가?’ 라는 결정문제로 대응된다.- 결정문제 중, 다차시간 알고리즘으로 풀 수 있는 모든 결정문제 집합을 흔히 P라 칭한다.) 비결정적 알고리즘(nonde...

. 개요- Knuth - Morris - Pratt 알고리즘의 약자로, 찾고자 하는 단어를 긴 문자열 내에서 검색하는 문자열 검색 알고리즘의 하나다. 알고리즘의 발견자들인 James Morris, Donald Knuth, Vaughan Pratt의 이름을 따서 지어진 이름이다.- 이와 같은 문자열 검색 알고리즘을 완전탐색_(긴 문자열 인덱스 하나하나를 시작점으로 해서, 그 지점에서부터 검색 단어가 문자열과 일...

가장 기초적인 비트마스크 DP 문제./*. 노드가 N개인 양방향 그래프에서 어느 한 노드를 출발해 모든 노드를 방문하고 시작점으로 돌아오는 순회 경로를 만든다고 할 때(단, 한번 지난 노드는 다시 지날 수 없다), 지나온 간선 가중치의 합이 최소인 경로의 가중치의 합을 구하는 문제. . dp[mask][i]: mask라는 경로를 거쳐 i번 노드에 도착했다 할 때, 거...

N x N 격자판에서의 간단한 DFS 문제./*. N x N 격자판에 체스의 퀸을 N개 배치하되 각 퀸이 서로 공격할 수 없는 위치에만 퀸을 배치할 경우, 가능한 배치의 경우의 수를 구하는 문제. . 다음 알고리즘으로 코드를 구현했다. () i번째 행에서 퀸을 놓기 합당한 열을 탐색한다. - i-번째 행까지 총 i-개의 퀸이 배치되어 있으므로, i번째 행의 j열에 퀸을 배치한다 할 때 ...