개발일지

해시 테이블(Hash Table)개요　해시 테이블은 키(key)와 값(value)을 이용해 데이터를 저장하는 자료구조로서, 키를 주어진 데이터로부터 고유한 숫자 값을 계산하는 해시 함수(hash function)를 이용해 해시 값으로 변환한 후, 해당 해시 값에 해당하는 위치에 값을 저장한다. 여기서 해시 값(hash value)이란 해시 함수에 의해 반환되는 숫자를 의미한다. 　키와 값을 이용한 자료구조라는 점에서 std::map 자료구조와 비슷하다고 생각할 수 있다. 실제로 두 컨테이너는 유사하지만, 내부 구조와 동작 방식, 그리고 성능 특성 등에서 차이가 있다.   hash tablemap탐색이진 탐색해싱정렬XO속도O(1)O(logN)해싱과 충돌　해시 테이블의 핵심은 해싱이다. 해싱(hashing)..

문제설명 입출력 예제 개념 입력이 매우 클 때 소수를 찾는 문제다. 일반적인 O(N)의 시간 복잡도를 갖는 알고리즘은 시간 초과가 걸리기 때문에 효율적으로 소수를 구별해야 한다. 풀이 #include using namespace std; int main() { long long N, n; cin >> N; for (int i = 0; i > n; while (!isPrime(n)) n++; cout

문제설명 입출력 예제 개념 심어져 있는 N개의 가로수 사이에 간격이 일정하도록 심어야 하는 가로수의 개수를 구하는 문제다. 이 문제를 해결하기 위해서 가로수들 사이의 거리를 구한 후, 거리를 일정하게 만들기 위해 최대 공약수 개념을 사용해야 한다. 풀이 #include #include #include int main() { int N; std::cin >> N; std::vector v(N); std::vector dist(N-1); for (int i = 0; i > v[i]; for (int i = 1; i < v.size(); i++) dist[i - 1] = v[i] - v[i - 1]; 가로수의 개수 N을 초기화하고, 가로수가 놓여 있는 위치를 초기화할 벡터 ..

그래프(Graph)개요　지금까지 공부한 트리는 계층적인 데이터를 표현하기에 적합한 자료구조지만, 원형 또는 순환적인 종속성을 표현할 수 없다. 예를 들어 서울과 광역시간의 이동 정보를 생각해 보면, 특정 장소에서 다른 장소로 이동하기 위한 다양한 경로가 존재할 수 있다. 이러한 경우엔 노드와 간선(edge)을 모아놓은 자료구조인 그래프를 사용하는 것이 더 적합하다. 그래프는 순환 구조를 가지므로, 이러한 경우에도 경로를 표현할 수 있다. 따라서, 계층적인 데이터가 아닌 경우엔 그래프를 사용하는 것이 더욱 유용할 것이다.종류　그래`프는 다양한 종류가 있으며, 먼저 무방향(Undirected) 그래프와 방향(Directed) 그래프로 나뉜다. 무방향 그래프에서는 간선이 양방향으로 연결되어 있으며, 방향 그래..

문제설명 입출력 예제 개념 기약분수는 분자와 분모를 더 이상 나눌 수 없는 분수를 의미한다. 따라서 분자와 분모를 통분한 후, 최대 공약수를 나눠주면 답을 찾을 수 있다. 풀이 #include #include int main() { int n1, d1; std::cin >> n1 >> d1; int n2, d2; std::cin >> n2 >> d2; int n = n1 * d2 + n2 * d1; int d = d1 * d2; int gcd = std::gcd(n, d); std::cout

문제설명 입출력 예제 개념 최소 공배수를 찾는 문제다. 입력 A와 B에 대하여 두 수의 최소 공약수를 구하고, A * B / 최소 공약수를 하면 최대 공배수를 구할 수 있다. (유클리드 호제법) 풀이 #include int GCD(int a, int b) { if (b == 0) return a; return GCD(b, a % b); } int main() { long long int A, B, gcd; std::cin >> A >> B; gcd = GCD(A, B); std::cout

문제설명 입출력 예제 개념 문자열 S에 대해 서로 다른 부분 문자열의 개수를 구하는 문제다. 여기서 연속된 일부분이라는 것에 주목해야 한다. 즉, S의 길이가 1인 부분 문자열은 a, b, a, b, c가 되고, 여기서 서로 다른 부분 문자열은 a, b, c S의 길이가 2인 부분 문자열은 ab, ba, ab, bc가 되고, 여기서 서로 다른 부분 문자열은 ab, ba, bc S의 길이가 3인 부분 문자열은 aba, bab, abc가 되고, 여기서 서로 다른 부분 문자열은 aba, bab, abc S의 길이가 4인 부분 문자열은 abab, babc가 되고, 여기서 서로 다른 부분 문자열은 abab, babc S의 길이가 5인 부분 문자열은 ababc가 되고, 여기서 서로 다른 부분 문자열은 ababc 따..

문제설명 입출력 예제 개념 집합 A와 B가 주어졌을 때 (A - B) ∪ (B - A)의 값을 구하는 문제다. 자료구조 map을 이용해서 푸는 방법도 있지만, 필자는 조금 다르게 풀었다. 두 집합의 원소를 벡터에 삽입 교집합을 이진 탐색을 이용하여 정수형 변수에 삽입 벡터의 크기에서 교집합의 원소의 차를 출력 풀이 #include #include #include int main() { int N, M, n, count = 0; std::cin >> N >> M; std::vector v(N + M); 집합 A, B의 원소의 개수 N, M, 입력받을 숫자 n, 교집합의 수 count를 초기화해준다. 그리고 N + M의 크기를 가지는 벡터 v를 초기화해 준다. for (int i = 0; i < N; i++..

힙(Heap)개요　우리는 힙 자료구조에 대해 이전에 컨테이너 어댑터 포스팅에서 간략하게 알아본 적이 있다. 특정한 우선순위를 갖는 이 컨테이너에 대해 더욱 자세하게 알아보는 시간을 갖도록 하자. 　힙은 다음과 같은 시간 복잡도 특징을 갖고 있다.최대/최소 원소에 접근: O(1)원소 삽입, 삭제: O(logN) 　힙은 다음과 같은 특징이 있다.부모 노드와 자식 노드의 우선순위는 항상 유지우선순위가 높은 원소는 항상 루트 노드에 존재완전 이진 트리(Perfect Binary Tree)　힙은 원소 삽입 또는 삭제에 대해 O(logN)의 시간 복잡도를 만족해야 하기 때문에 일반적으로 완전 이진트리를 사용해야 한다. 여기서 완전 이진 트리(Complete Binary Tree, 포화 이진트리)는 레벨 순서대로 왼..

문제설명 입출력 예제 개념 N개의 문자열과 M개의 문자열 중 겹치는 문자열을 출력하는 문제다. 여기서 사전순으로 출력해야 하기 때문에 set 자료 구조를 이용하여 저장과 동시에 정렬을 하면 편하게 해결할 수 있다. 풀이 #include #include #include #include int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int N, M; std::string str; std::vector v; std::set res; 문자열의 수 N, M, 입력받을 문자열 str, 초기에 N개의 벡터를 저장할 벡터 v, 최종 적으로 자료를 담을 res를 초기화한다. std::cin >> N >> M; while (N--) { std:..