[백준] 15649번 - N과 M(1) 풀이 시간: 5분 이내 1) 문제 해결 아이디어 1부터 N까지의 자연수 중에서 중복 없이 M개를 고른 수열을 모두 구하는 문제로 전형적인 백트래킹 문제다. 아래 조건에 따르면 순열을 구하는 문제다. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 너무 기본 문제라 쉽게 풀 수 있었다. DFS를 이용하거나 permutations 라이브러리를 이용하는 방식 2가지가 있지만 이 문제는 순열을 구현하는 것이 키포인트이기 때문에 DFS를 이용한 풀이만 할 것이다. 순열을 구할 때는 dfs 인자로 깊이(depth)만 넘겨주면된다!! 2) 소스코드 n, m = map(int, input().split()) temp = [] # 수열을 담을 곳 # DFS def dfs(..
[백준] 15683번 - 감시 풀이 시간: 2시간 이내 1) 문제 해결 아이디어 사각 지대의 최소 크기를 출력하는 문제다. 처음에는 아무생각없이 BFS로 풀어도 되나하는 문제였지만 cctv들의 방향을 설정하는 모든 경우의 수를 고려하여 풀어야 하는 완전탐색 문제로 DFS를 이용하여 풀어야했다. 지금까지 풀었던 문제는 되게 단순하고 정형화된 문제였기때문에 새로운 방식으로 풀려고 아이디어를 떠올리는데 시간이 많이 걸렸다. 추후 꼭 복습이 필요한 문제!! 나는 북, 동, 남, 서 방향을 차례대로 0, 1, 2, 3 으로 설정하였다. CCTV 번호에 따른 방법(방향 경우의 수)수는 다음과 같다. 첫번째 오류. 틀렸습니다 nx, ny를 x, y로 초기화해야 하는데, dx를 1번 더해준 값으로 초기화해서 문제가 생..
[백준] 2503번 - 숫자 야구 굉장히 익숙한 소재라 문제를 이해하고 설계를 하는데 어려움이 없었으나 오류를 고치느라 시간이 좀 걸렸다. 서로 다른 숫자로 구성된 세자리수를 영수가 생각하고 있을 때, (민혁이가 질문한 세자리수, 스트라이크 개수, 볼 개수)를 보고 가능성이 있는 답의 총 개수를 구하는 문제로 전형적인 완전탐색 문제다. 영수가 생각할 수 있는 수의 모든 경우의 수는 순서가 상관이 있기 때문에 순열로 풀 수 있는데 DFS를 이용하거나 permutations를 이용한 방식 2가지가 있다. (풀이1) DFS 이용 풀이 시간: 40분 이내 1) 문제 해결 아이디어 1. 깊이가 3일 때 종료 num이 세자리수가 되었으므로 종료 1-1. 각 질문(세자리수)에 대해 스트라이크, 볼 개수에 모순이 생기..
[백준] 2309번 - 일곱 난쟁이 풀이 시간: 10~15분 이내 9난쟁이 중에 키의 합이 100이 되는 7난쟁이를 구하는 문제로 조건에 맞는 조합을 구하는 전형적인 완전탐색 문제다. 그냥 for문으로 풀거나 DFS를 이용하여 풀거나 combinations 라이브러리를 이용하여 풀 수 있다. for문으로 푸는 방식이 가장 간편한 방식인 것 같다. 정답은 오름차순으로 출력해야하므로 입력받은 값(arr)을 오름차순 정렬하고 시작하면 무조건 출력은 오름차순 형태가 된다. (풀이1) DFS 이용 1) 문제 해결 아이디어 1. 찾음 여부 확인 정답이 여러가지인 경우에는 아무거나 출력하라고 했으므로 정답을 찾으면 찾음 여부(find)를 True로 바꾼 후 해당 목록(temp)를 출력한다. 그리고 찾음 여부(find..
[백준] 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..
[백준] 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..
[백준] 1926번 - 그림 풀이 시간: 10분 이내 아주 쉽게 해결할 수 있었던 문제이다. 그림의 개수와 그 중 가장 넓은 그림의 넓이를 출력하는 문제로 BFS, DFS로 모두 풀이가 가능한 유형이다. 하지만 다른 사람들의 DFS 풀이를 찾아봐도 시간초과나 메모리초과 문제가 다수가 발생했다. 아래 글에 따르면 DFS에서 방향벡터를 이용해 for문을 돌리지 않으면 메모리 초과가 뜨지 않았지만 이런 문제의 경우 그냥 BFS로 풀이하는 것이 좋을 듯 하다. DFS는 재귀 방식으로 수행되기 때문에 호출할 때마다 스택에 쌓여 메모리를 많이 차지하게 되고 BFS는 큐에 쌓이는 객체의 크기가 크지 않다면 훨씬 적은 비용이 발생하므로 메모리 측면에서 유리할 수 있다. 오늘의 교훈! 상황에 따라 DFS, BFS 풀이를..
