• 동적 계획법
    - Top-down
    1. 문제를 작은 문제로 나눈다.
    2. 작은 문제를 푼다.
    3. 작은 문제를 풀고, 문제를 푼다.(큰 문제를 풀어 간다.)

    * CODE - 피보나치
     : 트리로 생각하자

    int memo[100];
    int fibonacci(int n) {
    	if (n <= 1) {
    		return n;
    	}
    	else {
    		memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
    		return memo[n];
    	}
    }
    

     : memorization을 이용하면 반복을 줄일 수 있다! 


    int memo[100];
    int fibonacci(int n) {
    	if (n <= 1) {
    		return n;
    	}
    	else {
    		if (memo[n]) {
    			return memo[n];
    		}
    		memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
    		return memo[n];
    	}
    }
    

     
    - Bottom-up
    1. 문제를 크기가 작은 문제부터 차례대로 푼다.
    2. 문제의 크기를 조금씩 크게 만들면서 문제를 점점 푼다.
    3. 작은 문제를 풀면서 왔기 때문에, 큰 문제는 항상 풀 수 있다.
    4. 반복하면 언젠간 풀어야 하는 문제를 풀 수 있다.

    * CODE - 피보나치

    int dp[100];
    int fibonacci(int n) {
    	dp[0] = 1;
    	dp[1] = 1;
    	for (int i = 2; i <= n; i++) {
    		dp[i] = dp[i - 1] + dp[i - 2];
    	}
    	return dp[n];
    }


'Algorithm' 카테고리의 다른 글

Dynamic Programming  (0) 2016.04.04
에라토스테네스의체  (0) 2016.03.22
알고리즘 - 보간 탐색  (0) 2015.11.14
알고리즘 - 이진 탐색  (0) 2015.11.14
알고리즘 - 순차 탐색  (1) 2015.11.14
알고리즘 - 위상 정렬  (0) 2015.11.14
  • m부터 n까지의 소수를 구하는 문제 


    #define N 1000000
    #include <iostream>
    using namespace std;
    
    bool prime[N+1]; // true 소수 x, false 소수 o
    
    int main()
    {
    	prime[0] = prime[1] = true;
    	for (int i = 2; i*i <= N; i++) {
    		if (prime[i] == false) {
    			for (int j = i*i; j <= N; j+=i) {
    				prime[j] = true;
    			}
    		}
    	}
    	
    	int m, n;
    	cin >> m >> n;
    	cin.sync_with_stdio(false);
    
    	for (int i = m; i <= n; i++) {
    		if (prime[i] == false)
    			// cout << i << endl;
    			// cout은 stdio와의 동기화 때문에 느림 -> sync_with_stdio를 false
    			// endl을 하게되면 매번 출력 버퍼를 비움 -> '\n'으로 개행
    			cout << i << "\n";
    	}
    	return 0;
    }
    


'Algorithm' 카테고리의 다른 글

Dynamic Programming  (0) 2016.04.04
에라토스테네스의체  (0) 2016.03.22
알고리즘 - 보간 탐색  (0) 2015.11.14
알고리즘 - 이진 탐색  (0) 2015.11.14
알고리즘 - 순차 탐색  (1) 2015.11.14
알고리즘 - 위상 정렬  (0) 2015.11.14

- interpolation search

- 사전이나 전화번호부를 탐색하는 방법과 같이 탐색 키가 존재할 위치를 예측, 비례식 이용


- 탐색 위치 = (k-list[low]) / (list[high]-list[low] * (high-low) + low

- 시간복잡도: 



'Algorithm' 카테고리의 다른 글

Dynamic Programming  (0) 2016.04.04
에라토스테네스의체  (0) 2016.03.22
알고리즘 - 보간 탐색  (0) 2015.11.14
알고리즘 - 이진 탐색  (0) 2015.11.14
알고리즘 - 순차 탐색  (1) 2015.11.14
알고리즘 - 위상 정렬  (0) 2015.11.14

- binary search

- 정렬된 배열에서의 탐색

- 재귀 호출, 반복을 이용하여 구현 가능 

- 시간복잡도: 


'Algorithm' 카테고리의 다른 글

에라토스테네스의체  (0) 2016.03.22
알고리즘 - 보간 탐색  (0) 2015.11.14
알고리즘 - 이진 탐색  (0) 2015.11.14
알고리즘 - 순차 탐색  (1) 2015.11.14
알고리즘 - 위상 정렬  (0) 2015.11.14
알고리즘 - 플로이드  (0) 2015.11.14

- sequential search

- 정렬여부 상관없이 비슷한 성능

- 시간복잡도: 


- 개선된 순차 탐색
 : 비교 횟수를 줄이는 방법

int seq_search2(int key, int low, int high) 
{
    int i;
    list[high+1] = key;
    for(i=low; list[i] != key; i++) // 키 값을 찾으면 종료
        ;
    if(i==(high+1)) return -1; //탐색 실패
    else return i;             //탐색 성공
}


'Algorithm' 카테고리의 다른 글

알고리즘 - 보간 탐색  (0) 2015.11.14
알고리즘 - 이진 탐색  (0) 2015.11.14
알고리즘 - 순차 탐색  (1) 2015.11.14
알고리즘 - 위상 정렬  (0) 2015.11.14
알고리즘 - 플로이드  (0) 2015.11.14
알고리즘 - 다익스트라  (0) 2015.11.14
  1. 2021.06.14 23:29

    왜 시간복잡도가 n이 아니고 n제곱이죠?

- topological sort

- 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것

- 진입 차수가 0인 정점을 선택하고, 선택된 정점과 여기에 부속된 모든 간선을 삭제 -> 반복

- 사이클이 있는 경우 위상정렬 불가

'Algorithm' 카테고리의 다른 글

알고리즘 - 이진 탐색  (0) 2015.11.14
알고리즘 - 순차 탐색  (1) 2015.11.14
알고리즘 - 위상 정렬  (0) 2015.11.14
알고리즘 - 플로이드  (0) 2015.11.14
알고리즘 - 다익스트라  (0) 2015.11.14
알고리즘 - 프림  (0) 2015.11.13

Floyd

- 최단 경로 알고리즘

- 모든 정점 사이의 최단 경로를 구하려면 다익스트라의 알고리즘을 정점의 수만큼 반복 실행, But 모든 정점 사이의 최단 거리를 구하려면 더 간단한 알고리즘으로 플로이드 알고리즘

- 2차원 배열을 이용하여 3중 반복을 하는 루프로 구성

- distance 배열없이 그래프를 갱신함.

- 다익스트라로 모든 정점의 쌍으로 최단 경로를 구하려면 알고리즘 n번 반복, 전체 복잡도는 


- 시간복잡도: 

'Algorithm' 카테고리의 다른 글

알고리즘 - 순차 탐색  (1) 2015.11.14
알고리즘 - 위상 정렬  (0) 2015.11.14
알고리즘 - 플로이드  (0) 2015.11.14
알고리즘 - 다익스트라  (0) 2015.11.14
알고리즘 - 프림  (0) 2015.11.13
알고리즘 - 크루스칼  (0) 2015.11.13

- Dijkstra

- 최단 경로(shortest path) 알고리즘


- 하나의 시작 정점으로부터 모든 다른 정점까지의 최단 경로를 찾는 알고리즘

- distance[w] = min(distance[w], distance[u] + weight[u][w])

- 시간복잡도
  : 선형탐색일 경우 

  : 이진 힙을 이용하면 실행 시간은 O((m+n)\log n) 시간이 되고, 피보나치 힙을 통해 O(m + n \log n) 시간까지 개선할 수 있다.



'Algorithm' 카테고리의 다른 글

알고리즘 - 위상 정렬  (0) 2015.11.14
알고리즘 - 플로이드  (0) 2015.11.14
알고리즘 - 다익스트라  (0) 2015.11.14
알고리즘 - 프림  (0) 2015.11.13
알고리즘 - 크루스칼  (0) 2015.11.13
알고리즘 - 너비 우선 탐색  (0) 2015.11.13

- Prim

-
 시작 정점에서부터 출발하여 신장 트리 집합을 단계적으로 확장해나가는 방법, 정점 선택 기반

- 시작 단계에서는 시작 정점만이 신장 트리 집합에 포함

- 앞 단계에서 만들어진 신장 트리 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장

- 시간복잡도 

 => 희박한 그래프를 대상으로 할 경우에는 크루스칼의 알고리즘이 적합, 밀집한 그래프의 경우에는 프림 알고리즘이 유리

'Algorithm' 카테고리의 다른 글

알고리즘 - 플로이드  (0) 2015.11.14
알고리즘 - 다익스트라  (0) 2015.11.14
알고리즘 - 프림  (0) 2015.11.13
알고리즘 - 크루스칼  (0) 2015.11.13
알고리즘 - 너비 우선 탐색  (0) 2015.11.13
알고리즘 - 깊이 우선 탐색  (0) 2015.11.13

- Kruskal

- 탐욕적인 방법(greedy method), 간선 선택 기반  

- 간선들을 가중치의 오름차순으로 정렬, 사이클을 형성하지 않는 간선을 찾아서 현재의 최소 비용 신장 트리의 집합에 추가

- 시간복잡도 


- union-find 연산 (사이클, 집합)


  

#define MAX_VERTECS 100

int parent[MAX_VERTECS]; // 부모 노드
int num[MAX_VERTECS]; // 각 집합의 크기

// 초기화
void set_init(int n)
{
	int i;
	for(i=0; i<n; i++) {
		parent[i] = -1;
		num[i] = 1;
} } // vertext가 속하는 집합을 반환한다. int set_find(int vertex) { int p, s, i = -1; for(i = vertex; (p=parent[i])>=0; i=p) // 루트 노드까지 반복 ; s = i; // 집합의 대표 원소(최상위 부모노드) for(i = vertex; (p=parent[i])>=0; i=p) parent[i] = s; // 집합의 모든 원소들의 부모를 s로 설정 return s; } // 두 개의 원소가 속한 집합을 합친다. void set_union(int s1, int s2) { // 연산량을 줄이기 위해 정점의 개수가 적은 트리의 루트가 큰 트리의 루트를 가리키도록 함 if(num[s1] < num[s2]) { parent[s1] = s2; num[s2] += num[s1]; } else { parent[s2] = s1; num[s1] += num[s2]; } }


'Algorithm' 카테고리의 다른 글

알고리즘 - 다익스트라  (0) 2015.11.14
알고리즘 - 프림  (0) 2015.11.13
알고리즘 - 크루스칼  (0) 2015.11.13
알고리즘 - 너비 우선 탐색  (0) 2015.11.13
알고리즘 - 깊이 우선 탐색  (0) 2015.11.13
알고리즘 - 정렬 알고리즘 비교  (2) 2015.11.12

+ Recent posts