본문 바로가기

CS/Data Structure & Algorithm

 (14)
Dijkstra 우선순위 큐(Priority Queue) 가장 높은 우선순위를 가진 데이터가 큐에서 먼저 추출되는 자료 구조 우선순위 큐(최솟값 찾기) 구현 방식 배열 연결리스트 ☆완전이진트리 ☆ enqueue() 들어오는 대로 배열에 append 시간복잡도 O(1) append 시 정렬 시간복잡도 O(nlogn) 우선순위 높은 값을 노드쪽으로 swap 시간복잡도 O(logn) dequeue() 모든 인덱스 확인하여 원하는 값 찾음 시간복잡도 O(n) 따로 확인 없이 추출 시간복잡도 O(1) 우선순위 높은 값을 노드쪽으로 swap하여 추출 시간복잡도 O(logn) 완전이진트리로 우선순위 큐 구현하는 것이 가장 시간복잡도 측면에서 효율적. 이러한 완전 이진트리는 힙 자료구조로 되어있음. 힙(Heap) 완전 이진 트리(co..
동적 계획법(DP) DP 문제에 대한 정답이 될 가능성이 있는 모든 해결책을 체계적이고 효율적으로 탐색하는 풀이 Top-down / Bottom-up 방식이 존재 최대/최소, 방법의 개수 등을 구할 때 주로 사용 미래의 계산이 앞선 계산 결과에 영향을 받을 때 주로 사용 DP 문제해결 과정 크고 복잡한 문제를 작은 문제들로 나눔 : subproblem(하위문제) 하위 문제의 답을 계산 중복 계산해야 하는 하위 문제가 존재 : overlapping subproblem(중복하위문제) 한 번 계산한 결과는 메모리에 저장하여 재계산하지 않도록 함 => 속도 향상(memoization, dp table) 하위 문제에 대한 답을 통해, 원래 문제에 대한 답을 계산 : potimal substructure(최적 부분 구조) * 최적 부..
그래프 순회 그래프 순회 그래프 탐색으로도 불림 그래프의 각 정점을 방문하는 과정 dfs / bfs 2가지 알고리즘 존재 너비 우선 탐색(BFS) 코드 템플릿(암기) from collections import deque def bfs(graph, start_v): visited = [start_v] queue = deque(start_v) while queue: cur_v = queue.popleft() for v in graph[cur_v]: if v not in visited: visited.append(v) queue.append(v) return visited bfs(graph, 'A') 깊이 우선 탐색(DFS) 코드 템플릿(암기) graph = { ... } visited = [] def dfs(cur_v)..
그래프 그래프 어떤 자료나 개념을 표현하는 정점(vertex)들의 집합과, 이들을 연결하는 간선(edge)들의 집합으로 구성된 자료구조 그래프가 트리보다 넓은 개념. (트리는 계층적 구조) 그래프 종류 방향 그래프 vs 무향 그래프 방향 그래프(방향이 존재) 무향 그래프(방향 미존재) 다중 그래프 vs 단순 그래프 다중 그래프(두 점을 연결하는 간선이 여러 개가 될 수 있음) 단순 그래프(두 점을 연결하는 간선이 한 개) 가중치 그래프 -> 다익스트라 한 점을 기준으로 간선들의 가중치가 존재 그래프 활용 도시들을 연결하는 도로망 지하철 연결 노선도 컴퓨터 네트워크 소셜 네트워크 분석 그래프 표현 방법 인접 행렬 graph = [ [0, 0, 1, 0, 1], [0, 0, 0, 1, 1], [1, 0, 0, 0,..
트리 순회 트리 순회 트리 탐색으로도 불림 트리의 각 노드를 방문하는 과정 recurrence relation(점화식), 모든 노드를 한 번씩 방문해야 함 -> 완전탐색 순회 방법: BFS / DFS 너비 우선 탐색(BFS) 루트 노드를 기준으로 루트 노드에서 가까운 것을 탐색 level 순서대로 (0 level, 1 level ...n level) 탐색 bfs는 queue 사용 접근 해야 할 노드들을 queue에 저장 -> 탐색 시 popleft() visited = [] 선언 후, 방문한 노드들을 visitied에 방명록처럼 남김 bfs 코드 템플릿(암기) def bfs(root) : visited = [] if root is None: return ; q = deque() q.append(root) while..
재귀 & 트리 재귀함수 자신을 정의할 때 자기 자신을 재참조 하는 함수 recurrence relation(점화식), base case로 구성됨 recurrence relation f(n)을 f(n-1), f(n-2), ... f(2), f(1)의관계식으로 표현한 것 ex) Factorial: f(n) = n * f(n-1) base case 더이상 재귀호출을 하지 않아도 계산값을 반활할 수 있는 상황(조건) 모든 입력이 최종적으로 base case를 이용해서 문제를 해결 무한 루프 방지 재귀함수의 시간 복잡도 재귀함수 전체 시간복잡도 = 재귀함수 호출 수 x (재귀 함수 하나 당) 시간복잡도 O(n)의 시간복잡도 f(n) = f(n-1) + n O(2^n)의 시간복잡도 f(n) = f(n-1) + f(n-2) O(l..
Hash Table & Dictionary Hash Table 효율적인 탐색(빠른 탐색)을 위한 자료구조 key-value 쌍의 데이터를 입력 받음 hash function에 key값을 입력으로 넣어 얻은 해시값을 위치로 지정하여 데이터 쌍(key-value)을 저장 저장, 삭제, 검색의 시간복잡도 O(1) Array List 또는 Array List+Linked List로 구현 가능 → 파이썬의 경우 Array List로 구현됨 Direct-address Table key 값이 index가 되는 테이블 낭비되는 메모리가 발생 문자열이 key로 들어오면 index로 사용 불가 이러한 문제를 해결하기 위해 Hash Table 사용 Collision 해시 테이블에서 인덱스 간 중복이 발생하는 것(충돌) Open Addressing, Seperate ..
List 리스트 set 자료형과는 다르게 순서가 있는 자료형 리스트 자료형의 경우 Array List또는 Linked List로 구현 가능 List Array List (Static) Array Dynamic Array Linked List Node Array List 배열 기반으로 연속적(순서대로) 데이터 저장 파이썬에서 말하는 list Array 또는 Dynamic Array로 구현(파이썬은 Dynamic Array를 통해 구현됨) Dynamic Array는 Array를 이용하여 구현 즉 Array->Dynamic Array->Array List (Static) Array 선언 시 size를 정하여(C언어) 해당 size만큼의 연속된 메모리를 할당 받아 데이터를 연속적(순차적)으로 저장 데이터의 갯수가 정해져..

티스토리툴바