[백준] 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..
[백준] 2331번 - 반복수열 풀이 시간: 20분 이내 1) 문제 해결 아이디어 이 문제는 설명에 나와있는대로 구현을 하면 되는 문제였다. 아이디어만 쉽게 떠올리면 금방해결되는 문제! D[1] = A D[n] = D[n-1]의 각 자리의 숫자를 P번 곱한 수들의 합 위와 같은 연산을 반복했을 때 만들어지는 수열에서 반복되는 부분을 제외한 수들의 개수를 구하는 것이다. 반복이 시작되는 지점의 인덱스를 찾아 그 인덱스를 출력시켜주면 된다. 여기서 중요한 점은 연산을 해서 현재 만들어낸 값(num)이 수열(d)에 있다는 조건을 최초로 만족할 때 그 값(num)이 반복이 시작되는 값이 된다는 것이다. 그러므로 반복이 시작되는 값의 인덱스(start)를 찾으면 정답이다. 2) 소스코드 a, p = map(int..
[백준] 10451번 - 순열 사이클 풀이 시간: 20분 이내 매번 위치벡터를 이용한 DFS/BFS문제를 풀다가 오랜만에 그래프 문제를 만나 평소보다 조금 시간이 걸리긴 했지만 쉽게 풀 수 있는 문제였고 DFS, BFS 중 편한 방식으로 풀면 된다. 이 문제의 경우 메모리, 시간 측면에서 모두 DFS로 푸는 것이 더 효율적인 결과가 나왔기 때문에 DFS로 푸는 것을 추천한다. (풀이1) DFS 1) 문제 해결 아이디어 2) 소스코드 t = int(input()) # 테스트 케이스 수 # DFS def dfs(v): visited[v] = True # 현재노드 방문처리 nv = graph[v] # 인접 노드 # 아직 방문하지 않은 노드라면 dfs 호출 if not visited[nv]: dfs(nv) fo..
[백준] 9663번 - N-Queen 풀이 시간: 60분 이내 1) 문제 해결 아이디어 어떤 식으로 풀어야할지 구상은 했으나 막상 코드로 짜기가 어려웠던 문제였다. 추후 복습이 꼭 필요!! N X N의 체스판에서 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 구하는 문제로 전형적인 백트래킹, 완전탐색 문제다. 상하좌우/대각선 원하는 만큼 이동 가능 처음에는 2차원 리스트를 이용하여 간 곳을 체크하는 방식으로 하나하나 확인해야하나 했는데, 다른 글들을 보니 행/열(n)의 크기만큼 1차원 리스트를 만들고 (리스트[행] = 열) 혹은 (리스트[열] = 행) 과 같이 퀸의 위치를 저장하였다. 1차원 리스트로 퀸의 위치를 저장하는 것이 중요포인트!! 나는 행을 기준으로 퀸을 배치할 열을 선택하기 위해 (리스트..
[백준] 2231번 - 분해합 풀이 시간: 20분 이내 1) 문제 해결 아이디어 자연수 N의 가장 작은 생성자를 구하는 문제로 완전탐색으로 풀어야 하는 문제다. N = M + M의 각 자리수의 합 → N의 생성자 = M 우리가 구해야할 값은 M이고 여기서 1
