DFS + Memorization 문제 (DFS로만 풀 시 시간초과) https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net (1) 시간초과난 코드 (실패) # 내리막 길 (골드 3) / DFS-recursion (시간 초과) import sys r, c = map(int, sys.stdin.readline().split()) arr = [] visit = [[False] * c for _ in range(r)] dx = [-1, 0, 1, 0] dy = ..

Dijkstra 문제 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) 처음에 실패한 이유 (1) 처음엔 distance[start] = 0 이부분을 빼뜨려서 dijkstra 로직이 동작하지 못했다. 즉, distance 벡터를 출력했을 때 값이 모두 최댓값으로 나오는 문제가 있었다. [10001, 10001, 10001, 10001, 10001] 이런식으로 나왔었음. (2) 두번째로는 distance..

DP로 해결 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 (1) 처음 내 코드 (런타임 에러 - 실패) # 피보나치 수4 (실버5) import sys n = int(sys.stdin.readline()) dp = (n + 1) * [0] dp[0] = 0 dp[1] = 1 for i in range(2, n + 1): dp[i] = (dp[i - 1] + dp[i - 2]) print(dp[n]) 문..

▪︎ 클래스명은 'Main'으로, 패키지는 없어야 함. public class Main { public static void main(String[] args) { // ... } } ▪︎ BufferedReader, BufferedWriter : Scanner나 sysout보다 속도가 빠르기 때문에 사용 1. 입력 // 엔터로 구분하여 입력을 받음. BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 띄어쓰기로 구분하는 경우에는 StringTokenizer 사용 StringTokenizer st = new StringTokenizer(br.readline()); 2. 출력 BufferedWriter bw = new B..

우선순위 큐 문제 입력 5 12 7 9 15 5-> 15 12 9 7 5 13 8 11 19 6-> 19 13 11 8 6 21 10 26 31 16-> 31 26 21 16 10 48 14 28 35 25-> 48 35 28 25 14 52 20 32 41 49 -> 52 49 41 32 20 다음과 같은 5X5 입력이 주어졌을 때, 5번째로 큰 수를 찾기 위해서 일단 입력 받은 줄별로 내림차순 정렬을 진행해보았다. 하지만, 5번째로 큰 수를 찾기 위해선 맨 마지막 줄에 있는 수들끼리만 비교하면 될게 아니라 필요에 따라선 그 위에 줄의 숫자도 함께 비교하며 N번째로 큰 수를 찾아나가야 한다. 그렇다고 해서 세로 방향으로는 정렬된 상태로 입력 받은 수들을 몽땅 하나의 리스트에 넣고 재정렬시키는 방법은 비..

BFS 문제 (1) 처음에 내가 생각한 방식 #BFS from collections import deque import math a,b=map(int,input().split()) queue = deque() count=[] ans=0 queue.append(a) index=0 while queue: index+=1 q = queue.popleft() if q==b: ans=math.ceil(math.sqrt(index)) break queue.append(q*2) queue.append(int(str(q)+str("1"))) print(ans) 처음에 이 문제를 보자마자 나는 위와 같은 방식으로 풀었다. 하지만, 예제 입력 1이나 예제 입력 3처럼 공백을 기준으로 입력 받은 왼쪽 값에서 오른쪽 값으로 ..