Programming language/Algorithm4 [Algorithm]Dijkstra 최단 경로 알고리즘 틀린 부분이 있다면 언제든지 댓글 남겨주세요! 최단 거리 알고리즘 Dijkstra 알고리즘 - 그래프에서 여러 개의 노드가 있을 때 특정 노드에서 다른 노드로 가는 각각의 최단 경로 (0보다 적안 값을 가지는 간선이 없어야 함) = greedy 알고리즘(가장 비용이 적은 노드 선택) - 최단경로를 구하는 과정에서 각 노드에 대한 현재까지의 최단거리를 1차원 리스트에 계속 갱신 = 최단 거리 테이블 - 출발 노드에서 다른 모든 노드로 가는 최단거리는 '무한' = 999,999,999(=약 10억) = 1e9 = 주로 int(1e9)로 초기화 - 최단 거리가 같은 경우 주로 더 작은 번호의 노드를 선택 - 최단 거리를 갱신할 수 있는 최단 거리가 없는 경우 최단 거리 테이블을 갱신하지 않음 - 이미 방문처리.. 2022. 1. 27. Python 주요 자료형 시간 복잡도 틀린 부분이 있다면 언제든지 댓글 남겨주세요! 코딩 테스트 효율성 통과하기 너무 어렵다 List Operation Example Complexity Class Notes Index l[i] O(1) Store l[i] = 0 O(1) Length len(l) O(1) Append l.append(5) O(1) Pop l.pop() O(1) same as l.pop(-1) Clear l.clear() O(1) similar to l = [] Slice l[a:b] O(b-a) l[:] : O(len(l)-0) = O(N) Extend l.extend(…) O(len(…)) depends only on len of extension Construction list(…) O(len(…)) depends on .. 2022. 1. 24. [Algorithm]DFS/BFS 개념 틀린 부분이 있다면 언제든지 댓글 남겨주세요! DFS(Depth-First Search) : 깊이를 우선적으로 탐색, 스택 및 재귀함수 사용 최상단 노드를 시작으로 인접한 노드 중 방문하지 않은 노드를 깊이 우선으로 선택 방문하지 않은 인접 노드가 없으면 스택의 최상단 노드를 꺼냄 방문했던 노드를 체크하여 더 이상 방문할 수 있는 노드가 없는 경우 종료 # chapter 5 DFS def dfs(graphs, n, visit): visit[n]=True # 방문 #print(n) for i in graphs[n]: if visit[i]==0: visit[i]=1 dfs(graphs, i, visit) visit=[0]*9 # graph의 개수에 맞춰 노드 방문 여부 확인을 위한 리스트 생성 graphs=.. 2022. 1. 18. [Algorithm] 선형구조-리스트/스택/큐/데크 틀린 부분이 있다면 언제든지 댓글 남겨주세요! 아래에서 설명할 자료구조는 파이썬에서 리스트를 이용하면 대부분 구현 가능하다. 순차 리스트 (> static) : 배열과 유사하게 동일한 유형의 자료를 연속적으로 나열하기 위해 사용되는 추상 데이터 구조(ADT) * ADT(추상화 자료 구조): 프로그램의 대상이 되는 무엇인가를 추상화하여 표현하는 것으로 유지보수가 용이 - 특정 위치에서의 삽입/삭제 = O(n) - i번째 노드 탐색 수행 시간 = O(1) > 각 배열의 위치를 알고 있기 때문에 연결리스트 (> dynamic) : 자료의 연결을 위해 포인터 사용, 각 노드는 다음 노드를 가리키는 포인터를 가짐 - 특정 위치에서의 삽입/삭제 = O(1) - i번째 노드 탐색 수행 시간 = O(n) 배열을 이용해.. 2022. 1. 16. 이전 1 다음 728x90 반응형
