본문 바로가기

글

 (385)
[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를 순서대로 밀던 도중에 만난 문제로, 그다지 어렵지는 않았던 문제였다. 한번 틀리긴 했으나, 단순한 문제 읽고 구현하는 문제로, 쉽게 생각하면 되는 문제였다. 문제 접근 방식: 문제 주인공인 다솜이는 사람들을 매수해서 국회의원에 당선이 되게끔 하려 한다. 당선 조건은 다른 모든 후보들보다 많은 투표수를 가지는 것. 이때 매수하는 최소의 사람을 구하는 것이다. 나..
[Python] 1402번 아무래도이문제는A번난이도인것같다 https://www.acmicpc.net/problem/1402 1402번: 아무래도이문제는A번난이도인것같다 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 100)이 주어진다. 테스트 케이스마다 두 정수 A, B(-231 ≤ A, B ≤ 231-1)가 주어진다. www.acmicpc.net 22/09/16 이 문제는 풀고 나서 정말 감탄했던 문제이다. 아이디어가 기가 막히는 문제이다. 문제 접근 방식: 문제는 굉장히 짧고 간단하다. 어떤 정수 $A$가 있으면 그 숫자를 $A = a_1 * a_2 * a_3 * \cdots * a_n$으로 했을 때 $A' = a_1 + a_2 + a_3 + \cdots + a_n$이 성립하면 "$A$는 $A'$으로 변할 수 있다"라고 한다. ($a_i$는 정수) 만..

티스토리툴바