본문 바로가기

알고리즘/백준 문제 풀이

 (338)
[Python] 16895번 님 게임 3 / 7685번 Nim https://www.acmicpc.net/problem/16895 16895번: 님 게임 3 구사과와 큐브러버가 님 게임을 하고 있다. 님 게임은 돌을 위로 쌓아올린 돌 더미 k개를 이용한다. 각각의 돌 더미에는 한 개 이상의 돌이 있다. 두 사람은 서로 턴을 번갈아가면서 님 게임을 진 www.acmicpc.net https://www.acmicpc.net/problem/7685 7685번: Nim The input test file will contain multiple test cases, each of which begins with a line indicating the number of piles, 1 ≤ n ≤ 1000. On the next line, there are n positive ..
[Python] 13034번 다각형 게임 / 16187번 Game on Plane https://www.acmicpc.net/problem/13034 13034번: 다각형 게임 N개의 꼭짓점으로 이루어진 볼록 다각형이 있다. 다각형의 내각은 모두 180보다 작다. 꼭짓점은 1부터 N번까지 시계 방향으로 번호가 매겨져 있다. 성관이와 홍준이는 다각형에서 게임을 하려고 www.acmicpc.net https://www.acmicpc.net/problem/16187 16187번: Game on Plane You are given $N$ points on a plane. These points are precisely the set of vertices of some regular $N$-gon. Koosaga, an extreme villain, is challenging you with ..
[Python] 3986번 좋은 단어 https://www.acmicpc.net/problem/3986 3986번: 좋은 단어 이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 www.acmicpc.net 22/10/09 스택을 이용해서 푸는 문제로, 괄호 문자열 문제를 풀었다면 응용해서 풀 수 있는 문제이다.(유사한 유형임) 문제 접근 방식: 괄호 문자열이 옳은지 그른지 판단하는 문제와 동일하지만, 차이점은 괄호 문자열은 시작과 끝이 정해져 있지만 이 문제 같은 경우는 시작과 끝이 괄호 문자열처럼 명확하지 않다는 것이다. 나는 괄호 문자열의 풀이에서 힌트를 얻어, 스택에 문자들을 계속 쌓다가 현재 문자가 스..
[Python] 14496번 그대, 그머가 되어 https://www.acmicpc.net/problem/14496 14496번: 그대, 그머가 되어 첫째 줄에 머호가 바꾸려 하는 문자 a와 b가 주어진다. 둘째 줄에 전체 문자의 수 N과 치환 가능한 문자쌍의 수 M이 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ M ≤ 10,000) 이후 M개의 줄에 걸쳐 치환 가능한 문 www.acmicpc.net 22/10/08 단순 BFS문제이다. 문제 접근 방식: 이 문제에서 요구하는 바는 a를 b로 바꾸기 위해 필요한 최소 치환 횟수이다. 결국 어느 정점에서 다른 한 정점으로 가는 최소 거리를 구하는 문제와 별 다를 바가 없으므로, BFS로 해결할 수 있다. 구현하는데 주의할 점은 행렬과 같이 주어진 그래프와는 다르게 실제 간선으로 그래프가 주어져서, 그 ..
[Python] 4172번 sqrt log sin https://www.acmicpc.net/problem/4172 4172번: sqrt log sin 입력은 여러 개의 테스트 케이스로 이루어져 있으며, 한 줄에 하나씩 주어진다. 각 줄에는 \(i\)가 주어지며, 이 수는 0보다 작지 않고, 백만보다 크지 않다. 입력의 마지막 줄에는 -1이 주어지며, www.acmicpc.net 22/10/08 DP라고 보기에도 조금 민망할 정도로, 이미 점화식을 문제에서 다 주었다. 이를 메모이제이션 기법을 활용하여 단순 구현만 하면 되는 문제이다. 문제 접근 방식: 처음에는 입력마다 DP값을 구해주도록 했는데, 시간초과가 났다. 그래서 입력 전에 미리 DP값을 다 구해주고(전처리 과정), 입력 할 때마다 그 값을 출력하도록 바꿔주었다. 구현은 math모듈의 floo..
[Python] 4375번 1 https://www.acmicpc.net/problem/4375 4375번: 1 2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오. www.acmicpc.net 22/10/08 처음에는 특별한 규칙이 있는 문제인 줄 알고 괜히 시간을 오래 썼었다. 알고 보니 그냥 단순한 브루트 포스라는 것을 알고 그냥 깡 구현하여 문제를 풀었다. 문제 접근 방식: 어떤 정수가 주어지면, 그에 맞춰서 가장 작은 1로만 구성된 그 정수의 배수의 자릿수를 출력하는 것이 우리의 목표이다. 때문에 파이썬의 큰 수 연산에 대한 장점을 살려서 10을 곱하고 1을 하는 연산을 반복하다 입력받은 N으로 나눠질 때, 그 자리 수를 출력하도록 단순 ..
[Python] 2556번 별 찍기 - 14 https://www.acmicpc.net/problem/2556 2556번: 별 찍기 - 14 지금까지 안 나온 별 찍기가 뭐가 있는지 생각해본 후, 별을 적절히 찍으세요. www.acmicpc.net 22/10/08 번외 문제다. 문제 접근 방식: 직각삼각형을 출력하면 된다. 아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다. 더보기 n = int(input()) for i in range(n): print('*'*n)
[Python] 20130번 Metroidvania Extreme https://www.acmicpc.net/problem/20130 20130번: Metroidvania Extreme 첫 번째 줄에는 지금까지 기록한 좌표의 수 k을 출력한다. 이후 k개의 줄에 걸쳐 기록한 순서대로 방문한 칸의 행 번호와 열 번호를 공백으로 구분하여 출력한다. www.acmicpc.net 22/10/08 독특한 아이디어가 돋보이는 BFS문제로, 일반적인 BFS가 아니라 더 재미있게 느껴졌던 문제이다. 문제 접근 방식: 일단 당연히 시작 지점부터 무지성으로 BFS를 진행하면 안 된다. 해당 알파벳의 대문자 지점은 해당 알파벳의 소문자가 열쇠인데, 그 열쇠를 얻어야만 대문자 지역을 지날 수 있다는 제약조건이 걸려있기 때문이다. 이 문제의 핵심 아이디어는, 대문자 지역을 방문했을 때 열쇠를..

티스토리툴바