1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net ** 문제 유형 백트래킹 ** 풀이 C개의 문자들이 주어졌을 때, 가능한 L 길이의 암호를 모두 찾아야 함 따라서 C개의 문자들 중에서 L개를 선택하는 모든 조합을 고려 파이썬의 조합(combinations) 라이브러리를 사용하면 간단히 해결 가능 혹은 DFS를 이용하여 조합 함수 구현 가능 from itertools import combinations as comb l, c = map(int, input().split()) array = list(input().sp..

1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net ** 문제 유형 백트래킹 ** 풀이 말은 상, 하, 좌, 우 4가지 방향으로 이동할 수 있음 지금까지 지나온 모든 칸에 적혀 있는 알파벳과 다른 알파벳이 적힌 칸으로 이동해야 함 행의 길이(r)와 열의 길이(c)가 20 이하이므로, 백트래킹을 이용하여 모든 경우의 수 고려해야 함 # 이동 좌표 (상, 하, 좌, 우) dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] def bfs(x, y): global result # 동일한 경우는 한..

9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net ** 문제 유형 백트래킹 ** 풀이 대표적인 백트래킹(Backtracking) 문제 N의 크기가 작기 때문에 완전 탐색 가능 N x N 크기의 체스 보드 위에 퀸 N개를 서로 공격할 수 없게 배치시켜야 함 DFS를 이용하여 간단히 백트래킹 알고리즘을 구현할 수 있음 각 행을 차례대로 확인하면서, 각 열에 퀸을 놓는 경우를 고려함 이 때 위쪽 행과 대각선 행을 모두 확인하며, 현재 위치에 놓을 수 있는지 확인함 PyPy3로 제출 # x번째 행에 놓은 Queen에 대해서 검증 de..

1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net ** 문제 유형 그리디 ** 풀이 모든 박스를 배로 옮기는데 드는 시간의 최솟값 계산 매 분마다, 모든 크레인에 대하여 옮길 수 있는 박스를 선택하여 옮기도록 함 박스를 무게 기준으로 내림차순 정렬한 뒤에, 무거운 것부터 옮기도록 함 시간 복잡도 O(NM)에 문제 해결 가능: 크레인 개수 N, 박스 개수 M import sys n = int(input()) cranes = list(map(int, input().split())) m = int(i..

2012번: 등수 매기기 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다. 예상 등수는 500,000 이하의 자연수이다. www.acmicpc.net ** 문제 유형 그리디 ** 풀이 예상 등수와 실제 등수의 차이를 최소화해야 함 그 방법으로 예상된 등수를 오름차순으로 정렬하면 됨 n = int(input()) array = [] # 예상 등수 answer = 0 # 불만도의 합 for _ in range(n): array.append(int(input())) array.sort() # 오름차순 정렬 수행 for i in range(1, n + 1): answer += abs(i - array[i - 1]) prin..

1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net ** 문제 유형 그리디 ** 풀이 문자열에 있는 숫자를 모두 0 또는 모두 1로 만들어야 함 문자열의 길이는 100만 이하이므로, 시간 복잡도는 O(N)에 해결해야 함 data = input() states = [0] * 2 # states[0-1]: 0-1이 연속으로 오는 집합 수 states[int(data[0])] += 1 for i in range(1, len(data)): if data[i] != data[i - 1]: # 0과 1이 바뀔 때 state..