728x90 SMALL 전체 글61 [백준] 1753번 : 최단경로 (파이썬) 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.. 2024. 1. 4. [백준] 2579번 : 계단 오르기 (파이썬) DP 문제 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net (1) 처음에 내가 생각한 방식 (실패) # 계단오르기 (실버3) import sys n = int(sys.stdin.readline()) score = [] for _ in range(n): i = int(sys.stdin.readline()) score.append(i) def ans(score): dp = [0] * n dp[n -1] = score[n - 1] dp[n - 2] = score.. 2024. 1. 3. [백준] 10826번 : 피보나치 수 4 (파이썬) 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]) 문.. 2023. 12. 27. C++ 이중 포인터 완벽 이해 이중 포인터 포인터를 가리키는 포인터는 다른 포인터의 주소를 보유하는 포인터로 생각하면 된다. 1) 단일 포인터 - int에 대한 일반 포인터 : 하나의 별표(*)만 사용해서 선언 int* ptr; 2) 이중 포인터 - int에 대한 포인터를 가리키는 포인터 : 두개의 별표(**)를 사용해서 선언 int** ptrptr; ▪︎ 단일 포인터와 이중 포인터 사용 예시 int value = 5; int* ptr = &value; cout 2023. 10. 1. 백준 자바 제출 방법 ▪︎ 클래스명은 '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.. 2023. 7. 23. Dijkstra 알고리즘 δ(A, B) : A->B로 가는 최단경로 w(A, B) : A와 B 사이의 연결된 edge의 weight if) A와 B 사이에 연결된 edge의 weight = 5 -> w(A,B) = 5 if) A와 B 사이에 edge가 X -> w(A, B) = ∞ (갈 수 없으므로) Single-Source Shortest Paths 시작 정점(s)이 하나 주어졌을 때, s에서 다른 모든 노드로 향하는 shortest path를 찾는 문제 Dijkstra Algorithm - S라는 이미 방문한 정점들에 대한 set 유지 -> 처음엔 비어있고, 시작과 동시에 시작 정점이 s에 들어가게 된다. - D라는 distance array를 정점 수만큼 유지 -> D[i]는 현재까지 밝혀진 경로들 중 최단 경로 (d(s,.. 2023. 5. 23. 이전 1 2 3 4 5 6 7 8 ··· 11 다음 320x100 LIST
