코딩하는 해맑은 거북이

해당 글은 백준 1158번 문제 '요세푸스 문제'를 다룬다. 문제 https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 설명 deque의 rotate 함수를 사용해서 -(k-1)만큼 큐를 돌리고, 가장 첫번째 값만 계속 뽑으면 된다. 그리고 출력을 할 땐, replace 함수를 이용해서 리스트의 [ ] 괄호를 괄호로 변경할 수 있다. 코드 from collections import deque n, k = map(int, input().split()) queue = deque([i for i in range(1, n+1)]) resul..

해당 글은 백준 2579번 문제 '계단 오르기'를 다룬다. 문제 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 설명 해당 문제는 동적 계획법 알고리즘으로 풀 수 있는 문제이다. 마지막 n번째 계단은 반드시 밟아야 하므로, 마지막 n번째 계단을 밟을때 1) n-1번째 계단을 밟지 않는 경우, n-2번째 계단을 밟는다. 2) n-1번째 계단을 밟는 경우, n-2번째 계단을 밟지 않는다. 즉, 점화식은 아래와 같이 표현된다. dp[i] = max(stairs[..

해당 글은 백준 3085번 문제 '사탕 게임'을 다룬다. 문제 https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net 설명 해당 문제는 사탕의 색이 다른 인접한 두 칸을 모두 바꿔가며 완전 탐색하는 문제이다. 탐색을 진행해보면서 행과 열 중 같은 색이 가장 큰 갯수를 구해나간다. 코드 n = int(input()) board = [] for i in range(n): board.append(list(input())) dx = [-1, 1, 0, 0] dy = [0, 0, 1, -1] def search(board): row_max, col_max = 0, 0 for i..

해당 글은 백준 10610번 문제 '30'을 다룬다. 문제 https://www.acmicpc.net/problem/10610 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net 설명 숫자들을 조합해서 30의 배수가 될 수 있는 가장 큰 값을 출력하는 문제이다. 30의 배수는 10의 배수와도 같으므로 숫자들에 0이 꼭 포함되어 있어야 한다. 그리고 30의 배수는 10으로 나누면 3의 배수와도 같으므로 3, 6, 9, 12(1+2=3), 15(1+5=6), 18(1+8=9), ... 와 같이 숫자들의 총 합이 3의 배..

해당 글은 백준 2164번 문제 '카드2'를 다룬다. 문제 https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 설명 deque 모듈을 불러와서 쉽게 구현할 수 있는 문제이다. 문제에서 제안하는대로 카드 1장이 남을 때 까지 첫번째를 카드를 꺼내서 버리고, 다음 첫번째 카드를 아래로 다시 보내면 보내는 과정을 반복한다. 그리고 카드가 한 장 남았으므로 인덱스 0번째 카드를 출력한다. 코드 from collections import deque n = ..

해당 글은 백준 1463번 문제 '1로 만들기'를 다룬다. 문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 설명 3개의 연산을 섞어서 1로 만드는 최소의 경우의 수는 이전 결과를 통해서 구하면 되는 DP 문제이다. -1은 무조건 연산이 가능하므로 dp[i] = dp[i-1]+1을 해주고, 2나 3으로 나누어 떨어지는 연산은 -1한 dp값과 나누기를 했을때의 dp값과 비교해서 최소값을 선택하면 된다. 여기서 2, 3으로 둘다 나누어 떨어지는 경우의 수가 있을 수도 있으므로 if-elif문이 아닌 if-if문으로 두 경우를 모두 계산해서 가장 최소값을 입력..