본문 바로가기

코딩공부66

(c++) DFS 2644번: 촌수계산 https://www.acmicpc.net/problem/2644 문제 개요 dfs(깊이 우선 탐색) 응용 문제 내 방식대로 풀었기에 다른 사람과 약간 다를 수 있다. 부모가 하나로 고정되어있는 트리 형태의 문제로, 주어진 두 사람에 대해서 촌수를 계산하면 된다. 아이디어는 아래와 같다. 기존 트리 구조처럼 위에서 아래로 내려오는 구조로 만들게 되면 입력에서 주어진 사람들 찾는데 어려움이 있다.그래서 반대로 자식을 트리의 윗부분으로 오게 하고, 아랫 부분에 부모 하나를 넣어두었다. 첫 번째 사람에 대해서 루트 노드까지 각 촌수를 저장하여 올라간다.여기서 부모 노드 중 두 번째 사람이 있다면 멈추고 정답을 출력한다. 두 번째 사람에 대해서 부모 노드로 올라가면서 똑같이 촌수를 저장하되,촌수가 이미 기.. 2025. 9. 12.
(c++) 동적계획법 2482번: 색상환 https://www.acmicpc.net/problem/2482 2482번: 색상환 첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 개요 원형일 경우에 동적계획법을 사용하는 문제이다. 문제에 대한 점화식을 만든다면 쉽게 풀 수 있는 문제이다. (이게 가장 어렵다.) 메모이제이션은 n = 색깔의 개수, k = 선택 개수라고 할 때의 경우의 수를 저장하면 되고, 색깔의 개수인 n에 대해서 n을 선택한 경우 + n을 선택하지 않는 경우로 점화식을 만든다. $$ d[n][k] = d[n-1][k] + d[n-2][k-1] $$ 문제가 원형으로 주어질 .. 2024. 2. 7.
(c++) 2098번: 외판원 순회 비트마스크 https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 문제 개요 유명한 문제인 외판원 순회는 다익스트라 알고리즘에서 많이 등장했던 문제이다. 해당 문제의 취지는 비트마스크와 동적계획법을 사용하여 해결하는 방법으로 푸는 것이다. 비트마스크는 해당 도시의 방문 여부를 파악하는 용도로 사용하면 된다. 문제의 테스트케이스는 무조건 순회하는 방법으로 나오기에 순회가 안 되는 상황은 고려하지 않아도 된다. 그리고 첫 번째 .. 2024. 2. 1.
(c++) 비트마스크(bitmask) 정리 비트마스크(bitmask) 0, 1로 이루어진 이진수를 자료 구조 형태로 사용하는 기법을 비트마스크라 한다. 비트 연산자를 이용한다면 일반 계산보다 빠른 연산이 가능하다. AND, OR, XOR로 특정 비트를 변경, 삭제, 추가가 가능하고, 쉬프트 연산을 통해서 곱셈, 나눗셈을 빠르게 연산가능하다. 정수 a, b를 AND 연산 a & b 정수 a, b를 OR 연산 a | b 정수 a, b를 XOR 연산 a ^ b 정수 a를 NOT 연산 ~a 정수 a를 왼쪽으로 b비트 시프트 a > b 비트마스크는 집합에 사용되는 경우가 많은데 {1, 2, 4} 배열일 경우 $$ 2^{1} + 2^{2} + 2^{4} = 1\;0110 $$ 원소 i는 2 ^ i 번째 비트가 1로 되어있다는 것으로 사용한다. 집합에서 사용.. 2024. 1. 30.
(c++) 동적계획법 BOJ 2293번: 동전 1 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 개요 주어진 K에 대해서 동전 조합으로 만들 수 있는 경우의 수를 계산하는 코드이다. 동전 조합이 1, 2가 있다면 동전 1를 이용해서 만들 수 있는 조합은 1 = (1) 1가지 2 = (1, 1) 1가지 3 = (1, 1, 1) 1가지 동전 2를 이용해서 만들 수 있는 조합은 1 = 없음 2 = (2) 1가지 3 = 1원을 사용해서 (2, 1)만 가능 여기서 3은 3에서 2를 뺀 1원을 동전.. 2024. 1. 25.
(c++) 동적계획법 7579번: 앱 https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 문제 개요 배낭 문제는 메모이제이션을 [물품의 용량] [물품의 개수] = 물건의 가치 위와 같이 사용했지만, 이 문제를 보면 주어지는 M의 용량은 10,000,000 이다. 배낭 문제와 비슷한 방법으로 푼다면 cache[10,000,000][100] 이라는 말도 안되는 배열을 사용하게 된다. 그래서 반대로 비교적 최대 값이 10,000인 비활성화 결과를 메모이제이션으로 사용할 것이다. cache[비활성화.. 2024. 1. 24.

티스토리툴바