백준 3055 탈출 Gold V 문제링크 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 나의 접근 너비 우선 탐색으로 한시간이 지날때마다 물에 대한 경로탐색 및 이동 후, 고슴도치에 대한 경로 탐색 및 이동을 진행해야한다. 처음에는 단순 BFS로 구현했다가 당연히 시간초과가 떴다. Deque을 사용하고, 미리 선언해놓은 N 길이의 배열에 거리를 저장해준다. from collections import deque def bfs(x, y): q.append([x, y]) mapp[x][y] = 1 dx = [1, -1, 0,..
문제: 2748: 피보나치수2 백준 2748 Dynamic Programming Silver V 문제링크 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 된 www.acmicpc.net 접근: a1, a2를 각각 피보나치 수열의 시작인 0과 1로 설정해주고 while loop이 한 번 돌 때마다 a1, a2를 재설정해준다. 포인터만 잘 설정해주면 된다. count가 N과 같아지면 while문이 종료된다. 내 코드: N = int(input()) a1 = 0 a2 = 1 # a1 a2 # a1 a2 # a..
문제 SWEA Stack 4869 D2 파이썬 문제링크 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 접근 이 문제는 점화식을 사용해서 푸는 문제라고 한다..! 처음 문제를 보았을 때 대체 어떻게 접근을 해야하는지 몰라서 여러 코드를 찾아봤는데 아직도 잘 이해가 가지 않기 때문에 다음에 리뷰해보겠다 ㅠㅠ 동적프로그래밍(Dynamic Programming)의 일종이라고도 한다. 방식: n = 1, n = 2, n = 3 ... 일 때의 경우의 수를 찾아본다. n = 1 일 때는 경우가 1개가 나오고 n = 2일 때는 경우가 3개가 나온다. n = 3일 때부터 규칙이 드러나는데 그 규칙을 dp(n-1) + 2 *..
