puravida

1. 문제의 종류 ① 문제의 종류 - 풀 수 있는 문제와 풀 수 없는 문제로 나뉨. - 현실적인 시간안에 풀 수 없는 문제는 근사해를 구하는 것을 목표로 할 수 밖에 없음 - NP 완전 문제 : 현실적인 시간에 풀 수 없다 추정되면서 서로 강력한 연관성을 가진 특이한 문제군에 관한 것. ② 현실적인 시간 - 다항식 시간을 의미 (= 현실적인 시간) > 문제의 크기가 n이면 그 문제를 푸는데 n의 다항식에 비례하는 시간이 드는 알고리즘 > 어떤 문제가 다항식 시간에 해결되면 현실적인 시간에 풀 수 있다고 간주 - 비현실적인 시간 > 문제를 해결하는데 비다항식의 시간이 소요되면 현실적인 시간에 풀 수없는 경우로 간주 (지수시간, 계승시간) 2. YES/NO 문제와 최적화 문제 ① YES/NO 문제 - 결정문..

1. 원시적인 매칭 방법 ① 문자열 매칭 - 텍스트 문자열(apple)이 패턴 문자열(pl)을 포함하고 있는 지 알아보는 것. - db검색, dna 정보검 ② 원시적인 매칭 - 본문의 길이 n, 패턴의 길이 m -> n*m번의 비교 수행해야 하므로 느림 - 수행시간 : O(nm) - 어떻게 불일치가 일어났는지 개의치 않고 무조건 한칸씩 이동해 비교함. - 오토마타를 이용하는 매칭과 KMP 알고리즘은 패턴 문자열의 앞부분과 텍스트 부분 문자열의 뒷부분의 일치 여부를 활용할 수 있도록 전처리 과정에서 준비. 2. 오토마타를 이용한 매칭 ① 오토마타를 이용한 매칭 - 문제 해결 절차를 상태간의 이동(전이)으로 나타낸 것 - 상태는 문제 해결 과정의 문맥 반영 ② 오토마타를 이용한 매칭의 예 - 상태 전이 함수..

1. 그리디 알고리즘 ① 그리디 알고리즘 - 현재 시점에서 가장 이득이 되어 보이는 해를 선택하는 행위를 반복함. - 온전한 해가 만들어질 때까지 눈 앞에 가장 좋아 보이는 선택을 반복함. - 뛰어난 결과를 도출하지 못하지만 드물게 최적해를 보장하는 경우도 있음. - 동적 계획법과 마찬가지로 최적화 문제의 답을 얻기 위해 사용 ② 그리디 알고리즘 잘 작동하는 문제 ③ 동작 과정 1. 배낭 채우기 문제 ① 문제 - 한 사람이 가지고 가는 배낭에 담을 수 있는 무게의 최대값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제. - 두가지 경우로 나누어짐 ② 동적계획법과 그리디 알고리즘 ③ 0-1 배낭 채우기 문제 -> 탐욕적 방법 사용불 ..

1. 벨만-포드 알고리즘 ① 다익스트라, 플로이드 와샬, 벨만 포드 알고리즘 - 세가지 알고리즘은 모두 최단경로 찾는데 사용되고 유용 - 주로 많이 사용하는 것은 다익스트라 알고리즘 ② 벨만-포드 알고리즘 - 가중 유향 그래프에서 최단 경로 문제를 푸는 알고리즘 - 입력 그래프 G=(V,E)에서 간선의 가중치가 음의 값을 허용하는 임의의 실수인 경우 최단 경로 알고리즘 - 다익스트라는 우선 순위 큐를 사용하여 연결된 가장 가까운 정점을 이용하여 정점의 거리를 갱신했다면, 벨만-포드는 모든 간선을 여러 번 확인하여 최단 거리를 갱신한다. - 벨만 - 포드 알고리즘은 가중치가 음수인 경우도 허용하지만, 음수 가중치가 사이클을 이루고 있는 경우 작동하지 않음. ③ 벨만- 포드 알고리즘에 대한 전제조건 - 최단..

1. 플로이드 와샬 알고리즘 ① 플로이드 와샬 알고리즘 : 최단 경로를 구하는 알고리즘인 플로이드 와샬 알고리즘은 가능한 모든 노드 쌍들에 대한 최단 거리를 구하는 알고리즘 - 그래프에서 모든 정점 사이의 최단거리(4)를 구하기 위한 알고리즘 ② 다익스트라 알고리즘과 플로이드 와샬 알고리즘 비교 ③ 그래프의 탐색 방법 2. 플로이드 와샬 알고리즘의 적용방법 ① 플로이드 와샬 알고리즘 ③ 플로이드 와샬 알고리즘 수행시간 -> 모든 정점 간 경로의 최소 비용을 구하는 것은 O(|V^3|)의 시간 복잡도 가짐 ④ 이행폐쇄 : 거쳐서 갈 수 있는 모든 곳을 직접 가는 간선으로 연결한 그래프 - 간선의 추가를 통해 대부분의 노드들이 인접 노드로 바뀌게 되며 인접 행렬로 표현하는 것이 편리 3. 플로이드 와샬 알고..

1. 다익스트라 알고리즘 ① 최단 경로 문제 - 최단 경로 문제의 구분 : 시작점과 도착점의 수에 따라 구분 ◆ 단일 쌍 최단 경로 : 한 출발점에서 한 목적지로 가는 최단경로 ◆ 단일 출발 최단 경로 : 출발점 1개 목적지 여러개일 때 각각의 여러 종점까지의 최단경로 ◆ 단일 도착 최단 경로 : 출발지 여러개 목적지 1개일때 각각의 출발지에서 종점까지의 최단경로 ◆ 전체 쌍 최단 경로 : 전체 쌍 각각의 출발-목적지 쌍들 사이의 최단 경로 구하기 - 다익스트라 알고리즘 : 모든 간선 가중치가 음이 아닌 일반적인 경우 (양수) - 음의 가중치가 존재하는 경우 : 벨만 - 포드 알고리즘 -> 음의 가중치는 허용하지만 가중치 합이 음인 사이클은 절대 허용 X ② 다익스트라 알고리즘 - 어떠한 간선도 음수값을..

1. 경로의 존재 ① 경로의 존재 - 임의의 정점에서 다른 정점으로의 경로가 존재한다 : 직, 간접적인 경로 모두 의미 ② 도달행렬 - 방향 그래프에서 정점 간 경로의 존재 여부를 행렬로 표현한 것 - A*를 도달행렬이라고 하고 행렬 A에 대한 거듭제곱 - 부울 곱 연산, 합 - 부울 합 연산 - 각각의 정점에서 다른 정점으로가는 경로가 존재하는 지 여부를 알려줌. 2. 최단 경로 ① 최단 경로 - 빠른 길을 어떻게 찾을 것인가? -> 짧다는 것은 단지 물리적인 거리 뿐 아니라 시간 거리, 비용 거리 등 다양한 기준이 적용될 수도 있음. ② 최단 경로의 조건 - 간선 가중치가 있는 유향 그래프 - 무향 그래프는 각 간선에 대해 양쪽으로 유향 간선이 있는 유향 그래프로 생각할 수 있음 -> 즉 무향 간선(..

1. 위상 정렬 ① 비순환 방향 그래프 (공정이랑 비슷하네) - 방향 그래프이면서 사이클이 없는 그래프 ② 위상 정렬 - 처리해야 할 여러가지 일들이 있고, 이들 사이의 선후 관계가 있으면 이를 유향 그래프로 표현 가능 - 유향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것 - 정렬의 순서는 유향 그래프의 구조에 따라 여러 개의 종류가 나올 수 있음 - 위상 정렬은 사이클이 있어서는 안됨 - 위상 정렬 알고리즘이란? 순서가 정해져있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘 - ex) 대학의 선수과목 => 각 업무를 수행하기 위한 순서를 제공! - 조건 : 사이클이 없는 유향 그래프 - 진입 간선 : 유향 그래프에서 한 정점으로 들..

1. 최소 신장 트리 ① 신장 트리 - 그래프 G의 신장 트리는 정점 집합 V를 그대로 두고 간선을 |V|-1개만 남겨 트리가 되도록 만든 것! - 너비우선 트리와 깊이 우선 트리도 신장 트리임 - 간선들의 가중치를 갖는 그래프에서 간선 가충치의 합이 가장 작은 트리를 최소 신장 트리라고함. ② 최소 신장 트리 - 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치 합이 최소인 신장 트리 - 프림 알고리즘/ 크루스칼 알고리즘 - 조건 : 무향 연결 그래프(모든 정점 간에 경로가 존재하는 그래프) 2. 프림 알고리즘(힙 이용) ①프림 알고리즘 - 집합 S를 공집합에서 시작하여 모든 정점을 포함할 때까지 키워나감 - 연결된 정점들과 연결된 모든 간선들 중 가중치가 가장 작은 간선 선택 ② 프림 알고..

1. 트리 탐색 ① 트리 순회 - 트리 내의 모든 노드를 오직 한 번씩 방문하는 방법 -> 전위 순회/ 중위 순회/후위 순회 ②전위 순회 ③ 중위 순회 ④ 후위 순회 2. 너비 우선 탐색 (큐 이용) ① 그래프 순회 - 하나의 정점에서 시작하여 그래프에 있는 모든 정점을 한번씩 방문하여 처리하는 연산 - 트리 순회와 달리 일반적인 그래프 순회에서는각 정점들을 한 번 이상 방문하는 경우도 있음 - 그래프에서는 다른 모든 정점들을 연결시켜주는 트리의 루트 같은 정점이 존재하지 않을 수도 있음. ② 그래프에서 모든 정점 방문하기 - 임의의 정점 선택하여 탐색하는 방법보다는 시작점을 기준으로 일정한 방향으로 탐색하는 것이 효율적 - 너비우선 탐색 / 깊이 우선 탐색 ③ 너비 우선 탐색 - 노드들을 동심원의 형태..