2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 고등학교 확률과 통계 시간에 경우의 수 파트에서 다루는 내용이다. 주어진 동전의 종류에 따라, 합을 만들 수 있는 경우의 수를 구하는 문제이다. 처음에는 경우의 수 문제를 풀듯이 가장 가치가 큰 동전부터 하나씩 줄여가며 갯수를 세주는 방식으로 구현하였는데, 동전 종류의 개수가 고정이 아니므로 재귀를 활용하였다. import sys sys.setrecursionlimit(10**9) n, k = map(int, input().split()) coins = list(..

1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 자연수 N이 주어졌을 때, N보다 작은 연속하는 소수들의 합이 N과 같을 경우의 수를 구하는 문제이다. N의 최댓값이 4,000,000이므로, 소수 판별에 있어서는 에라토스테네스의 체를, 연속합은 투 포인터 알고리즘을 통해 시간복잡도 O(n)으로 구현하였다. N = int(input()) # 예외 처리 if N == 1: print(0) exit(0) # 소수 판별 by 에라토스테네스의 체 sosu = [True for _ in range(N + 1)] number = list() for i in range(2, N + 1): if sosu[i]: for j in range(i, ..

2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 백준 단계별로 풀기에서 퇴각검색 카테고리에 속해 있는, N - Queen 다음으로 나오는 문제이다. N - Queen 문제를 완벽히 익히고 나면 구현하는 데에 어려움이 없겠지만, 파이썬은 요구 시간이 좀 짜서 빠른 입출력과 3중 반복문을 한 개의 반복문으로 줄이는 등 여러 노력 끝에 AC를 받아낼 수 있었다. import sys # 스도쿠 판과 아직 채워지지 않은 칸의 좌표를 담을 리스트 sodoku = list() blank = list() # 입력, 빈칸의 ..

16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 주어진 A값의 뒤에 1을 붙이거나 A를 2배하여 B로 도달하게 만드는 연산 횟수의 최솟값을 구하는 문제다. 요새 동적 계획법 연습을 많이 하기도 했고, 최근 푼 문제인 25418 - 정수 a를 k로 만들기가 동적 계획법으로 해결할 수 있는데, 이 문제와 결이 비슷하다고 생각하여 접근하였다가 메모리 초과가 나왔다. 그도 그럴 것이 B의 최댓값이 10^9 이므로 배열에 담기엔 너무 큰 수이긴 했다. (+ 동적 계획법은 배열에 일부 최적해를 계산해서 담는 방식인데, 작성한 코드를 보니 최적해를 계산한다기보단 그저 값을 할당하는 과정일 뿐이였다.) 1. DP let input = readLine..

1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 추가하는 건 맨 뒤에서, 빼는 건 양쪽 방향에서 해줄 수 있는 큐가 필요하다. 덱(double ended queue)을 구현해주면 되는데, 해당 문제에서는 양방향으로 추가해줄 필요가 없어서 기존에 구현했던 큐를 일부 수정, 변형하였다. 회전하는 큐 구현 struct Queue { var left = [Int]() var right = [Int]() var count: Int { left.count + right.count } var isEmpty: Bool ..