문돌이 Theo

최단 경로 최단 경로 정의 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로 하나의 시작 정점에서 끝 정점까지의 최단 경로 다익스트라(dijkstra) 알고리즘 음의 가중치를 허용하지 않음 벨만-포드(Bellman-Ford) 알고리즘 음의 가중치 허용 모든 정점들에 대한 최단 경로 플로이드-워샬(Floyd-Warshall) 알고리즘 Dijkstra 알고리즘 시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식 시작정점(s)에서 끝정점(t) 까지의 최단 경로에 정점 x가 존재 이때, 최단경로는 s에서 x까지의 최단 경로와 x에서 t까지의 최단경로 구성 탐욕 기법을 사용한 알고리즘으로 MST의 프림 알고리즘과 유사 알고리즘 # 다익스트라 알..

최소신장트리 (MST) 그래프에서의 최소 비용 문제 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리 두 정점 사이의 최소 비용의 경로 찾기 신장 트리 n 개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리 최소신장 트리 (Minimum Spanning Tree) 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리 MST 표현 그래프 간선들의 배열 인접 리스트 부모 자식관계와 가중치에 대한 배열 (트리) Prim 알고리즘 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어가는 방식 임의 정점을 하나 선택해서 시작 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택 모든 정점이 선택..

서로소 집합 (Disjoint-Sets) 서로소 또는 상호배타 집합들은 서로 중복 포함된 원소가 없는 집합들 집합에 속한 하나의 특정 멤버를 통해 각 집합을 구분 → 이를 대표원소(representative)라고 함 상호배타 집합을 표현하는 방법 연결 리스트 트리 상호배타 집합 연산 Make-Set(x) Find-Set(x) Union(x, y) 상호배타 집합 예시 Make-Set(x) Make-Set(y) Make-Set(a) Make-Set(b) Union(x, y) Union(a, b) Find-Set(y) → return x (representative) Find-Set(b) → return a (representative) Union(x, a) 상호배타 집합 표현 - 연결리스트 같은 집합의 원소..

그래프 아이템(사물 또는 추상적 개념)들과 이들 사이의 연결관계를 표현 정점(Vertex)의 집합과 이들을 연결하는 간선(Edge)들의 집합으로 구성된 자료 구조 v : 정점의 개수, e : 간선의 개수 v 개의 정점을 가지는 그래프는 최대 v(v-1)/2 간선이 가능 선형 자료구조나 트리 자료구조로 표현하기 어려운 N : N 관계를 가지는 원소들을 표현하기에 용이 그래프 유형 무향 그래프 (Undirected Graph) 유향 그래프 (Directed Graph) 가중치 그래프 (Weighted Graph) 사이클 없는 방향 그래프 (DAG, Directed Acyclic Graph) 완전 그래프 정점들에 대해 가능한 모든 간선들을 가진 그래프 부분 그래프 원래 그래프에서 일부의 정점이나 간선을 제외한..

퀵 정렬 (Quick Sort) 주어진 배열을 두 개로 분할하고, 각각을 정렬 그럼 병합 정렬과 동일한 것이 아닌가? 차이점 1 : 병합 정렬은 그냥 두 부분으로 나누는 반면, 퀵 정렬은 분할할 때, 기준 아이템(pivot item) 중심으로, 이보다 작은 것은 왼편, 큰 것은 오른편에 위치 차이점 2 : 각 부분 정렬이 끝난 후, 병합 정렬은 "병합"이란 후처리 작업이 필요하나, 퀵 정렬은 필요 없음 퀵 정렬 과정 알고리즘 def quick_sort(a, low, high):# (리스트, 시작 인덱스, 끝 인덱스) if low < high: pivot = partition(a,low,high) quick_sort(a, low, pivot-1) quick_sort(a, pivot+1, high) Hoar..

병합 정렬 (Merge Sort) 여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방식 분할 정복 알고리즘 활용 자료를 최소 단위의 문제까지 나눈 후에 차례대로 정렬하여 최종 결과를 얻어냄 top-down 방식 시간 복잡도 : O(n log n) 병합 정렬 과정 [69, 10, 30, 2, 16, 8, 31, 22] 를 병합 정렬하는 과정 분할 단계 : 전체 자료 집합에 대하여, 최소 크기의 부분집합이 될 때까지 분할 작업을 진행 병합 단계 : 2개의 부분집합을 정렬하면서 하나의 집합으로 병합 8개의 부분집합이 1개로 병합될 때까지 반복 분할 과정 def merge_sort(arr): # 리스트 길이가 1이면 최소 단위이므로 종료 if len(arr) == 1: return ar..

n진수 2진수, 8진수, 10진수, 16진수 10진수를 n진수로 변환 원하는 타진법의 수로 나눈 뒤 나머지를 거꾸로 읽는다. 예시 (149)_10 = (10010101)_2= (95)16 = (225)_8 n진수를 10진수로 변환 (135)_8 = 1 * 8^2 + 3 * 8^1 + 5 * 8^0 = (93)_10 소수점이 있을 때 (135.12)_8 = 1 * 8^2 + 3 * 8^1 + 5 * 8^0 + 1 * 8^(-1) + 2 * 8^(-2) = (93.15625)_10 n진수간 변환 음의 정수 표현 1의 보수 부호와 절대값으로 표현된 값을 부호 비트를 제외한 나머지비트들을 0은 1로, 1은 0으로 변환한다. -6 = 1000000000000110 : 부호와 절대값 표현 -6 = 111111111..

비트 연산 비트 연산자 연산자연산자의 기능 &비트단위로 AND 연산 진행|비트단위로 OR 연산 진행^비트단위로 XOR 연산 진행 (같으면 0 다르면 1)~단항 연산자로서 피연산자의 모든 비트를 반전피연산자의 비트 열을 오른쪽으로 이동 1 &#39;, end=&#39;&#39;) a ^= key Bbit_print(a) # => a^=key ==> 00101100 print(&#39;a^=key ==> &#39;, end=&#39;&#39;) a ^= key Bbit_print(a) # => a^=key ==> 10000110 엔디안 컴퓨터의 메모리와 같은 1차원 공간에 여러 개의 연속된 대상을 배열하는 방법을 의미하며 hw 아키텍처마다 다르다. 주의 : 속도 향상을 위해 바이트 단위와 워드 단위를 변환하..

복잡도 분석 알고리즘의 효율 공간적 효율성과 시간적 효율성 공간적 효율성 : 연산량 대비 얼마나 적은 메모리 공간을 요하는 가 시간적 효율성 : 연산량 대비 얼마나 적은 시간을 요하는 가 효율성을 뒤집어 표현하면 복잡도(Complexity) 복잡도가 높을수록 효율성은 저하 시간적 복잡도 분석 하드웨어 환경에 따라 처리시간이 상이 부동소수 처리 프로세서 존재유므, 나눗셈 가속기능 유무 입출력 장비의 성능, 공유 여부 소프트웨어 환경에 따라 처리시간이 상이 프로그램 언어의 종류 운영체제, 컴파일러의 종류 이러한 환경적 차이로 인해 분석이 난해 복잡도의 점근적 표기 시간 복잡도는 입력 크기에 대한 함수로 표기, 이 함수는 주로 여러개의 항을 가지는 다항식 이를 단순한 함수로 표현하기 위해 점근적 표기(Asym..

트리 개념 비선형 구조 원소들 간에 1:n 관계를 가지는 자료구조 원소들 간에 계층관계를 가지는 계층형 자료구조 상위 원소에서 하위 원소로 내려가며 확장되는 트리(나무)모양의 구조 정의 한 개 이상의 노드로 이루어진 유한 집합이며 다음 조건을 만족 노드 중 최상의 노드는 루트(root) 나머지 노드들은 n(>=0)개의 분리 집합 T1, ... , TN으로 분리 가능 이들 T1, ... , TN은 각각 하나의 트리로 간주 가능하며(재귀적 정의) 루트의 부 트리(subtree)라고 함 용어 설명 노드(node) - 트리의 원소 트리 T의 노드 - A, B, C, D, E, F, G, H, I, J, K 간선(edge) - 노드를 연결하는 선, 부모 노드와 자식 노드를 연결 루트 노드(root node) - ..