개발일지

문제설명 입출력 예제 개념 주어진 정수 N(짝수)을 두 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 문제다. 예를 들어, 10을 입력하면 10 = 3 + 7, 5 + 5로 2개가 출력된다. 이때 소수의 순서만 다른 것은 같은 파티션인 것에 유의하자. 문제의 시간 제한이 매우 빡빡하기 때문에, 에라토스테네스의 체 알고리즘을 사용하여 주어진 범위 내의 소수를 미리 구한 후, 구한 소수들을 활용하여 문제를 해결할 수 있다. 이러한 알고리즘은 시간 복잡도가 O(Nlog(log(N))) 으로 매우 빠르다. 풀이 #include #include #include using namespace std; const int n = 1000000; vector isprime(n + 1, true); int main() ..

문제설명 입출력 예제 개념 자연수 n과 2n 사이의 소수의 개수를 출력하는 문제다. O(sqrt(N)) 보다 조금 더 세밀한 시간 조정이 필요하다. 풀이 #include using namespace std; bool IsPrime(long long num) { if (num N; if (N == 0) break; for (int i = N + 1; i

충돌 해결체이닝(Chaining)　해시 충돌 문제를 해결하는 첫 번째 방법인 체이닝 기법에서는 충돌이 발생한 지점에서 연결 리스트를 만든다. 즉, 이 방법은 해시 테이블의 특정 위치에서 하나의 연결 리스트를 저장하여, 충돌이 발생하면 리스트의 맨 뒤에 새로운 키를 추가하는 방식이다.  　연결 리스트는 포인터를 이용하여 다음 노드를 가리키기 때문에, 메모리를 재사용하지 않아 중간에 요소를 삽입하거나 삭제하는 경우에도 O(1) 시간에 수행할 수 있다는 장점이 있다. 그리고 배열과 다르게 데이터가 흩어져 있지 않고 연속된 메모리 공간을 차지하지 않으므로, 캐시 효율성이 높다. 　이러한 체이닝 기법을 이용하여 이전 충돌 문제를 해결해 보자. #include #include #include #include cla..

문제설명 입출력 예제 개념 주어진 범위 내의 소수를 찾는 문제다. 이전에 포스팅했던 소수 찾는 알고리즘을 활용하면 쉽게 풀 수 있다. 풀이 #include bool IsPrime(int n) { if (n m >> n; for (int i = m; i

해시 테이블(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을 초기화하고, 가로수가 놓여 있는 위치를 초기화할 벡터 ..

문제설명 입출력 예제 개념 기약분수는 분자와 분모를 더 이상 나눌 수 없는 분수를 의미한다. 따라서 분자와 분모를 통분한 후, 최대 공약수를 나눠주면 답을 찾을 수 있다. 풀이 #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 따..