본문 바로가기

알고리즘/백준 문제 풀이

 (338)
[Python] 11688번 최소공배수 찾기 https://www.acmicpc.net/problem/11688 11688번: 최소공배수 찾기 세 정수 a, b, L이 주어졌을 때, LCM(a, b, c) = L을 만족하는 가장 작은 c를 찾는 프로그램을 작성하시오. LCM(a, b, c)는 a, b, c의 최소공배수이다. www.acmicpc.net 24/01/25 단순한 정수론 문제로, 소인수 분해 코드를 효율적으로 작성한다면 쉽게 풀 수 있는 문제이다. 문제 접근 방식: $a, b, L$의 값이 주어질 때, $\mathrm{lcm}(a, b, c) = L$을 만족시키는 가장 작은 $c$의 값을 구하는 것이 문제의 의도이다. $\mathrm{lcm}(a, b, c) = \mathrm{lcm}(\mathrm{lcm}(a, b), c)$가 성립하므..
[Python] 17504번 제리와 톰 2 https://www.acmicpc.net/problem/17504 17504번: 제리와 톰 2 $$ 1 - \cfrac{1}{2 + \cfrac{1}{7 + \cfrac{1}{1 + \cfrac{1}{8}}}} = 1 - \cfrac{1}{2 + \cfrac{1}{7 + \cfrac{8}{9}}} = 1 - \cfrac{1}{2 + \cfrac{9}{71}} = 1 - \cfrac{71}{151} = \cfrac{80}{151} $$ www.acmicpc.net 24/01/24 수학에 구현을 덧붙인 재미있는 문제다. 말로는 설명하기 힘들어 예시를 하나 직접 따라가 보면 쉽게 이해할 수 있다. 문제 접근 방식: 제리가 훔쳐간 치즈의 무게만 구하면 톰이 가지고 있는 치즈의 무게를 구할 수 있다. $a_1,..
[Python] 10407번 2 타워 https://www.acmicpc.net/problem/10407 10407번: 2 타워 2 타워의 높이 H는\[2^{2^{2^{\cdot^{\cdot^{\cdot 2}}}}}\]에서 숫자 2가 나타나는 횟수로 정의된다. 2 타워의 값은 해당 표현식의 값으로 정의된다. 예를 들어, 높이 1의 2 타워 값은 2이고, 높이 2의 2 타워 www.acmicpc.net 24/01/20 수학 문제로, 찍어서 맞출 수도 있으나 여기서는 증명을 소개하도록 하겠다. 문제 접근 방식: 결론만 이야기 하자면, $H = 1$일 때는 나머지가 $2$이고, 그 외에는 $1$이다. 일단 $H=1$일 때는 2타워의 값은 $2$이므로, $3$으로 나눈 나머지가 $2$이다. $2$를 짝수 번 곱하면 그 숫자를 $3$으로 나눈 나머지..
[Python] 1325번 효율적인 해킹 https://www.acmicpc.net/problem/1325 max_hacked: ans = [] ans.append(start) max_hacked = hacked elif hacked == max_hacked: ans.append(start) print(*ans) main()
[Python] 26260번 이가 빠진 이진 트리 https://www.acmicpc.net/problem/26260 26260번: 이가 빠진 이진 트리 김소마는 최근에 포화 이진 트리에 대해 배웠다. 포화 이진 트리란, 이진 트리에서 리프 노드를 제외한 모든 노드가 두 자식 노드를 가지며, 모든 리프 노드가 채워진 것을 말한다. 아래의 그림 www.acmicpc.net 24/02/16 업다운 랜디를 하다가 만난 문제로, 처음 보고 뇌 정지가 와서 잘 해결하지 못했던 문제다. 이후 다시 풀게 되었고, 생각보다 간단한 해결 방법이 있어 글을 쓴다. 문제 접근 방식: 문제의 요구 조건은, 포화 이진 트리이면서 이진 검색 트리인 트리가 주어졌을 때, 특정 부분을 제거하고 다시 새롭게 썼을 때 바뀌는 트리의 후위 순회 결과를 출력하는 것이다. 처음에 보고 정석..
[Python] 9024번 두 수의 합 https://www.acmicpc.net/problem/9024 9024번: 두 수의 합 프로그램은 표준입력으로 입력을 받는다. 프로그램 입력은 t 개의 테스트 케이스로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 정수 t 가 주어진다. 두 번째 줄부터 두 줄 www.acmicpc.net 24/02/12 이전에 실패 했던 문제를 다시 풀어보았다. 전형적인 투 포인터 문제이지만, 포인터를 움직이는 방향에 유의해서 문제를 해결해야만 했었다. 문제 접근 방식: 특정한 값이 주어져 있고, 그 값에 가장 가까운 두 수의 합을 만들 수 있는 모든 조합을 찾는 것이 문제의 목표이다. 투 포인터 문제임을 보자마자 파악했지만, 포인터를 움직이는 방향에 유의해야만 했다. 나는 두 가지 경우로 분리해서..
[Python] 23325번 마법천자문 https://www.acmicpc.net/problem/23325 23325번: 마법천자문 최근最近 만화漫畫 마법천자문魔法千字文을 감명感銘 깊게 읽은 연두然斗는, 모든 수數를 한자漢字로 적기 시작始作했다. 그런데 수업授業을 들으면서 필기筆記 해놓은 내용內容을 복습復習 www.acmicpc.net 24/02/08 업 다운 랜디를 하다 만난 문제로, 처음에 어떤 알고리즘을 적용해야 할 지 몰라 많이 헤맸던 문제다. 문제 접근 방식: 처음에 접근했던 방식은 무지성 dfs였다. 열심히 짰지만 당연히 시간초과가 났다. 태그를 까고 곧바로 어떻게 풀지 알아버렸는데, 태그는 DP였다. 상태 식은 다음과 같이 정의된다. $$DP[i] = i\textrm{번째 문자까지 보았을 때 해석할 수 있는 가장 큰 계산 결과}$..
[Python] 25512번 트리를 간단하게 색칠하는 최소 비용 https://www.acmicpc.net/problem/25512 25512번: 트리를 간단하게 색칠하는 최소 비용 0번 정점을 black, 1번 정점을 white, 2번 정점을 white, 3번 정점을 black, 4번 정점을 black, 5번 정점을 black, 6번 정점을 black, 7번 정점을 white로 색칠하는 비용 310이 정답이다. www.acmicpc.net 24/02/08 간단한 그래프 탐색 문제로, 트리의 성질을 이용한 교육적인 좋은 문제다. 문제 접근 방식: 트리를 색칠할 수 있는 최소 비용을 문제에서는 요구하고 있고, 인접한 노드마다 항상 다른 색깔로 칠해야 한다는 제약 조건이 걸려있다. 요지는, 트리는 이분 그래프라는 점이다. 트리는 이분 그래프이기 때문에, 루트를 중심으로 ..

티스토리툴바