본문 바로가기

분류 전체보기377

[알고리듬] 시간복잡도 분석(피보나치, Peasant, Hanoi, Quick sort, Merge sort) 지난주는 시간복잡도, 알고리즘을 수행하는데 걸리는 시간(running time) 어떻게 측정하는가? 알고리즘 자체가 추상적인 상태이므로, 시간 복잡도를 이용하자. 시간 복잡도 분석 = 연산의 개수 세기 >> (시간복잡도 = n에 대한 함수) n에 대한 개수를 정확하게 세는 것은 어렵다. 따라서 최악의 경우를 따짐 -> 최대 개수에 대한 상한을 분석 ◇예제. 피보나치 수열◇ : O(mn)만큼의 한 자릿수 곱셈 (안쪽 for문) >> ppt 내용 인덱스 범위 지정이 잘못됐음. if문을 써서 i 안쪽 for 문 : 상수 개+1번의 상한을 갖게 됨. // O(k+1)를 넘지 않는 빅오를 갖게 된다. >> 안쪽 for문에서 hold += hold*X[i][j]의 값이 O(mn)의 값을 가진다. 그 이유는 i와 j.. 2020. 5. 8.
[알고리즘] 시간복잡도란? 빅오표기법을 사용하는 이유? 1. 시간 복잡도 2. 빅오 표기법 3. 정렬 알고리즘 시간 복잡도(Time Complexity) 시간 복잡도는 왜 필요한가? 알고리즘 中 최선의 방법을 찾기 위하여. (학교 수업을 바탕으로 생각한 그적 피셜) 우리는 알고리즘의 효율성 즉, 실행시간은 컴퓨터가 해당 알고리즘을 실행하는 속도에 의존적이다. 시간 복잡도를 이용해 최선의 방법을 찾음으로써 알고리즘의 효율성을 따질 수 있다. 알고리즘 실행속도는 코드, 언어, 컴파일러, 컴퓨터의 스펙 등 다양한 요인에 따라서 수행 시간이 달라진다. 그럼 어떻게 알고리즘 실행 시간을 측정할 수 있을까? 매 시간 알고리즘의 정확한 실행 시간을 측정하기 어렵기 때문에 우리는 알고리즘의 환경적 요인들을 날려버린다. 알고리즘의 환경적 요인을 날려버린 상황에서 우리는 알고.. 2020. 5. 8.
[이산수학] 최소 신장트리와 프림/크루스칼 알고리즘 트리는 그래프의 유형이다. 1. 무방향 2. 모든 정점 연결 3. 비순환 루트 트리(Rooted Tree, top) : 지정된 한 개의 정점을 갖는다. 뿌리 보다는 top이라고 생각하자. (->정상에 있는 정점) 루트 트리와 관련된 용어 // 정점 - 부모 정점 : 바로 위 정점 - 조상 정점 : 위에 있는 정점 모두 - 자식 정점 : 바로 아래 정점 - 후손 정점 : 아래 있는 정점 모두 - 형제 정점 : 같은 부모 - 단말 정점 또는 잎 : 터미널 vertices, 마지막 노드 - 비단말 또는 내부 정점 : 단말 정점을 제외한 것 - 부 트리 ** 만약 단말 정점인데 부트리를 구하라? >> 본인 자신 정점뿐 m-가지 루트 트리 : 자식이 최대 m개(m=2이면 이진트리) 포화 m-가지 트리에는 각각 m.. 2020. 5. 6.
[이산수학] 방향그래프, 그래프 탐색과 구현 11. 방향그래프 12. 강한연결요소 13. 비순환그래프 14. 그래프탐색 15. 그래프구현 --------------------------------------------------------------------------------- ⑪ 방향그래프 : 간선의 끝에 방향을 추가 G = (V, E) V : 노드(nodes)라고 부른다. E : 아크(arcs)라고 부른다. //★관계를 순서쌍으로 표현한다.★ 예제) G = (V,E) V = {1,2,3,4} E = { (1,2), (2,1), (2,5), (3,1), (3,4), (4,2), (5,4), (5,5) } 차수 : 정점에 연결된 간선의 수 //사람으로 따지면 인기인 고립된 사람으로 취급함 deg = indeg+outdeg - indeg(v) .. 2020. 5. 6.
[이산수학] 외판원문제(TSP문제)와 그래프 동형 6. TSP 문제 7. 매칭 8. 그래프동형 9. 평면그래프 10. 그래프색칠 ----------------------------------------------------------------------------------------- ⑥ TSP(Traveling Salesman Problem) : 외판원 방문 문제 : 모든 도시를 한 번만 방문하고, 출발점으로 다시 돌아오는 최단 경로 >> 최소비용의 헤밀턴 사이클 찾기 ★TSP의 어려움★ : 도시 수가 많을수록 최적의 해를 계산하는 데에 엄청난 시간이 소요된다. 해밀턴 순환의 총 수 = (n-1)! / 2 "팩토리얼 증가" 해결 방안 타협 >> 품질 vs 비용 Naive algorithm vs Greedy algorithm (숲전체) (나무) Be.. 2020. 5. 6.
[이산수학] 그래프의 종류와 오일러/해밀턴 경로 1. 그래프소개 2. 부분그래프 3. 연결그래프 4. 이동경로 5. 최단경로찾기 --------------------------------------------------------------------------------- ① 그래프 모델링 : 주어진 문제를 그래프로 표현하여 해결 (정점과 정점을 잇는 간선으로 표현) 주요 구성 요소 - 정점(꼭짓점) - 간선(모서리) G = (V,E) V = {1,2,3,4,5,6} E = {{1,2}, {1,5}, {2,3}, {2,5}, {3,4}, {4,5}, {4,6}} // 집합으로 나타내면 '연결'이 되어 있음. // 순서쌍으로 연결되어 있으면 '방향' 그래프로 표현 가능 다중 간선 : 두 정점을 연결하는 간선의 수가 두 개 이상인 경우 (루프 : 자기에.. 2020. 5. 6.

티스토리툴바