본문 바로가기
반응형

알고리즘/BAEKJOON88

BOJ 2467, 2470 : 두 용액 알고리즘 문제 전체 링크 www.acmicpc.net/problem/2467 www.acmicpc.net/problem/2470 BOJ 2467은 입력이 정렬이 되어서 들어오는 차이가 있다. 그 외 풀이는 BOJ 2470과 같다. B형에서 어떤 조건을 만족하는 값을 찾으려면 대부분 정렬을 한 후, 이분 탐색으로 찾는다. 이분 탐색 외에도 답을 찾는 테크닉 중 하나가 투 포인터 알고리즘이다. 포인터(index) 2개를 이용하여 효율적으로 원하는 답을 찾는다. 두 용액 문제는 모든 배열의 값 2개 중 합이 0에 가까운 값 2개를 찾는다. 용액이 모두 양수라면 가장 작은 두 값이, 모두 음수라면 가장 큰 두 값이 답이 된다. 문제는 양수와 음수가 있는 경우이다. 이 경우는 가장 작은 값과 가장 큰 값을 더해보.. 2021. 3. 29.
BOJ 10830 : 행렬 제곱 알고리즘 문제 전체 링크 www.acmicpc.net/problem/10830 곱셈 문제처럼 이진수의 원리를 그대로 적용하여 해결하였다. 행렬의 곱은 A = B * C 일 때, A[r][c] = ∑B[r][k] * B[k][c]를 이용한다. #include typedef unsigned long long int ull; int N; ull B; int matrix[7][7]; int ans[7][7]; void multiply(int matrixA[][7], int matrixB[][7]) { int temp[7][7] = { 0 }; for (int r = 1; r 2021. 3. 25.
BOJ 1629 : 곱셈 알고리즘 문제 전체 링크 www.acmicpc.net/problem/1629 A를 B번 곱할 때, B가 최대 2,147,483,647이므로, 2,147,483,647번 곱하면 연산 비용이 너무 많이 든다. 즉, O(B)의 비용이 든다. 하지만 분할 정복을 이용하면, O(logB)로 해결 가능하다. 만약 A를 100번 곱해야 한다고 생각해보자. A100 = A50 * A50 A50 = A25 * A25 A25 = A12 * A13 A12 = A6 * A6 A13 = A6 * A7 A6 = A3 * A3 A7 = A3 * A4 A3 = A * A2 A4 = A2 * A2 A2 = A * A 따라서, 재귀 함수를 이용해 답을 (log100)번만에 찾을 수 있다. typedef unsigned long long.. 2021. 3. 24.
BOJ 2696 : 중앙값 구하기 알고리즘 문제 전체 링크 www.acmicpc.net/problem/2696 문제의 원리는 가운데를 말해요와 같다. 차이점은 매 tc마다 heap을 초기화 그리고 최초 입력을 받고 홀수 번째 입력부터 가운데 값을 출력 한 줄에 10개씩 출력 이다. #include int T, M; int minHeap[100100]; int minHn; int maxHeap[100100]; int maxHn; int maxPop(int* heap, int& hn) { int tmp, ret; ret = heap[1]; heap[1] = heap[hn]; heap[hn--] = -10001; for (int i = 1; i * 2 heap[i * 2] && heap[i] > heap[i * 2 + 1]) break; el.. 2021. 3. 20.
BOJ 4913 : 페르마의 크리스마스 정리 알고리즘 문제 전체 링크 www.acmicpc.net/problem/4913 1,000,000의 크기의 수를 매번 소수 판단할 수 없으므로 에라토스테네스의 체를 이용하여 메모해둔다. 그리고 매번 L과 U에 포함된 소수의 개수와 소수 중 제곱수의 수를 셀 수 없으므로 아래와 같이 메모한다. #define MAX (1000000) int L, U; int prime[MAX + 100]; int primeSum[MAX + 100]; int squreSum[MAX + 100]; int main() { makePrime(); /* 에라토스테네스의 체 */ squreSum[2] = primeSum[2] = 1; for (int i = 3; i = 1 : L이 자연수인 경우 (U는 항상 L보다 크다) 2) L이 음수.. 2021. 3. 19.
BOJ 7569 : 토마토 (3차원) SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 알고리즘 문제 전체 링크 www.acmicpc.net/problem/7569  BOJ 7576 토마토는 2차원에서 토마토가 퍼져나갔다.이번 문제는 3차원에서 토마토를 만들어가면 된다. 2차원에서는 4방향으로 토마토를 큐에 담았지만,3차원에서는 좌표의 높이(h)에 대해 위, 아래 토마토를 추가해주면 된다.즉, 총 6방향으로 BFS가 퍼져 나간다./* 순서대로 왼쪽, 위, 오른쪽, 아래 */int dr[] = { 0, -1, 0, 1 };int dc[] = { -1, 0, 1, 0 };void BFS(){ for (int h = 1; h rp) { QUEUE out = queue[rp++]; for (int i = 0; i  그리고 inp.. 2021. 3. 17.
BOJ 7576 : 토마토 A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 알고리즘 문제 전체 링크 www.acmicpc.net/problem/7576  미로 탐색 문제에서 BFS를 이용하여 거리를 계산하였다. 같은 방법을 토마토 문제에서 적용할 수 있다.토마토를 모두 넣고 미로 탐색과 같은 방식으로 BFS를 적용하면, 토마토가 상자를 꽉 채우게 된다.토마토가 상자를 꽉 채우는 것은.각 토마토가 상자에서 최소로 가능 경로를 모든 토마토에 대해 실행하면 된다. 다음과 같은 5 x 5 상자(MAP)에 토마토가 있다고 가정하자.편의상(경계 조건을 신경쓰지 않기 위해) MAP의 주변은 -1로 만든다. 이제 모든 토마토를 queue에 담는다. 참고로 토마토 문제의 경우는 미로 탐색과는 달리 visit이 필요가 없다.상자.. 2021. 3. 16.
BOJ 6588 : 골드바흐의 추측 알고리즘 문제 전체 링크 www.acmicpc.net/problem/6588 어떤 숫자가 소수의 합으로 이루어져 있는지 판단해야 한다. 매번 소수 판단 함수를 사용하면, 비용이 많이 들어 time out이 나기 때문에, 주어진 n = 1000000이하의 수에 대해 모두 소수인지 미리 구해둔다. 즉, 에라토스테네스의 체를 이용하여 소수를 먼저 만든다. 그리고 primeNumber에는 prime을 check하여 실제 소수 값을 순서대로 적어둔다. 주어진 요구사항은, n을 만들 수 있는 방법 중 b - a가 가장 큰 값을 출력해야 하므로, 가장 작은 소수 2, 즉 primeNumber[st = 0]부터 시작하면서 n - primeNumber[st]가 소수인지 판단한다. primeNumber[st]가 소수이고 .. 2021. 3. 16.
BOJ 1406 : 에디터 알고리즘 문제 전체 링크 www.acmicpc.net/problem/1406 참고 - BOJ 5397 : 키로거 stack을 2개 이용하면 에디터의 문자열을 쉽게 관리할 수 있다. 먼저 초반에 abcd가 입력되었다고 하자. 커서는 바로 d의 옆에 존재한다. (sp1 = 4) → abcd| 이제 P e 명령어에 의해 e가 추가되었다고 하자. stack1의 크기를 늘려주면서 e를 넣어주면 된다. (sp1 = 5) stack1[sp1++] = 'e'; → abcde| 이제 L 명령어에 의해 왼쪽으로 옮긴다고 하자. 왼쪽으로 옮기는 것은, 문자열은 여전히 abcde 이지만 커서는 d 뒤에 위치하게 된다. 따라서 커서의 뒷부분을 stack2로 옮겨준다. (sp1 = 4, sp2 = 1) stack에서 가장 나중에.. 2021. 3. 15.
반응형

티스토리툴바