본문 바로가기

알고리즘/백준 문제 풀이

 (338)
[Python] 25576번 찾았다 악질 https://www.acmicpc.net/problem/25576 25576번: 찾았다 악질 구수한 욕설과 귀여운 동남권 사투리가 매력인 인기 스트리머 랄파는 오늘도 열심히 게임 방송을 한다. 랄파는 과거 게임 최상위 랭커를 달성했던 빛나는 시절이 있었으나, 현재는 실력이 많이 www.acmicpc.net 22/09/21 전형적인 문제 잘 읽고 구현하면 되는 문제로, 그렇게 어렵지는 않다. 문제 접근 방식: 문제 요약하자면, 어떤 시청자가 악질인지 악질이 아닌지 판단하는 문제이다. 첫 번째 줄에는 어떤 시청자가 구독한 스트리머의 명수와 그 스트리머들의 시청자 수 변화 리스트의 길이가 주어진다. 이후 두 번째 줄에서는 랄파의 시청자 수의 변화가 주어지고, 나머지 줄에서는 각 스트리머의 시청자 수의 변화가..
[Python] 10216번 Count Circle Groups https://www.acmicpc.net/problem/10216 10216번: Count Circle Groups 백준이는 국방의 의무를 수행하기 위해 떠났다. 혹독한 훈련을 무사히 마치고 나서, 정말 잘 생겼고 코딩도 잘하는 백준은 그 특기를 살려 적군의 진영을 수학적으로 분석하는 일을 맡게 되었 www.acmicpc.net 22/09/20 전형적인 분리 집합 문제로, 분리 집합에 대한 내용만 잘 알고 있다면 쉽게 풀 수 있는 문제이다. 만약 분리집합을 모른다면 조금 푸는데 힘들 것이다. 문제 접근 방식: 문제에서는 통신영역이 서로 닿거나 겹치면 통신이 가능하다고 보는데, 여러 다리를 거쳐서 통신이 되는 것도 통신이 가능하다고 간주하였다. 때문에 이 정보를 보고 바로 분리 집합에 관련된 문제이겠구나..
[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 ..

티스토리툴바