[백준] 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분정도 고민하다가 검색을 했고 도움을 받았다. 문제 자체가 이해가 가지 않아 어려움을 겪은 문제였다. 문제를 다 이해하고나서도 여러가지 오류를 해결하는데 시간이 오래걸렸기 때문에 ..
[백준] 3055번 - 탈출 풀이 시간: 50분 이내 유사 문제: 4179 (풀이1) 물, 고슴도치 deque을 각각 생성한 방식(고슴도치→물 이동) 1) 문제 해결 아이디어 이 문제는 물이 차기 전에 고슴도치가 안전하게 비버의 굴로 이동하기 위한 최소 시간을 구하는 문제로 BFS로 풀이가 가능하다. 혼자서 푸는데는 성공했지만 나중에 복습을 한번 해봐야할 문제! 매 분마다 고슴도치는 현재 있는 칸과 인접한 4칸 중 하나로 이동할 수 있고 물은 인접한 4방향으로 모두 이동한다. 고슴도치는 물이 찰 예정인 칸으로 이동할 수 없기 때문에 물→고슴도치 순으로 이동시켜야 하지만 고슴도치→물 순으로이동시켜도 전혀 문제가 되지 않는다. 그리고 고슴도치가 안전하게 비버의 굴로 이동할 수 없다면 "KAKTUS"를 출력해..
[백준] 1541번 - 잃어버린 괄호 1) 문제 해결 아이디어 - 기준으로 괄호를 쳤을 때 최솟값이 된다. 60+20-50+10-20+30 이 입력으로 들어오면 (60+20)-(50+10)-(20+30) 이렇게 괄호를 쳤을 때 최소값이 된다. 상식적으로 최소값을 만들기 위해서는 큰 값으로 뺴주어야 하는데 - 기준으로 나누었기 때문에 괄호 ( ) 안에는 항상 숫자 혹은 더하기로만 이루어진 식이 오게 된다. 1. - 기준으로 분리한 결과 ["60+20", "50+10", "20+30"] 2. 각각을 + 기준으로 분리하고 int형 변환한 결과 [60, 20], [50, 10], [20, 30] 3. 첫번째 결과에서 나머지 결과들을 모두 뺀 결과 80 - 60 - 50 = -30 첫번째 괄호의 계산값에서 나머지..
[백준] 5585번 - 거스름돈 1) 문제 해결 아이디어 그리디 알고리즘의 대표적인 문제이다. for문에서 화폐단위가 큰 것부터 검사해야 총 동전 수의 최소값을 만들 수 있다. 2) 소스코드 pay = int(input()) # 지불 금액 money = [500, 100, 50, 10, 5, 1] charge = 1000 - pay # 잔돈 res = 0 # 잔돈 개수 for m in money: # 탈출 조건 if(charge == 0): break # 해당 단위로 나눠지면 if((charge // m) != 0): res += charge // m # 잔돈 개수 추가 charge %= m # 잔액 변경 print(res)
