본문 바로가기

파이썬

 (320)
[Python] 18126번 너구리 구구 https://www.acmicpc.net/problem/18126 18126번: 너구리 구구 텔레토비 동산에 사는 너구리 구구는 입구, 거실, 주방, 안방, 공부방, 운동실, 음악실, 음식 창고 등 N개의 방을 가지고 있다. 입구를 포함한 모든 방은 1부터 N까지의 번호가 있고, 입구는 1번이 www.acmicpc.net 22/09/19 그룹원들과 푼 그룹 주간 문제로 이 문제를 선택해서 풀었다. 오랜만에 DFS문제, 그것도 일반적인 matrix모양으로 간선이 주어지는 것이 아닌 실제 간선 모양으로 주어지는 그래프라서 조금 헷갈리긴 했지만 더듬더듬 기억을 되살려 가며 주석을 달아가며 작성했던 문제이다. 문제 접근 방식: 처음에는 이 문제를 재귀 오류로 틀렸었다. (재귀 제한 코드를 실수로 적지 못했다...
[Python] 16588번 Substring Permutation https://www.acmicpc.net/problem/16588 16588번: Substring Permutation Given two strings S and P, there are several ways to find whether P appears as a substring of S. The simplest one would be directly checking whether P is equal to any substring of S. As there can be O(|S|) substring of S of length |P|, this approach has O( www.acmicpc.net 22/09/19 전형적인 문제 해석이 어려운 문제로, 실제 난이도는 그다지 어렵지는 않은 문제이다. 문..
[Python] 1932번 정수 삼각형 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 22/09/18 전형적인 DP문제로, 이것과 비슷하게 어떤 행렬을 주고 내려오면서 DP를 계속 갱신하는 유형의 문제로는 스티커, 내려가기 2 등이 있다. 문제 접근 방식: 내려가면서 DP리스트를 갱신해주는데, DP[i]는 n번째 줄(n개의 숫자가 있음)에서 i번째 숫자에 도착했을 때, 경로의 최댓값이다. 나는 2차원 배열을 선언하는 대신에 DP리스트를 매 반복문마다 갱신해줌으로써 문제를 해결하였다. 아래로 떨어질 때, DP[0]은 제일 왼쪽에 있는 원소에서 내려가야만 ..
[Python] 25625번 샤틀버스 https://www.acmicpc.net/problem/25625 25625번: 샤틀버스 3년만에 열리는 대면 SNUPC를 위해서, 민준이는 제2공학관으로 가고자 한다! 제2공학관에 가는 버스는 여러 가지가 있다. 관악02, 5511, 5513, 5516... 어떤 버스를 타더라도 단점이 있는데, 그것은 바로 www.acmicpc.net 22/09/18 스트릭 채우려고 빠르게 풀었던 문제로 문제 포장이 좀 길어서 읽기 귀찮았던 문제였다. 문제 접근 방식: 처음 주어지는 숫자는 버스가 공학관에서 입구역까지 또는 입구역에서 공학관까지 이동하는 시간이고, 두 번째로 주어지는 숫자는 버스가 공학관으로 도착 예정인 시간을 의미한다. 민준이는 현재 입구역에 있다. 만약에 처음 주어지는 숫자가 두번째 주어지는 숫자..
[Python] 3135번 라디오 https://www.acmicpc.net/problem/3135 3135번: 라디오 첫 줄엔 정수 A와 B가 주어진다 (1 ≤ A, B < 1000, A ≠ B). 다음 줄엔 정수 N이 주어진다 (1 ≤ N ≤ 5). 다음 N개의 줄엔 미리 지정되어 있는 주파수가 주어진다 (주파수는 1000 보다 작다). www.acmicpc.net 22/09/17 단순하게 생각하면 쉽게 풀리는 문제로, 티어를 끈다면 조금 당황할 수도 있을 문제라고 생각한다. 문제 접근 방식: 내가 왜 당황할 수도 있는 문제라고 이야기했냐면, 이 문제는 그리디적 사고를 해야 풀리는 문제이기 때문이다. 버튼을 누르는 방법은 3가지가 있다. 주파수를 하나 올리거나, 내리거나, 즐겨찾기가 돼있는 주파수로 이동하거나. 당연히 최대한 적게 버..
[Python] 2407번 조합 https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 22/09/17 이 문제는 파이썬의 강점을 제대로 보여주는 문제로, 다른 언어에 비해서 큰 수 연산이 뛰어나고 지원하는 함수가 많다는 장점을 매우 잘 살릴 수 있는 문제다. 문제 접근 방식: 여러 방식으로 풀 수 있지만, 나는 문제에서 의도하는 바 대로 풀고자 했다. 사실 제일 간단한 풀이는 파이썬의 math 모듈에서 지원하는 factorial함수를 사용하여 combination의 정의를 사용해 문제를 푸는 것이다. 나 같은 경우는 문제에서 원하는 바 대로, 파스칼의 삼각형을 이용하여 DP문제로 풀었다. nCm ..
[Python] 11660번 구간 합 구하기 5 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 22/09/17 이전에 누적 합 문제를 풀어 본 적이 있었는데, 그때를 경험 삼아서 이 문제도 풀 수 있을 것 같아 풀게 된 문제다. 전형적인 누적 합, DP문제이다. 문제 접근 방식: 표의 크기가 주어지고(N = ~1024) 쿼리의 크기가 10만까지 주어지는데, 한 쿼리 마다 표의 연산을 전부 처리한다는 극단적인 케이스를 가정한다면, 1024*1024*..
[Python] 1417번 국회의원 선거 https://www.acmicpc.net/problem/1417 1417번: 국회의원 선거 첫째 줄에 후보의 수 N이 주어진다. 둘째 줄부터 차례대로 기호 1번을 찍으려고 하는 사람의 수, 기호 2번을 찍으려고 하는 수, 이렇게 총 N개의 줄에 걸쳐 입력이 들어온다. N은 50보다 작거나 같 www.acmicpc.net 22/09/17 실버 5를 순서대로 밀던 도중에 만난 문제로, 그다지 어렵지는 않았던 문제였다. 한번 틀리긴 했으나, 단순한 문제 읽고 구현하는 문제로, 쉽게 생각하면 되는 문제였다. 문제 접근 방식: 문제 주인공인 다솜이는 사람들을 매수해서 국회의원에 당선이 되게끔 하려 한다. 당선 조건은 다른 모든 후보들보다 많은 투표수를 가지는 것. 이때 매수하는 최소의 사람을 구하는 것이다. 나..

티스토리툴바