-
그래프 알고리즘알고리즘 2021. 5. 31. 19:46
최소 신장 트리 (MST : Minimum Spanning Trees) 비방향 연결 그래프를 대상으로 한다. --> 연결 그래프 : 모든 정점 간의 경로가 존재하는 그래프이다 그래프의 신장 트리(spanning tree) 그래프의 정점 집합인 V와 간선 집합의 개수는 |V| - 1 개 이다. 싸이클이 없어야 한다. 그래프의 최소 신장 트리 활용 어떻게 하면 도로를 최소한으로 만들수 있는가? 최소 신장 트리 문제를 푸는 탐욕적 알고리즘 탐욕적 기준에 따라 싸이클이 생기지 않도록 연결 그래프가 되도록 간선 추가 최소 거리를 만족하는 최소 신장 트리는 유일하지 않을 수 있다. 크루스칼 알고리즘 탐욕적으로 간선을 추가하는 방식 저밀도 그래프에서 유용하다 프림 알고리즘 탐욕적으로 정점을 추가하는 방식 고밀도 그래..
-
그래프(Graph)알고리즘 2021. 5. 17. 16:52
Graph G = (V , E) G : 그래프 V : 정점(vertex)의 집합 E : 정점들을 잇는 간선(Edge)의 집합 Graph의 종류 간선의 뱡향성 유무 비방향(undirected) 그래프 == 양뱡향 방향(directed) 그래프 간선의 가중치(숫자) 유무 가중치(weighted) 그래프 비가중치 그래프 Graph 용어 경로(path) - 어떤 정점에서 다음 정점을 잇는 이음선(간선)이 존재하는 일련의 정점 - 단순 경로(simple path) : 같은 정점을 두 번 거치지 않는 경로 - 경로의 길이 : 경로상의 간선의 수 싸이클(cycle) - 어떤 정점에서 그 정점 자신으로 가는 경로 - 싸이클 존재 유무 : cyclic 그래프 vs acyclic(싸이클이 하나도 없어야 한다.) 그래프 -..
-
탐욕적 알고리즘알고리즘 2021. 5. 10. 17:34
탐욕적 기법 탐욕적 알고리즘 에서 시작, 탐욕적인 기준에 따라 아이템을 차례로 추가하여 문제의 해답이 될 까지 계속하는 기법 단계 선택 과정 기준에 따라 현제 상태(Locally)에 최적의 선택 적정성 검정 해답 점검 -> 동적 보다 쉽다. 해답이 항상 최적해를 보장하지 않는다. 그래서 증명이 필요하다. 반드시 연속 배낭문제 각 아이템을 잘라서 배낭에 넣을 수 있다. 용량을 초과하지않고 아이템 가치의 합이 최대가 되도록 담기 정렬로도 풀 수 있다. 탐욕적 알고리즘과 우선순위 큐 탐욕적 알고리즘 구현은 우선 큐를 동반한다. 큐 (Queue) Queue는 리스트라고 하는 선형 구조 만족하는 조건 FIFO(선입선출) 들어온것 : 입력 나가는것 : 삭제 Queue에서 중요한 것 입력 순서가 중요하다. 우선순위 ..
-
동적 프로그래밍알고리즘 2021. 4. 28. 21:58
최적화 문제란? 최적값을 구하거나 최적값에 해당하는 후보해답(=최적해: 정해진 답을 구하는 방법)을 구하는 문제 예) 최단경로 문제 : 한 정점에서 다른 정점으로 가는 경로들 중 가장 거리가 짧은 경로 배낭 채우기 문제 : 배낭의 용량을 초과하지 않으면서 가치를 최대로 배낭에 물건을 채우는 방법 (0-1 배낭문제 vs 연속 배낭문제 해법 무작정 알고리즘(brute-force search) 모든 가능한 경우를 탐색하여 최적화 구하기 흔히 지수시간 알고리즘 -> 가능하면 사용하지 않는 것 주로 동적프로그래밍 혹은 탐욕적 방법을 사용 두 방법 중 하나로 해결되는 경우, 알고리즘은 흔히 다차시간(polynomial time) 소요 많은 최적화 문제는, 다차시간 알고리즘을 구해지 못했고 다차시간 알고리즘이 존재하..
-
검색알고리즘 2021. 4. 5. 18:08
심볼 테이블키 심볼 테이블 키-벨류 쌍(key-value pair) 추상화 키: 검색에 사용하는 필드 밸류 : 관련(부속, 위성) 데이터(satellite data) 연산 검색: 주어진 키에 대하여 검색한 후, 해당 밸류를 반환 삽입: 키와 함께 밸류를 삽입 - 만일 키가 이미 존재하면, 밸류를 업데이트 삭제: 특정 키를 검색하여 해당 키-밸류 쌍을 삭제 선형자료구조를 이용한 심볼 테이블 구현과 검색 정렬되지 않은 연결 리스트(unordered linked list) 삽입/검색이 앞의 정의와 비슷하다. 삽입/검색의 시간복잡도 : O(n) 예) 정렬 상태를 유지하는 배열(ordered arrays) 검색: 이분검색(binary search) 이분검색의 시간복잡도: O(lg n)이다. -> 빠른 것 같지만,..
-
정렬알고리즘 2021. 3. 15. 17:03
주어진 객체(레코드, 아이템)들의 리스트를 정해진 기준으로 순서대로 나열(재배치)하는 것 숫자는 크기순으로 정렬 : 오름차순(ascending order) vs 내림차순(descending order) 문자열은 사전 순서(lexical order)로 정렬 : 대소문자 이슈 다수의 필드(속성)를 갖는 레코드의 경우, 특정 필드(들)를 정렬 기준으로 함 정렬은 컴퓨팅 인프라에서 가장 중요한 컴포넌트 중 하나이다. 대표적 정렬 알고리즘 단순하지만 비효율적인 방법 : 삽입정렬, 버블정렬, 선택정렬 복잡하지만 효율적인 방법 : 병합정렬, 퀵정렬, 힙정렬 특수한 상황에서만 사용하는 방법 : 기수정렬, 계수정렬, 버킷정렬 정렬 알고리즘의 논제 실행시간은 빨라야 한다 안정적(stable) 정렬: 값이 같은 경우 원래 ..
-
분석알고리즘 2021. 3. 10. 17:57
시간복잡도 분석 (time complexity analysis) 알고리즘의 실행시간(running time) 효율성 분석 알고리즘의 실제 실행시간을 측정하는 방법 : 실행환경의 영향을 많이 받음 시간복잡도 분석은 물리적 시간 대신 명령문의 실행 횟수를 분석 주어진 알고리즘의 실행시간은 입력(input)에 따라 달라짐 입력 크기 : 흔히 n으로 표현한다. 시간복잡도 분석 모든 경우 시간복잡도 T(n) 최악의 경우 시간복잡도 W(n) : 최대 실행 횟수 평균의 경우 시간복잡도 A(n) : 평균 실행 횟수 최선의 경우 시간복잡도 B(n) : 최소 실행 횟수 빅오 표기법 정확한 실행 횟수보다 n이 커짐에 따라 어떤 비율로 시간이 증가하는지가 중요 입력 크기 n과 상관없이 상수 번 실행되는 명령문은 무시해도 됨 ..
-
기초알고리즘 2021. 3. 8. 18:28
알고리즘 주어진 문제에 대한 답을 찾는 단계적 절차 혹은 기법 -> 프로그램에서 어떤 특정한 일을 수행하는 개별적인 모듈(module)과 유사 알고리즘의 조건 finite(우한한): 끝이 있다 deterministic(결정로적인): 같은 입력(instance)에 대해서 항상 같은 출력(값)을 주어야 한다. effective(효율적인): 빠른 시간에 적은 메모리를 사용하여 대답을 주어야 한다. 추상화(ADT) 구체화의 반대 1) 데이터 객체의 구체적인 내용 신경X 2) 데이터에 대한 연산 : 삽입, 삭제 3) 구체적인 구현 신경 예) 같은 문제를 주어질 때, 구체화 관점과 추상화 관점 구체화: 이번학기 최고 성적 추상화: n개의 정수 중 최대값 대표적 알고리즘 설계 기법 분할정복(divide-and-con..