본문 바로가기

파이썬

 (320)
[Python] 23309번 철도 공사 https://www.acmicpc.net/problem/23309 23309번: 철도 공사 첫 번째 줄에 공사를 시작하기 이전에 있는 역의 개수를 나타내는 양의 정수 $N$과 공사 횟수를 나타내는 양의 정수 $M$이 주어진다. ($1 \le N \le 500\,000$, $1 \le M \le 1\,500\,000$) 두 번째 줄에는 공사 www.acmicpc.net 24/02/13 파이썬으로 해결하기 정말 힘든 문제로, C++을 사용할 수 있는 사람이라면 웬만해서는 C++로 해결하기를 권장하는 문제다. 주어진 그대로 잘 구현을 했음에도 불구하고 여러 기술들을 활용해야만 시간 초과를 면할 수 있다. Python3로는 통과한 사람이 없는 것으로 보아, Pypy를 사용해야만 풀 수 있는 문제로 보인다. 문..
[Python] 14925번 목장 건설하기 https://www.acmicpc.net/problem/14925 14925번: 목장 건설하기 랜드 씨는 퇴직금으로 땅을 사서 목장을 지으려 한다. 그가 사려고 소개받은 땅은 직사각형이고 대부분 들판이지만, 여기저기에 베기 어려운 나무와 치울 수 없는 바위가 있다. 그는 목장을 하 www.acmicpc.net 24/01/29 2차원 DP문제로, 이전에 어떤 선배로부터 1915번 문제에 대한 풀이를 들은 적이 있었다.(물론 이 문제는 아직 해결하지 못한 상태다.) 그 접근 방법이 얼핏 생각이 나서 그 방식대로 접근을 했고, 맞았습니다를 받을 수 있었다. 문제 접근 방식: DP테이블을 다음과 같이 정의했다. $$DP[N][M] = N\textrm{행 }M\textrm{열을 오른쪽 아래 꼭짓점으로 가지는 정..
[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 이전에 실패 했던 문제를 다시 풀어보았다. 전형적인 투 포인터 문제이지만, 포인터를 움직이는 방향에 유의해서 문제를 해결해야만 했었다. 문제 접근 방식: 특정한 값이 주어져 있고, 그 값에 가장 가까운 두 수의 합을 만들 수 있는 모든 조합을 찾는 것이 문제의 목표이다. 투 포인터 문제임을 보자마자 파악했지만, 포인터를 움직이는 방향에 유의해야만 했다. 나는 두 가지 경우로 분리해서..

티스토리툴바