유령이 나오는 젤리하우스

Algorithm/Baekjoon

[BOJ 10826][백준 10826번] 피보나치 수 4 (파이썬 풀이)

https://www.acmicpc.net/problem/10826 10826번: 피보나치 수 4 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 🤔 문제 설명 및 입출력 ✍ 접근 방법 피보나치 수열을 구하는 방법은 여러가지가 있는데, 그 중 가장 대표적인 방법이 재귀 함수로 구현하는 방법과 메모이제이션을 활용한 풀이이다. 나는 DP를 이용해서 풀어봤다. 점화식에 따라, n번째 피보나치 수를 구하기 위해 n-1번째 수와 n-2를 더하는데, n-1번째 수와 n-2를 매번 계산하는 것이 아니라, 저장된 어..

Algorithm/Baekjoon

[BOJ 1753][백준 1753번] 최단 경로 (파이썬 풀이)

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 🤔 문제 설명 및 입출력 ✍ 접근 방법 1. 그래프를 탐색해야한다. 2. 근데 edge에 (음수가 아닌) 가중치가 붙어있다. 3. 다익스트라 알고리즘으로 푼다! 라는 사고방식이 머리 속 깊이 박혀 있었기 때문에, 다익스트라를 통한 풀이법을 생각하는 것은 어렵지 않습니다. 다만 "이것을 어떻게 최적화 할까?" 라는 물음에 답하는 것이 어려웠지요. 입력값이 1

Algorithm/Baekjoon

[BOJ 1932][백준 1932번] 정수 삼각형 (파이썬 풀이)

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 🤔 문제 설명 및 입출력 ✍ 접근 방법 이동할 수 있는 경로가 천차만별이고, 그 과정을 다 일일이 추적하기에는 굉장히 복잡했기 때문에 메모이제이션으로 해결해야겠다는 생각이 들었다. 메모이제이션의 기본 아이디어는 입력값을 받는 배열 이외에 새로운 배열을 만들어, 현재 필요한 값을 구할 때 새로운 배열의 이전 값을 참조하여 푸는 방식으로 접근하는 것이다. 문제 예시가 트리와 유사하게 생겼기에, 각 입력값을 노드라고 생각하고 각 노드까지 도달하는데의 최대값을 저장하면 된다고..