알고리즘 메모장

[Brute Force]

가능한 모든 경우의 수를 만들어보고 탐색하는 방법.

가능한 모든 경우의 수를 알아야함 => 경우의 수가 너무 많으면 불가

[BFS]

1.상태의 개수: 1초안에 나올 정도로 작아야함.

2.'최소'를 구하는 문제

3.상태와 상태를 연결하는 간선의 가중치가 모두 1.

0.graph & check 배열 정의

1.시작을 '큐'에 넣는다.

while(!q.empty()){

q.pop()

q.push(다음 정점)

if(!check[정점] && map[][] == 1){

check[정점] = true;

...

}

}

- check[]로 각 노드 1/0(true/false)

- 또는, dist[]로 각 노드까지의 거리 메모

[DFS]

1)

'재귀함수' 사용 => Stack을 사용하는 경우는 극히 일부.

0.graph & check 배열 정의

void dfs(int start, int size){

    cout << start << " ";

    s.push(start); // 시작점을 스택에 넣음

    check[start] = true; // 지나갔으니 체크!

    for(int i=1; i<=size; i++){

        if(a[start][i] && !check[i]){ // 시작점이랑 연결된 곳 중 한 곳을 정한다

            check[i] = true; // 지나간다!

            dfs(i,size); // 그곳에서 이걸 반복해나간다

            s.pop(); // 갔다왔으면 스택에서 뺀다!

        }

    }

}

2) 가장 일반적

int dx[] = {0,0,-1,1};

int dy[] = {-1,1,0,0};

void dfs(int x, int y){

    map[x][y] = 1;

    visit[x][y] = 1;

    //

    for(int i=0; i<4; i++){

        for(int j=0; j<4; j++){

            int nx = x + dx[i];

            int ny = y + dy[i];

            if(nx<0 || nx>=n || ny<0 || ny>=n) continue;

            if(!visit[nx][ny] && map[nx][ny] == 1) {

                //

                dfs(nx,ny,color);

                //

            }

        }

    }

}

=> 이미 확인한 부분은 visit배열로 true/false(1/0).

=> 또는, map 값을 아예 0으로 만든다.

[DP: 다이나믹 프로그래밍]

-풀이 전략

문제에서 구하려고 하는 답을 문장으로 나타낸다.

그 문장에 나와있는 변수의 개수만큼 메모하는 배열을 만든다.

다이나믹 프로그래밍에서 각 문제는 한 번만 풀어야한다.

따라서, 정답을 한 번 구했으면, 정답을 어딘가에 메모한다.

이 메모하는 것을 코드의 구현에서는 배열에 저장하는 것으로 할 수 있다.(Memorization)

ex) memo[n] = n번째 피보나치 수

int memo[100];

int fibonacci(int n){

if(n<=1) return n;

else

if(memo[n] > 0) return memo[n];

memo[n] = fibonacci(n-1) + fibonacci(n-2);

return memo[n];

}

*문제 풀이 전략

• 문제에서 구하려고 하는 답을 문장으로 나타낸다.
• 예) 피보나치 수를 구하는 문제
• N번째 피보나치 수
• 이제 그 문장에 나와있는 변수의 개수만큼 메모하는 배열을 만든다.
• Top-down인 경우에는 재귀 호출의 인자의 개수
• 문제를 작은 문제로 나누고, 수식을 이용해서 문제를 표현해야 한다.

-큰 문제를 작은 문제로 나눠서 푸는 알고리즘.

1.Overlapping Subproblem

:큰 문제와 작은 문제를 같은 방법으로 풀 수 있다.

:문제를 작은 문제로 쪼갤 수 있다.

2.Optimal Substructure

:문제의 정답을 작은 부분에서 찾을 수 있을 때

-푸는 방법은 크게 두가지

<Top-down>

1.문제를 작은 문제로 나눈다.

2.작은 문제를 푼다.

3.작은 문제를 풀었으니, 이제 문제를 푼다.

=>재귀호출로 쉽게 풀 수 있다.

<Bottom-up>

1.문제를 크기가 작은 문제부터 차례대로 푼다.

2.문제의 크기를 조금씩 크게 만들면서 문제를 점점 푼다.

3.작은 문제를 풀면서 왔기 때문에, 큰 문제는 항상 풀 수 있다.

4.그러다보면, 언젠가 풀어야 하는 문제를 풀 수 있다.

ex)

int d[100];

int fibonacci(int n){

d[0] = 0;

d[1] = 1;

for(int i=2; i<=n; i++){

d[i] = d[i-1] + d[i-2]; // 식을 세우는 것이 제일 중요***** => 식을 못찾으면 못품.

}

return d[n]; // 정답 = d[n]

}

[재귀함수&백트래킹]

1.재귀함수를 잘 설계해야 한다.

2.백트래킹의 경우...

-상태를 먼저 셋팅

-다음으로

-되돌아 왔을 때, 셋팅 이전으로 되돌린다.(백트래킹)

ex) 재귀함수 'go'가 있을때,

status = true;

go(x+1)

status = false;

[그리디 알고리즘]

최적의 답을 구하는 알고리즘으로 여러 경우 중 하나를 선택하는 매순간 마다 그 때 최적인 것을 골라 최종 답을 도출함.

ex) N원의 돈을 만드는 지페 최소 개수. K원을 받았을 때 거스름돈 최소 개수.

[스택]

stack<int> s;

[큐]

queue<int> q;