기억하고싶은것들

• Backtracking에 대한 정의
• DFS와 비교 

백트래킹은 '조합 알고리즘 문제'에 대해 모든 가능한 해를 나열하는 것이다.

모든 조합의 수를 살펴보는 것인데 단 조건이 만족하는 경우에만 해당된다.

즉 주어진 조합을 탐색 시 답이 될만한지 판단하고 그렇지 않으면 해당 조건은 탐색을 멈추고 가지치기를 하는 것이다.

완전 탐색에서 좀 더 효율적으로 유망성을 판단하고 가지치기를 수행한다.

완전 탐색 : 여러 개의 solution을 가진 문제에서, 모든 solution을 탐색하는 전략

DFS와 비교 

대표적인 완전 탐색 방법으로는 DFS (Depth First Search, 깊이 우선 탐색)가 있다.

DFS는 현재 지점에서 방문할 곳이 있으면 재귀 호출 또는 Stack을 이용해서 계속 이동한다. 

하지만 DFS는 모든 노드를 방문하기 때문에 굳이 목표지점이 있지 않는 경로로 빠져서 비효율적인 탐색을 수행할 수도 있다.

백트래킹은 DFS에 가지치기 (Pruning)를 통해 불 필요한 탐색을 제한하는 완전 탐색 기법이다.

가지치기를 얼마나 잘하느냐에 따라서 효율이 극대화될 수 있는 방법이다.

정리하자면, 백트래킹은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것이다.

• dynamic programming에 대한 개념 설명
• dynamic programming을 적용하기 위한 조건 
• dynamic programming의 특징
• dynamic programming의 접근법

Dynamic Programming은 보통 DP라고 줄여 쓰는것을 볼 수 있다.

이름만 봤을때는 뭔가 엄청나게 대단하고 복잡한 알고리즘일것 같은데, 실제 해당 내역을 공부하면 이름이랑 뭔가 맞지 않는다는게 느껴진다.

보통 인터넷을 찾아봤을때, Dynamic Programming의 정의는 아래와 같다.

복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법 

개념은 그렇게 어렵지 않고, 받아들일수 있다.

그러면, 이러한 DP를 어떠한 상황에 적용할 수 있는지 알아보자.

가장 대표적인 예시로는 피보나치 수열이 있다. 

간단하게 피보나치 수열에 대한 정의를 보면 아래와 같다.

첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열 이다.
처음 여섯 항은 각각 (0), 1, 1, 2, 3, 5, 8이다.
편의상 0번째 항을 0으로 두기도 한다.

DP라는 개념이 등장하기 전에는 대부분 해당 문제를 재귀적으로 해결하였다. 

아래는 예시 코드이다.

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

하지만 해당 방법으로 문제를 풀게 된다면, 반복되는 값들을 반복적으로 구한다는 문제가 있다. 

아래의 그림에서 트리에서 반복적으로 fib(5) 이하의 노드들을 계산하게 된다. 

한번만 계산해 놓고 해당 값을 다시 만나면 이전에 계산해 놓은 값을 가져다가 쓰기만 하면 계산 시간을 효율적으로 줄일 수 있게된다.

이러한 점을 반영하여서 DP의 적용 조건과 특징을 살펴보자.

DP의 적용 조건

• 부분문제 반복 ( Overlapping Subproblem )
  • 피보나치 수열과 같이  f(n) = f(n-1) + f(n-2) 와 같이 
    어떠한 문제가 여러개의 부분 문제로 쪼개 질 수 있고, 해당 부분 문제가 또 다시  재귀적으로 부분 문제로 쪼개질 수 있는 것
• 최적 부분구조 ( Optimal Substructure )
  • 피보나치 수열과 같이 f(n) = f(n-1) + f(n-2)와 같이
    작은 부분 문제에서 구한 최적의 답으로 합쳐진 큰 문제의 최적의 답을 구할 수 있는 것

( 해당 조건은 뭔가 전문적인 단어들이 들어가서 어렵게 표현된 것처럼 보이는데, DP의 핵심은 "복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 것" 이다. 이 핵심을 풀어서 전문적으로 설명해 놓은게 조건이라고 생각하자.)

DP의 특징으로는 Memorization이다.

반복적으로 등장하는 계산을 기억해 두었다가, 해당 계산이 다시 등장할때, 재계산을 하지 않고 기억해 두었던 값을 가져다 사용하는 것이다. 

위의 피보나치 수열 그래프에서 반복적으로 등장하는 fibo(5), fibo(4) ... 값들을 기억하고 사용하면 된다. 

접근법

이제 개념적인 부분과 특징을 알아 보았으니 실제로 문제를 만났을때 어떻게 접근해야하는지에 대해서 알아보도록 하자.

크게 2가지 방법이 있다. 

• Top-Down
  • 재귀로 해결 하는 대부분의 방식
  • 큰 문제를 해결 하기 위해 작은 문제로 나누고, 해당 값이 아직 계산되지 않은 경우 더 작은 값으로 나누며 값을 찾아가는 방식
  • ( 예시는 위의 fibonacci 코드 )
• Botton-up
  • 작은 문제에서 부터 하나씩, 하나씩 값을 찾아가는 방식
  • ( 예시는 아리의 코드 )

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

Flood Fill 알고리즘에 대한 정의를 찾아보면 보통 아래와 같이 나온다.

주어진 시작점으로부터 연결된 영역들을 찾는 알고리즘 
다차원 배열의 어떤 칸과 연결된 영역을 찾는 알고리즘

주변에서 해당 알고리즘을 사용하는 케이스는 보통 아래와 같다

• 그림판 프로그램의 "채우기" 기능 - 해당 영역의 주변에 모든 셀을 같은 색으로 색칠
• 지뢰 찾기 프로그램 - 특정 셀을 클릭 시 주변에 지뢰가 없는 모든 셀을 찾아 줌

Flood Fill 알고리즘은 보통 DFS 알고리즘을 이용하여 재귀 함수를 통해 구현하거나

BFS 알고리즘을 이용하여 Queue를 이용하여 구현한다.

이번에는 2차원 배열에서 DFS를 사용하여 Flood Fill 관련 알고리즘 문제를 푸는 예제를 하나 보도록 하겠다. 

DFS는 2차원 배열의 경우에서 인접한 배열을 ( 위 - 오른쪽 - 아래 - 왼쪽 )의 순서로 방문한다고 가정하자.

그러면 해당 내용을 간단하게 의사 코드로 표현하면 아래와 같다.

void DFS_array( int x, int y) {

	visit(x,y);
    
    if (isValid(x, y +1)) { // 위의 배열 방문 
    	DFS_array ( x, y+1);
    }
    if (isValid(x+1, y)) { // 오른쪽 배열 방문 
    	DFS_array ( x+1, y);
    }
    if (isValid(x, y -1)) { // 아래 배열 방문 
    	DFS_array ( x, y-1);
    }
    if (isValid(x-1, y)) { // 왼쪽 배열 방문 
    	DFS_array ( x-1, y);
    }
}    

이동 순서 ( 위 - 오른쪽 - 아래 - 왼쪽 ) 

 9번에서 4방향 모두 방문한 상태로 return 

 8번에서 - > 10번으로 이동하여 계속 DFS 진행 

이러한 방식으로 기본적으로 2차원 배열에서 DFS가 어떻게 동작하는지 파악하였으니 

이러한 내용을 응용하여 Flood Fill 알고리즘에 적용해 보도록 하자

해당 그림에서 검은색은 벽이고 하얀 부분을 방문 가능한 영역이라고 했을 때, 

최종적으로 방문 할 수 있는 영역의 개수를 구하는 문제를 푼다고 해보자 

    int floodFill(int[][] metrics) {
        int cnt = 0;
        for (int i = 0; i < metrics.length; i++) {

            for (int j = 0; j < metrics[0].length; j++) {

                if (isValid(metrics[i][j])) { // 벽이 아닌 영역인지 판단, 이미 방문했는지 판단
                    cnt++;
                    DFS_array(i, j);
                }
            }
        }

        return cnt;
    }

• BFS의 개념
• BFS에 대한 간단한 코드 설명 
• BFS의 장단점
• LeetCode 예시 문제 및 참고 코드

BFS ( Breadth First Search )는 너비 우선 탐색이라 불리는 알고리즘이다.

해당 알고리즘은 보통 DFS ( Depth First Search)와 많이 비교 된다. 

두 알고리즘은 모두 그래프를 탐색하는데 많이 사용된다.

그래프 탐색이란 - 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말한다.

예를 들어, 특정 도시에서 다른 도시로 이동을 할 수 있는지 탐색하는 것이 될 수 있다.

BFS는 그래프를 탐색시, 너비를 우선 해서 탐색을 하겠다는 전략이다. 

즉, 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법을 말한다.

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.

깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다.

사용하는 경우는 보통 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.

위의 설명을 코드로 나타낸 간단한 의사 코드를 보면 아래와 같을 수 있다. 

void search(Node root) {
  Queue queue = new Queue();
  root.marked = true; // (방문한 노드 체크)
  queue.enqueue(root); // 큐에 추가

  // 큐가 소진될 때까지 반복한다.
  while (!queue.isEmpty()) {
    Node r = queue.dequeue(); // 큐에서 노드 추출
    r.marked = true; // (방문한 노드 체크)
    
    // 큐에서 꺼낸 노드와 인접한 노드들을 모두 차례로 방문한다.
    foreach (Node n in r.adjacent) {
      if (n.marked == false) {
        queue.enqueue(n); // 큐에 추가
      }
    }
  }
}

BFS의 장단점은 아래와 같을 수 있다

• 장점
  • 출발 노드로 부터 목표 노드까지의 최단 경로를 보장해 준다.
• 단점
  • BFS에 비해 코드 구현이 까다롭다.
  • Queue에 노드를 저장하다 보니, 저장공간이 준비되어있어야 한다. 

예시 문제 

1161 - Maximum Level Sum of a Binary Tree ( 이진트리의 합이 가장 큰 레벨 )

joomn11.tistory.com/37

513 - Find Bottom Left Tree Value ( 트리의 가장 밑의 왼쪽 값 찾기 )

joomn11.tistory.com/39

429 - N-ary Tree Level Order Traversal ( N-ary 트리의 레벨 순서 순회 )

joomn11.tistory.com/38