잡다로그

15656 N과 M(7) 문제 및 조건 설명: https://www.acmicpc.net/problem/15656 알고리즘 설계 모든 수열을 구해야 하고, N과 M의 범위가 크지 않으므로 모든 경우를 탐색하는 백트래킹을 활용한다. 백트래킹은 DFS로 전체를 탐색하되 조건이 맞지 않으면 중단하는 알고리즘이다. 알고리즘 구현 출처: https://honggom.tistory.com/109 import sys n, m = map(int, input().split()) arr = list(map(int, sys.stdin.readline().split())) sub = [] def func(): # m개 완성 되었으면 종료 if len(sub) == m: print(*sub) return for k in ran..

2239 스도쿠 문제 및 조건 설명: https://www.acmicpc.net/problem/2239 알고리즘 설계 💡idea. 각 칸마다 가능한 경우를 확인해야 한다. 특정 칸에서 막힌다면 그 직전에 채운 칸을 바꾸어야 한다. 조건에 맞지 않으면 다시 돌아가서 탐색을 시작한다는 점에서 백트래킹을 활용할 수 있음을 알 수 있다. 🎲step. 1. 함수 빈 좌표를 찾아, 값을 넣어보고 다음 칸에도 계속 넣어본다. 2. Base condition 빈 좌표가 없다면 종료된다. 3. 재귀 빈 좌표에 어떤 값을 넣고, 다음 빈 좌표에 값을 채우기 위해 재귀를 사용한다. def func(): # 빈 좌표를 찾는다. # 빈 좌표가 없다면 True 반환 # 빈 좌표가 있다면 for i in range(1, 10): ..

17829 222-풀링 문제 및 조건 설명: https://www.acmicpc.net/problem/17829 알고리즘 설계 💡idea. 주어진 행렬의 한 변의 길이는 항상 2의 거듭제곱 꼴이고, 2x2 정사각형으로 나눠야 한다. 단계별로 몇 개의 정사각형을 가지게 될 지 복잡하나, 단계별로 같은 동작을 반복하게 된다는 것을 알 수 있다. 즉 재귀로 풀 수 있다. 🎲step. 1. 함수 변의 길이가 2(즉 2x2 사각형)가 될 때까지 행렬을 쪼개고, 2x2일 때는 두 번째로 큰 값을 반환한다. def func(x, y, size)# x, y는 시작 좌표이고 size는 탐색할 부분의 한 변의 크기이다. 2. Base condition size == 1일 때. 즉 한칸 * 한칸이 남았을 때 3.재귀 한 번..

21735 눈덩이 굴리기 알고리즘 설계 💡idea. 많은 경우의 수를 고려해서 합이 최대가 되는 경우를 구해야 하는데, 입력값이 제한을 넘지 않으므로 백트래킹을 사용한다. 🎲step. 1. 함수 백트래킹을 사용할 것이므로, 함수의 실행마다(즉 경우의 수마다) 총합을 구해준다. 최종적으로 가장 큰 값을 결과로 출력할 것이다. snowball(t, i, value) #남은 시간 t, 이동한 현재 위치 i, 현재까지의 총합 value 2. Base condition 남은 시간이 0이거나 현재 위치가 끝일 때 t == 0 or i ==n 3. 재귀 합을 수행하고, 현재 위치에서 1번과 2번 이동 방법을 실행한다. if type == 1: 앞 1칸과 2칸의 요소 값의 비교 없이 연산이 끝나고 비교하는 이유는, 현..