[백준] 1759번 - 암호 만들기 C개의 알파벳 목록에서 길이 L인 암호(모음 최소 1개, 자음 최소 2개)를 모두 구하는 것으로 전형적인 완전탐색(백트래킹) 문제다. 풀이 방법은 DFS를 이용하거나 combinations 라이브러리를 이용하는 2가지 방식이 있다. combinations 풀이가 DFS보다 시간측면에서 효율적이기는 했지만 코딩테스트에서 combinations 라이브러리를 사용할 수 없는 경우도 있으므로 1번 풀이로도 풀 수 있어야 한다. (풀이1) DFS 이용 풀이 시간: 30분 이내 1) 문제 해결 아이디어 dfs 매개변수로 (현재 암호 길이, 탐색 시작 인덱스, 모음 개수, 자음 개수) 를 넘겨주게 했다. dfs를 호출할 때마다 모음, 자음 개수도 함께 변경하여 넘겨주기 때문에 암호..
[백준] 1018번 - 체스판 다시 칠하기 풀이 시간: 40분 이내 1) 문제 해결 아이디어 n * m 의 보드에서 8 * 8의 크기로 잘라 체스판 처럼 인접한 검정색, 흰색이 번갈아가게 색을 칠해야 한다. 다시 칠해야하는 칸의 최소 개수를 구하는 문제로 모든 경우의수를 확인해봐야하는 완전탐색 문제다. n * m 의 2차원 리스트에서 r * c의 2차원 리스트를 추출하는 방법이다. 1. for문 이용 아래의 글에 의하면 numpy를 이용하면 쉽게 구할 수 있지만 코딩테스트에서는 보통 라이브러리 사용을 못하는 경우가 많으므로 꼭 기억해두자!! graph = [[0] * m for _ in range(n)]# n * m # n * m 2차원 리스트에서 r * c 2차원 리스트 추출하기 for i in ran..
[백준] 7568번 - 덩치 풀이 시간: 10분 이내 1) 문제 해결 아이디어 이 문제는 아주 쉽게 해결할 수 있는 문제였다. N명의 몸무게, 키 정보로부터 각 사람의 덩치 등수를 구해 출력하는 문제로 자신을 제외한 다른 사람들과 모두 비교를 해야하는 완전 탐색 문제다. 덩치가 크다는 의미는 몸무게, 키 2개 모두가 남보다 커야하기 때문에 이 조건을 만족할 때마다 카운트를 하면된다. 2) 소스코드 import sys input = sys.stdin.readline n = int(input()) # 사람 수 # n 명의 몸무게, 키 graph = [list(map(int, input().split())) for _ in range(n)] rank = [] # 덩치 등수 for i in range(n): c..
[백준] 14888번 - 연산자 끼워넣기 풀이 시간: 60분 이내 문제의 아이디어를 떠올리고 구현하는 것 자체는 30분 정도 걸렸는데 반례를 찾아 오류를 고치느라 시간이 오래 걸렸다. 추후 복습이 필요한 문제! N개의 수와 N - 1 개의 연산자가 주어졌을 때, 만들 수 있는 식의 최댓값과 최솟값을 구하는 문제로 DFS로 풀거나 permutations 라이브러리를 이용하면 푸는 방법 2가지가 있다. 처음에 입력받은 +, -, *, / 의 개수(cnt)로부터 연산자 리스트(operator)를 만드는 것이 중요하다. +, -, *, / 는 차례로 0, 1, 2, 3 이라고 생각하고 해당 개수에 따라 값을 넣어 리스트를 만든다. + - * / 0 1 2 3 예를 들어, 입력받은 연산자 개수가 0 1 0 2 이..
[백준] 2309번 - 일곱 난쟁이 풀이 시간: 10~15분 이내 9난쟁이 중에 키의 합이 100이 되는 7난쟁이를 구하는 문제로 조건에 맞는 조합을 구하는 전형적인 완전탐색 문제다. 그냥 for문으로 풀거나 DFS를 이용하여 풀거나 combinations 라이브러리를 이용하여 풀 수 있다. for문으로 푸는 방식이 가장 간편한 방식인 것 같다. 정답은 오름차순으로 출력해야하므로 입력받은 값(arr)을 오름차순 정렬하고 시작하면 무조건 출력은 오름차순 형태가 된다. (풀이1) DFS 이용 1) 문제 해결 아이디어 1. 찾음 여부 확인 정답이 여러가지인 경우에는 아무거나 출력하라고 했으므로 정답을 찾으면 찾음 여부(find)를 True로 바꾼 후 해당 목록(temp)를 출력한다. 그리고 찾음 여부(find..
[백준] 1436번 - 영화감독 숌 풀이 시간: 10분 이내 1) 문제 해결 아이디어 쉽게 아이디어를 떠올릴 수 있었던 문제였다. 666이 들어가는 숫자 중 작은 순서대로 N번째인 수를 찾는 문제로 모든 경우의 수를 확인해보아야 하는 완전 탐색 문제이다. 가장 작은 종말 숫자인 666부터 값을 1씩 증가시켜가면서 n번째로 작은 종말 숫자를 찾으면 된다. 조금이라도 탐색을 적게하려면 1이 아니라 최소 숫자인 666부터 시작해야한다. 2) 소스코드 n = int(input()) cnt = 0 # 종말 숫자 개수 num = 666 # 가장 작은 종말수 while True: # 666이 있으면 개수 세기 if '666' in str(num): cnt += 1 # n번째로 작은 종말수이면 출력 종료 if cnt ..
[백준] 10819번 - 차이를 최대로 풀이 시간: 20분이내 N개의 정수로 이루어진 배열 A에 있는 수의 순서를 적절히 바꿔 얻을 수 있는 식의 최댓값을 구하는 문제로 모든 경우의 수를 확인해봐야하는 완전탐색 문제다. 나중에 다시 풀어볼만한 문제! (풀이1) permutations 라이브러리 이용 1) 문제 해결 아이디어 permuations를 이용하면 일단 순열을 따로 구현할 필요가 없기 때문에 쉽게 풀 수 있다. 2) 소스코드 from itertools import permutations n = int(input()) arr = list(map(int, input().split())) # n개의 정수 max_res = 0 # 최댓값 for a in permutations(arr): res = 0 f..
[백준] 10974번 - 모든 순열 풀이 시간: 20~30분 이내 라이브러리를 사용하지 않는다면 시간이 좀 걸린 문제로 추후 복습 필요! (풀이1) permutaions 라이브러리 이용 1) 문제 해결 아이디어 파이썬에서 순열을 반환해주는 라이브러리를 이용하면 쉽게 풀 수 있다. 1. '구분자'.join(리스트) 이용 join을 이용하면 리스트의 문자들을 구분자로 이어붙여 문자열로 출력할 수 있다. 다만, graph에 담긴 원소들은 문자가 아니라 숫자이므로 map을 이용하여 int→str 형변환한 후 join함수를 사용해야 한다! 2. 2중 for문 이용 2) 소스코드 from itertools import permutations n = int(input()) graph = [i for i in rang..
