[백준] 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
[백준] 2798번 - 블랙잭 풀이 시간: 15분 이내 아주 쉽게 풀 수 있었고 완전탐색으로 풀어야하는 문제다. (풀이1) combinations 이용 1) 문제 해결 아이디어 itertools 모듈의 combinations 라이브러리를 이용하여 풀 수 있다. 2) 소스코드 from itertools import combinations # n: 카드 개수,m: 기준 숫자 n, m = map(int, input().split()) card = list(map(int, input().split())) max_res = 0 # M에 최대한 가까운 카드 3장의 합 # n개에서 3장 뽑아 m에 가장 가까운 3장의 합 찾기 for c in list(combinations(card, 3)): res = sum(c) ..
[백준] 2151번 - 거울 설치 풀이 시간: 3시간 이내 유사 문제: 2206 https://hseungyeon.tistory.com/223 [DFS/BFS/완전탐색] ★★ 2206번 - 벽 부수고 이동하기(BFS) [백준] 2206번 - 벽 부수고 이동하기 풀이 시간: 1) 문제 해결 아이디어 언제 벽을 부숴야 할지 조건을 떠올리는게 쉽지 않았다. 최근에 푼 BFS 문제 중에는 난이도가 가장 높은 문제인 것 같다. hseungyeon.tistory.com 1) 문제 해결 아이디어 문제를 읽었는데 문제 이해가 가질 않아서 15분정도 고민하다가 검색을 했고 도움을 받았다. 문제 자체가 이해가 가지 않아 어려움을 겪은 문제였다. 문제를 다 이해하고나서도 여러가지 오류를 해결하는데 시간이 오래걸렸기 때문에 ..
[백준] 4179번 - 불! 풀이 시간: 6시간 이내 유사한 문제: 3055 https://hseungyeon.tistory.com/241 [DFS/BFS/완전탐색] 3055번 - 탈출(BFS) [백준] 3055번 - 탈출 풀이 시간: 50분 이내 유사 문제: 4179 (풀이1) 물, 고슴도치 deque을 각각 생성한 방식(고슴도치→물 이동) 1) 문제 해결 아이디어 이 문제는 물이 차기 전에 고슴도치가 안전하 hseungyeon.tistory.com (풀이1) 실패한 코드 1) 문제 해결 아이디어 많이 어려웠던 문제로 추후 복습이 꼭 필요! 미로에서 지훈이의 위치와 불의 위치가 주어진다. 1분마다 지훈이는 상하좌우 중 1 방향으로 한 칸씩 이동하고 불은 상하좌우 4방향으로 1칸씩 이동한다. 지훈이가 불..
[백준] 3055번 - 탈출 풀이 시간: 50분 이내 유사 문제: 4179 (풀이1) 물, 고슴도치 deque을 각각 생성한 방식(고슴도치→물 이동) 1) 문제 해결 아이디어 이 문제는 물이 차기 전에 고슴도치가 안전하게 비버의 굴로 이동하기 위한 최소 시간을 구하는 문제로 BFS로 풀이가 가능하다. 혼자서 푸는데는 성공했지만 나중에 복습을 한번 해봐야할 문제! 매 분마다 고슴도치는 현재 있는 칸과 인접한 4칸 중 하나로 이동할 수 있고 물은 인접한 4방향으로 모두 이동한다. 고슴도치는 물이 찰 예정인 칸으로 이동할 수 없기 때문에 물→고슴도치 순으로 이동시켜야 하지만 고슴도치→물 순으로이동시켜도 전혀 문제가 되지 않는다. 그리고 고슴도치가 안전하게 비버의 굴로 이동할 수 없다면 "KAKTUS"를 출력해..
