본문 바로가기

분류 전체보기

 (41)
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..
빅데이터 아키텍처 빅데이터 아키텍처 개요Sources → Ingestion and Procssing → Storage →  Analytics and Prediction → OutputSource : 비즈니스/운영 데이터가 생성 Ingestion and Procssing : 데이터 소스로부터 데이터를 수집하여 데이터 추출/변형/적재(ETL) Storage : 쿼리와 프로세싱이 가능한 형태로 데이터 저장 Analytics and Prediction : 데이터 탐색 및 분석Output : 분석 결과 -> 대시보드/리포팅/모델을 어플리케이션에 탑재Workflow Management : 위 플로우를 관리하는 도구Source비즈니스/운영 데이터가 생성Data 종류정형데이터RDBMS, 엑셀 스프레드 시트비정형 데이터텍스트, 이미지, ..
데이터파이프라인 관련 영상 https://www.youtube.com/watch?v=rCbzilpjsdY https://www.youtube.com/watch?v=A8RpAFvbrl0 https://www.youtube.com/watch?v=8ZhnUgylQgo https://www.youtube.com/watch?v=6CZwKUp1ozw

티스토리툴바