본문 바로가기

알고리즘/백준 문제 풀이

 (338)
[Python] 9343번 랜덤 걷기 https://www.acmicpc.net/problem/9343 9343번: 랜덤 걷기 각 테스트 케이스 마다 음수 좌표를 방문하지 않고 시작점으로 도아오는 랜덤 걷기의 경로의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 23/12/07 누가 봐도 그냥 카탈란 수 문제다. 문제 접근 방식: 누가 봐도 그냥 카탈란 수 문제인데, 이건 제한이 크기 때문에 카탈란 수의 점화식으로 구현하면 안된다. 일반항으로 접근해야 되는데, 모듈로 역원을 활용하여 구현할 수 있다. 파이썬은 모듈로 역원을 pow함수를 통해 쉽게 구할 수 있으니 이를 잘 활용해 보자. 카탈란 수의 일반항은 다음과 같다. $$C_n = \frac{1}{n+1} \binom{2n}{n}$$ 아래는 내가 위..
[Python] 21739번 펭귄 네비게이터 https://www.acmicpc.net/problem/21739 21739번: 펭귄 네비게이터 펭귄은 현재 ($1$, $1$)에 있다. 펭귄은 집까지 가고 싶다. 펭귄의 집은 ($2$, $N$)이다. 하지만 누군가에 의해 얼음길이 다 깨져 집에 갈 수 없게 되었다. 현진이는 펭귄들을 위해 얼음길을 만들어줄 www.acmicpc.net 23/12/06 이것도 카탈란 수임을 알면 매우 쉬운 문제이다. 문제 접근 방식: 이 문제는 카탈란 수 임을 알아내는게 조금 까다롭다. 영 타블로를 잘 알고 있는 사람이라면 이 그림이 $2 \times n$짜리 영 타블로의 개수이고, 이를 계산하면 카탈란 수라는 사실을 알 수 있다. 근데 이건 좀 더 나아간 설명이고, 그림을 살펴보면, "항상" 윗 줄보다 밑 줄의 원소가..
[Python] 30924번 A+B - 10 (제2편) https://www.acmicpc.net/problem/30924 30924번: A+B - 10 (제2편) 1 이상 10,000 이하의 정수 A, B에 대해 A+B의 값을 출력해야 한다. 단, 이 문제는 인터랙티브 (상호작용) 문제이다. 이 문제에서는 A와 B의 값이 바로 주어지지 않고, 채점기와의 상호작용을 통해 그 www.acmicpc.net 23/12/19 무작위화 알고리즘을 사용하는 아주 좋은 문제여서, 소개해보고자 한다. 문제 접근 방식: 문제는 아주 간단하다. 이 문제에서는 총 $19,997$번의 질의를 할 수 있으며, 가능한 $A$와 $B$의 범위는 $1$부터 $10,000$까지이기 때문에 확정적으로 $A$와 $B$를 결정짓기 위해서는 $19,998$번의 질의가 필요하다. 왜냐하면, $A$..
[Python] 1670번 정상 회담 2 / 17268번 미팅의 저주 https://www.acmicpc.net/problem/1670 1670번: 정상 회담 2 첫째 줄에 정상 회담에 참가한 사람의 수 N이 주어진다. 이 값은 10,000보다 작거나 같은 짝수이다. www.acmicpc.net https://www.acmicpc.net/problem/17268 17268번: 미팅의 저주 인하대 컴퓨터 공학과에 재학 중인 이산이는 오랜만에 미팅을 나가 볼까 한다. 미팅은 N명이 원탁에 앉아서 진행된다고 한다. 질투가 난 이산이 친구 명기는 X의 저주를 걸었다. 그 저주는 N명이 www.acmicpc.net 23/12/06 카탈란 수 문제다. 두 문제는 완전히 동일한 문제이기 때문에 같이 올린다. 문제 접근 방식: 예제 출력 보고 카탈란 수 임을 인지한 뒤, 카탈란 수를 출..
[Python] 18132번 내 이진트리를 돌려줘!!! https://www.acmicpc.net/problem/18132 18132번: 내 이진트리를 돌려줘!!! 각 테스트 케이스에 대해 이진 트리의 경우의 수를 1,000,000,007로 나눈 나머지를 출력하시오. www.acmicpc.net 23/12/06 이것도 유명한 카탈란 수의 유형 중 하나이다. 문제 접근 방식: 먼저 문제의 출력을 보자. 익숙한 숫자들이 보일 텐데, 여기서 카탈란 수임을 예측하고 구현하면 맞았습니다를 받을 수 있다. 그러면 이 문제의 점화식이 왜 카탈란 수가 나오는지 생각해보자. 우리는 이진트리가 주어진다면, 그 이진트리의 왼쪽에 있는 부분과 오른쪽에 있는 부분으로 트리를 "분리"하여 생각할 수 있다. $N$개의 간선이 주어져 있을 때 만들 수 있는 트리의 경우의 수를 $C_n$..
[Python] 4099번 Skyline https://www.acmicpc.net/problem/4099 4099번: Skyline There will be several test cases in the input. Each test case will consist of a single line containing a single integer N (3 ≤ N ≤ 1,000), which represents the number of skyscrapers. The heights of the skyscrapers are assumed to be 1, 2, 3, …, N. The www.acmicpc.net 23/12/06 카탈란 수 임을 파악하면 쉽게 해결할 수 있는 문제이다. 문제 접근 방식: 먼저 문제의 입출력 예시를 보자. 어? $3$일때 ..
[Python] 3462번 이진 스털링 수 https://www.acmicpc.net/problem/3462 3462번: 이진 스털링 수 n명을 m개의 그룹으로 나누는 방법의 수를 제 2종 스털링 수(Stirling numbers of the second kind)라고 하고, S(n,m)으로 표현한다. S(n,k)는 크기가 n인 집합을 k개의 공집합이 아닌 부분집합으로 나누는 방법 www.acmicpc.net 23/11/29 학교 알고리즘 수업을 대비하기 위한 그룹에서 조합론 문제로 추천받아서 풀게 된 문제다. 규칙을 찾아서 풀기는 쉬운 난이도에 속하지만 증명이 좀 까다로운 편이라고 생각되어서 기존 난이도보다 한단계 높여서 난이도 기여를 했다. 문제 접근 방식: 문제에서 주어진 점화식을 활용하여 DP배열을 만들어 먼저 규칙을 찾아보기로 했다. $..
[Python] 28346번 XOR Necklace https://www.acmicpc.net/problem/28346 28346번: XOR Necklace Frograms, Inc. has been busy developing necklaces with brand-new design and feature. Every programmer working at Frograms now wears this necklace. A necklace consists of multiple beads stringed by a thread, as seen below. Each bead is given a number betwee www.acmicpc.net 23/11/28 비트 연산의 성질을 이용한 애드혹 문제이다. 다른 방법으로는 제한 시간이 널널하기 때문에 3차원 DP로..

티스토리툴바