https://www.acmicpc.net/problem/1904피보나치수열 문제와 비슷하지만, 재귀(Top-down)하를 사용하지 않고동적 계획법(DP; Dynamic Programing) 기법 중 하나인Bottom-up을 사용하여 해결해야한다.▷ 풀이한 키워드동적 계획법(DP)Bottom-up▷ Bottom-up위(큰 문제)에서 아래(작은 문제)로 내려가는 Top-down(재귀)와 반대로,작은 문제부터 차근차근 쌓아 올려서 큰 문제를 푸는 방법. DP에서 흔히 쓰이는 방식으로,기저 조건(Base Case)에서 출발해서 (ex; 피보나치의 f(0), f(1) )반복문으로 위로 계산해나간다. ( f(3) f(4) .... f(n) ) ▷ 전체 코드import sysinput = sys.stdin.re..

https://www.acmicpc.net/problem/2748해당 문제는 매우 간단한 문제다. DP 기법 중 하나인 Memoization을 이용해 해결했다.▷ 풀이한 키워드DPMemoization▷ 전체 코드import sysn = int(sys.stdin.readline().strip())memo = [-1 for _ in range(n+1)]memo[0], memo[1] = 0, 1def fibonacci(n): if memo[n] == -1: memo[n] = fibonacci(n-1) + fibonacci(n-2) return memo[n]print(fibonacci(n))▷ 코드 설명1. 메모이제이션 배열 초기화memo = [-1 for _ in range(n+1)]먼..

문제N*M배열에 미로가 주어지며, (1,1)에서 시작해 (N, M)에 도착하는 최단 거리를 찾는 문제다.접근 최단 경로를 찾는 문제이기에 DFS보단 BFS가 적합하다. 해당 문제는 모든 간선의 가중치가 동일하기에,BFS를 사용하면 "먼저 발견한 거리 = 최단 거리"라는 보장이 성립한다.반면 DFS를 사용하면 보장이 성립하지 않기 때문이다. 따라서 BFS의 최단 거리 보장을 이용해 문제를 풀었다. + BFS가 최단 거리를 보장하는 이유더보기더보기가중치가 모두 1이라고 가정하면, BFS는 시작 정점에서부터거리 1인 노드들 → 거리 2인 노드들 → 거리 3인 노드들 …이런 식으로 거리 순서대로 탐색을 진행한다. 즉, BFS는 탐색 레벨 자체가 곧 “이동 거리”가 된다.따라서 목표 정점에 처음 도착한 순간은..

https://www.acmicpc.net/problem/1991 문제이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.예를 들어 위와 같은 이진 트리가 입력되면,전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)가 된다. 입력첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른..

https://www.acmicpc.net/problem/2110문제 간단 정리N개의 집이 수직선 위에 흩어져 있고, C개의 공유기를 설치해야 한다.조건: 공유기 사이의 최소 거리를 최대한 크게 만들기.출력: 가능한 최대 최소 거리.처음 문제를 읽었을 때는 “이게 왜 이분 탐색이지?“라는 의문부터 들었다.보통 이분 탐색은 정렬된 배열에서 값을 찾을 때 쓰는 것으로만 생각했기 때문이다. 고민 과정처음엔 단순히 집들을 순서대로 배치하면서 거리 차이를 세면 되지 않을까? 하는 생각이 들었다.하지만 공유기를 어디에 놓느냐에 따라 최소 거리가 달라지고,그 경우의 수를 전부 따져보는 건 시간 초과가 날 게 뻔했다. 그러다 보니 “최소 거리 D가 가능할까?”라는 질문으로 문제를 바꿔서 생각하게 되었다.핵심 아이디어:..