CS/알고리즘
-
[알고리즘 + Python] 최단 경로 알고리즘 - 다익스트라(dijkstra), 플로이드 워셜(Floyd-Warshall)CS/알고리즘 2023. 2. 5. 22:07
해당 게시물은 동빈나님 유튜브 "(이코테 2021 강의 몰아보기) 7. 최단 경로 알고리즘"을 보고 학습용으로 기록한 것입니다. 최단 경로 문제 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미한다. cf. 다양한 문제 상황 한 지점에서 다른 한 지점까지의 최단 경로 한 지점에서 다른 모든 지점까지의 최단 경로 모든 지점에서 다른 모든 지점까지의 최단 경로 각 지점은 그래프에서 노드로 표현한다. 지점 간 연결된 도로는 그래프에서 간선으로 표현한다. 1. 다익스트라 최단 경로 알고리즘 개요 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다. 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작한다. 현실 세계의 도로(간선)은 음의 간선으로 표현되지 않는다. 다..
-
[알고리즘 + Python] DP(Dymanic Programming, 다이나믹 프로그래밍)CS/알고리즘 2023. 2. 2. 21:27
해당 게시물은 동빈나님 유튜브 "(이코테 2021 강의 몰아보기) 6. 다이나믹 프로그래밍"을 보고 학습용으로 기록한 것입니다. DP 사용조건 다이나믹 프로그래밍은 다음 조건을 만족할 때 사용할 수 있다. 최적 부분 구조(Optimal Substructure): 큰 문제를 작은 문제로 나눌 수 있다. 중복되는 부분 문제(Overlapping Subproblem): 동일한 작은 문제를 반복적으로 해결한다. DP 예시 대표적인 문제로는 피보나치 수열이 있다. (cf. 점화식: 인접항들의 관계식을 의미한다.) // 피보나치 수열 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ... * 피보나치 수열의 점화식 재귀함수를 통해서 점화식을 소스코드로 구현할 수 있다. 프로그래밍에서는 이러한 수열..
-
[알고리즘 + Python] DFS(Depth-First Search, 깊이우선탐색) & BFS(Breadth-First Search, 너비우선탐색)CS/알고리즘 2023. 2. 2. 21:27
해당 게시물은 동빈나님 유튜브 "(이코테 2021 강의 몰아보기) 3. DFS & BFS"를 보고 학습용으로 기록한 것입니다. Stack과 Queue 자료구조 1) Stack 파이썬에서 스택은 리스트 자료구조를 사용하면 된다. cf) stack[::-1] : 최상단 원소부터 출력 stack = [] stack.append(5) # 삽입 stack.append(2) stack.append(3) stack.append(7) stack.pop() # 제거 stack.append(1) stack.append(4) stack.pop() # 최상단 원소부터 출력 print(stack[::-1]) # [1, 3, 2, 5] # 최하단 원소부터 출력 print(stack) # [5, 2, 3, 1] 2) Queue 리..