Problem Solving13 백준 10897번 - Inherited disease(C++) 문제백준, 골드 5, https://www.acmicpc.net/problem/10897풀이 날짜: 2025.4.9.풀이 시간: 2시간 가량알고리즘 분류: 수학, 구현, 트리사용 언어: C++문제 해설d번째 세대의 인원 수는 d!이며 세대 d ≤ 100이므로, 트리를 직접 만들어서는 해결할 수 없다.따라서 수학적으로 해결해야 한다.몇 번의 실험 후, 다음과 같이 식을 세웠다.l 세대 c번째 자손의 번호 F(l, c)는F(l, c) = [1번째부터 (l-1)세대까지 정민의 수] + [(l-1) 세대에서 ‘현재 선택된 부모’의 손위 형제의 수] * l + c와 같이 정의할 수 있다.(다만, F는 이전 입력에 따라 바뀌므로 엄밀히 말하면 함수라고 할 수는 없다.)예를 들어, 예제 입력에서31 2 1출력은 0번.. 2025. 4. 9. 백준 1206번 - 사람의 수(C++) 문제백준, 골드 5, https://www.acmicpc.net/problem/1206알고리즘 분류: 사용 언어: C++문제 해설해당 문제는 처음에 떠올린 해결 방법이 잘못된 경우였다. 그 때문에 고생하기도 했고, 예상했던 부동소수점의 오차 문제에 대해서도 많이 고민하게 한 문제라고 할 수 있다. 하나의 접근 방법을 떠올리고 나서 이를 검증하는 과정이 중요하다는 것을 알 수 있었다.초기 시도: 최소 공배수로 접근하자(실패)처음에는 각 문항별로 필요한 최소 사람의 숫자를 구한 후, 이들 사이에 최소 공배수를 구하는 식으로 접근하였다.계산 시 floating point로 접근하면 정확하게 숫자가 구해지지 않으므로 Fixed Point 자료구조를 직접 구현하도록 했다.그러나 최소 공배수로 구하면 정확히 값이 .. 2025. 4. 3. 백준 28116번 - 선택 정렬의 이동 거리 문제백준, 실버 3, https://www.acmicpc.net/problem/28116풀이 날짜: 2025.3.22풀이 시간: 19:48~19:55, 21:45~21:56(총 18분)알고리즘 분류: 구현, 정렬사용 언어: C++문제 해설선택 정렬에서 각 수의 이동 거리를 계산하는 문제.n의 크기를 보면 최대 500000이므로, O(n^2)의 알고리즘으로는 해결할 수 없다.그러나 중요한 것은 수를 직접 정렬하는 것이 아니기 때문에 O(n^2)보다 더 빨리 해결할 방법이 있다는 것이다.실제로는 선택 정렬에서 수의 교환 횟수는 (n-1)번이다. 선택 정렬에서 가장 시간이 오래 걸리는 작업은 수의 위치를 파악하는 것으로 매 iteration마다 최대 n번의 비교 연산이 필요하다. 이 비교 연산의 횟수를 낮출 .. 2025. 3. 22. 백준 13460번 - 구슬 탈출 2 1. 문제백준, 골드 1, https://www.acmicpc.net/problem/13460풀이 날짜: 2025.3.21.풀이 시간: 10:52~12:24(1시간 32분)알고리즘 분류: 구현, 그래프 탐색, 시뮬레이션, 너비 우선 탐색(BFS)사용 언어: C++2. 문제 해설상, 하, 좌, 우로 이동시킨다는 것은, 위쪽, 아랫쪽, 왼쪽, 오른쪽으로 옮겼을 때에 대한 가능성 트리 노드를 순회하는 것과 같다고 생각할 수 있다.그러면 해당 문제는 이동횟수를 최소화하는 최단 경로 그래프 탐색 문제로 생각할 수 있으므로, 간선의 개수가 이동 횟수인 지금은 BFS를 통해서 탐색하면 된다.탐색할 수 있는 경우의 수는 4가지이고 깊이는 최대 10이므로(10회보다 더 이동할 경우 탐색하지 않음), 경우의 수는 $4^{.. 2025. 3. 21. 백준 11444번 - 피보나치 수 6(C++) 문제백준, 골드, https://www.acmicpc.net/problem/11444풀이 날짜: 2025.3.17.풀이 시간: 총 3시간 51분사용 언어: C++문제 해설수학을 이용한 문제로, 공식을 모르면 풀 수 없다. 여기서는 도가뉴 항등식을 이용하여야 하며, 이를 활용하여 분할정복을 사용하여야 시간복잡도를 최적화할 수 있다.내가 구했던 식 중 하나가 바로 도가뉴 항등식의 특수해로, $a_{2n}$에 대한 식까지는 어떻게든 유도했는데 그다음으로 넘어가는 데에 실패하여 다른 글을 찾아보게 되었다.도가뉴 항등식은 피보나치 등식을 활용하여 변형한 것인데, 도가뉴 항등식은$$ a_{m+n}=a_{m-1}a_n+a_m a_{n+1} $$을 말한다(단, $a_n$은 피보나치 수열의 n번째 수).도가뉴 항등식과.. 2025. 3. 18. 백준 9328번 - 열쇠(C++) 풀이 정리 개요백준, 골드 1, https://www.acmicpc.net/problem/9328풀이 날짜: 2025.2.26.풀이 시간: 10:16~11:37(1시간 21분)알고리즘 분류: 구현, 그래프 탐색 문제사용 언어: C++문제 해설해당 문제는 단순히 그래프 탐색을 구현하는 문제이다.다만 여기서 조사 조건이 여러 개 걸리면서, 따져야 할 상황이 많아지고 있다.나는 탐색하는 방식을 다음과 같이 결정했다.모든 테두리에 대해 *이 아닌 곳은 통과가 가능하다.우선, 탐색할 수 있는 곳을 모두 탐색한다.탐색하는 과정에서 모든 문은 열 수 있으면 열고, 아니면 위치를 저장해 놓는다.탐색 과정에서 $가 나올 때마다 document 개수를 증가시킨다.탐색을 완료한 후, 열리지 않은 문을 조사한다.열리지 않는 문은 다시 .. 2025. 2. 26. 백준 2075번 - N번째 큰 수: 약간 더 빠른 코드 문제백준, 실버 3, https://www.acmicpc.net/problem/2075풀이 날짜: 2025.2.4.풀이 시간: 11:03~11:29(26분)알고리즘 분류: 정렬, 우선순위 큐사용 언어: C++문제 해설해당 문제는 상위 N번째 값을 구하는 문제이지만 두 가지 특징이 있다.메모리 제한이 걸려 있다. 12MB의 제한이 있다.모든 수는 자신의 한 칸 위의 수보다 더 크다.첫 번째 특징을 생각해보면, 해당 문제는 NN (1≤N≤1500)의 보드가 주어지고 각 값의 절댓값이 10억보다 낮으므로 자료를 모두 저장하는 데에 최소 1,5001,5004Byte=2,250,0004Byte = 9,000,000Byte, 즉 약 9MB의 메모리가 필요하다.이것만 해도 메모리 제한이 아슬아슬하므로, 만약 정렬을 .. 2025. 2. 4. 백준 1311번 - 할 일 정하기 1 문제백준, 골드 1, https://www.acmicpc.net/problem/1311풀이 날짜: 2025.1.29.풀이 시간: 15:17~16:30, 안 돼서 GPT 킴, 17:28에 DFS 방식으로 해결(총 2시간 11분)알고리즘 분류: 비트필드를 이용한 다이나믹 프로그래밍사용 언어: C++문제 해설해당 문제는 비트필드를 이용한 다이나믹 프로그래밍을 활용하는 문제이다.문제의 정답을 탐색할 때 탐욕법이나 다른 방법을 사용할 수 없으므로, 완전 탐색으로 모든 경우의 수를 측정해야 한다. 그런데 4명의 사람이 순차적으로 1-2-3-4번 일을 맡는 경우와 2-1-3-4번 일을 맡는 경우, 뒤의 3-4번 일의 비용을 계산할 땐 중복 계산이 발생하게 된다.이러한 중복 계산을 피하려면 상태를 저장하는 비트필드 기.. 2025. 1. 29. 백준 1562번 - 계단 수 풀이(C++) 1562번-계단 수문제백준, 골드 1, https://www.acmicpc.net/problem/1562풀이 날짜: 2025.1.28.풀이 시간: 약 2시간알고리즘 분류: 다이나믹 프로그래밍, 비트마스킹, 비트필드를 이용한 다이나믹 프로그래밍사용 언어: C++문제 해설‘1562 계단 수’는 비트필드를 이용한 다이나믹 프로그래밍을 필요로 하는 문제로, 해당 알고리즘을 활용하는 문제 중 가장 기초적인 문제이다.‘2098 외판원 순회’ 문제가 해결되지 않아 시도해보았는데, 난이도는 더 쉽지만 개념을 안다면 꽤 간단하게 해결할 수 있는 문제였다.비트필드를 이용한 다이나믹 프로그래밍은 ‘현재 상태’를 필요로 하는 문제에 유용하게 사용된다. 일반적인 다이나믹 프로그래밍에서는 정점 번호에 대한 정보나, 문자열의 인덱.. 2025. 1. 28. 이전 1 2 다음
