[TIL] 2022-03-29 / 7일차

 

오늘 배운 내용

 

프로그래머스 네트워크 문제 풀이

 

코딩테스트 연습 - 네트워크

 

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

문제 설명을 보면 n 개의 컴퓨터가 있을 때, 연결되어 있는 네트워크가 몇 개인지 구하는 문제이다.

 

문제의 예제 1번의 그림을 보면 그래프 문제로 1번 컴퓨터에서 연결되어 있는 모든 컴퓨터를 탐색해야 하는 것을 떠올릴 수 있고, 이를 DFS로 해결하고자 했다.

 

처음에 문제를 풀 때 문제가 이해가 되지 않았다. 

입출력 예
n = 3
computers = [[1, 1, 0], [1, 1, 0], [0, 0, 1]]
return = 2

computers 배열의 1번째 요소는 1번 컴퓨터(정점)의 연결된 간선 정보인데, 1번 컴퓨터가 1번에 연결되어 있다고 되어 있어 문제를 이해하지 못했었다. 이렇게 표시가 된 이유는 3번 컴퓨터처럼 다른 정점과 연결된 간선이 없을 때, 하나의 네트워크가 되는 것을 찾기 위한 것으로 표시되어 있다고 이해를 한 후 문제를 풀 수 있었다.

 

n 개의 컴퓨터를 순차적으로 탐색하며 해당 컴퓨터에서 연결되어 있는 모든 컴퓨터를 탐색한 후 더 이상 탐색할 곳이 없을 때 정답 카운트를 하나 증가시킨다.

 

예를 들어 1번 컴퓨터에서 2번 컴퓨터가 연결되어 있다면 2번 컴퓨터를 기점으로 다음 컴퓨터를 탐색하는 DFS함수를 재귀적으로 호출하여 정답을 찾아간다. 컴퓨터를 찾아갈 때에는 check 배열을 통해 관리한다(check 배열에서 탐색한 컴퓨터는 true로 설정, 아닌 경우는 false).

 

function solution(n, computers) {
    let answer = 0;
    let check = Array.from({length : n}, () => false);

    for(let i=0; i<n; i++){
        if(!check[i]){
            dfs(i, n, computers, check);
            answer += 1;
        }
    }

    function dfs(startComputerNumber, n, computers, check){
        const stack = [startComputerNumber];

        while(stack.length > 0){
            const currComputerNumber = stack.pop();
            check[currComputerNumber] = true;

            for(let i=0; i<n; i++){
                if(!check[i] && computers[currComputerNumber][i]){
                    stack.push(i);
                }
            }
        }
    }
    return answer
}
// n	computers	                        return
// 3	[[1, 1, 0], [1, 1, 0], [0, 0, 1]]	2
// 3	[[1, 1, 0], [1, 1, 1], [0, 1, 1]]	1

let n = 3;
let computers = [[1, 1, 0], [1, 1, 1], [0, 1, 1]];
console.log(solution(n, computers));

---

백트래킹 알고리즘

 

백트래킹 알고리즘은 모든 경우의 수를 탐색하는 것이다. 백트래킹을 할 때에는 DFS(깊이 우선 탐색), BFS(너비 우선 탐색)을 이용한다.

 

효율을 위해 탐색하지 않아도 되는 곳은 미리 막는 것을 가지치기(Pruning)이라고 하는데, 백트래킹의 핵심은 "가지치기"이다. 가지치기를 얼마나 잘하느냐에 따라 효율성이 결정된다(불필요한 탐색을 줄이기에).

 

Javascript는 재귀 효율이 나쁘기 때문에 백트래킹을 구현할 때 재귀는 사용하지 않는 편이 좋다. DFS로 백트래킹을 구현한다면 stack을 이용하는 것이 조금 더 효율적이지만, 코딩 테스트에서는 이를 고려해 재귀를 이용하더라도 문제를 해결할 수 있도록 출제하는 경우가 많기 때문에 익혀두는 것이 좋다.

 

백트래킹 로직을 작성하는 방법?

 

우선 모든 경우의 수를 찾을 수 있도록 코드를 작성한다. 이후에 문제에서 특정한 조건을 만족하는 것만 탐색을 하고 불필요한 것은 탐색하지 않도록 조건문을 작성한다(조건문이 가지치기).

 

핵심은 절대로 답이 되지 않는 불필요한 탐색은 미리 종료를 하고 확장할 수 없도록 막는 것이 중요하다.

 

프로그래머스 N-Queen 문제 풀이

 

코딩테스트 연습 - N-Queen

 

N-Queen 문제는 대표적인 백트래킹 문제이다. 퀸이 체스판에서 갈 수 있는 모든 경우를 탐색하며 퀸을 하나씩 배치를 한다. (1,1) 위치에 첫 퀸을 배치한 후, 다음 퀸이 놓일 위치를 탐색한다. 퀸의 이동방향을 생각했을 때, 이미 놓여 있는 퀸의 같은 행과 열은 가지치기를 통해 막는다. 그리고 대각선 위치까지 가지치기를 통해 막는다.

 

이런 조건으로 모든 경우의 수를 탐색하며 N * N 체스판에서 N개의 퀸이 놓일 수 있는 경우의 수를 출력하면 된다.

 

첫번째 시도는 check 배열을 2차원 배열로(N * N의 체스판만큼) 만들어 확인하려고 했다. 이 풀이를 작성할 때 재귀를 잘못 호출해 (1,1)의 경우만 탐색하고 종료가 되었다. 억지로 코드를 변경해 모든 경우의 수를 탐색하도록 재귀를 작성하더라도 2중 for 문을 활용해야 할 것 같아서 이 풀이는 포기했다. 이밖에도 가지치기 코드가 너무 난잡했다. 퀸을 놓을 때마다 행과 열을 채우고(다음 퀸이 방문하지 못하도록), 대각선 방향까지 탐색하지 못하도록 코드를 작성했다.

function checkZero(row,col,check){
	if(check[row-1][col-1] === 1 || check[row-1][col+1] === 1 || check[row+1][col+1] === 1 || check[row+1][col-1] === 1) return false

    return true
}


// 대각선 방향 채우기
if (row - 1 >= 0 && col - 1 >= 0) check[row-1][col-1] = 1;
if (row - 1 >= 0 && col + 1 < n) check[row-1][col+1] = 1;
if (row + 1 < n && col + 1 < n) check[row+1][col+1] = 1;
if (row + 1 < n && col - 1 >= 0) check[row+1][col-1] = 1;

 

 

두 번째 시도는 check 배열을 1차원 배열로 바꾸었다. N * N의 체스판이라서 꼭 2차원 배열로 선언할 필요하 없다는 것을 배웠다. check 배열 자체를 column으로 생각하고, column의 index는 row가 된다. 

 

즉, column[idx] = col의 구조라면, idx = row가 되고 col 값은 column이 된다.

column[1] = 2 // (1,2)

이렇게 1차원 배열로 check 배열을 선언하고 1부터 N까지 탐색하는 for 문을 작성하면 1 행의 N개의 열 정보를 담을 수 있다(N번까지 탐색하는 반복문을 통해 확인할 수 있음). 

 

function solution(n) {
    let answer = 0;
    let column = Array.from({length : n + 1}, () => 0);
    dfs(column, 1);
    
    
    function isValidPoint(column, row){
        for(let i=1; i<row; i++){
            if(column[row] === column[i]) return false
            if(Math.abs(row - i) === Math.abs(column[row] - column[i])) return false // 행의 차 === 열의 차
        }
        return true
    }

    function dfs(column, row){
        if(row === n + 1) {
            //console.log(column)
            return answer++
        }
        
        for(let col=1; col<=n; col++){
            column[row] = col;

            if(isValidPoint(column, row)){
                dfs(column, row + 1, n);
            }
        }
    }

    return answer
}

// n	result
// 4	2
let n = 4
console.log(solution(n));

1차원 배열로 check 배열을 생성하고 모두 false로 초기화한다. DFS함수를 호출하고, (1,1)부터 시작한다. 1번 행부터 N번 행까지 탐색하므로 행이 N+1이 되면 탐색을 종료한다.

 

그전까지는 행과 열 정보를 가져와 퀸을 둘 수 있는지 확인하는 isValidPoint() 함수를 통해 검증한다. 행과 열이 같다면 false를 반환하고, 대각선 가지치기는 행의 차와 열의 차가 같은 경우 false를 반환하도록 했다. (x, y)를 기준으로 대각선은 (x-1, y-1)이 있을 수 있는데, 두 좌표의 행의 차와 열의 차는 같다는 점을 이용한다.

---

동적계획법 알고리즘

 

동적 계획법은 해결한 작은 문제로 큰 문제를 해결해 나가는 문제 풀이 방식이다. 잘게 쪼개서 큰 문제를 해결하기.

동적계획법은 그리디나 백트래킹처럼 특정 알고리즘이 아닌 문제 해결 방법만(작은 문제로 큰 문제를 해결)을 의미한다.

 

동적계획법은 다이내믹 프로그래밍이라고 하는데, 이름은 고안해낸 벨만이란 사람이 멋있어 보여서 이름을 이렇게 지었다고 한다... 이름에서 유추할 수 있는 아이디어가 없다. 딱히 다이내믹하지도 않고 프로그래밍과도 관련이 없어 보이기 때문에 이 유형의 문제가 어렵게 느껴지는 것 일수도 있다.

 

핵심은 "작은 문제로 큰 문제를 해결한다!".

 

메모리를 많이 사용하는 대신 빠른 성능을 자랑하는 특징이 있다. 동적계획법에는 다음 두 가지 방법론이 있다.

1. 메모이제이션*
2. 타뷸레이션

메모이제이션?

 

하향식 접근법으로 작은 문제들의 결과를 저장해 두었다 필요할 때 꺼내서 쓰는 방식이다. 흔한 예시가 피보나치 수열이다. 1항과 2항을 구해두고, 3항을 구할 때 1항과 2항을 사용한다.

 

이미 해결한 문제는 기록해두는 것이 메모이제이션이고, 이를 통해 성능을 개선할 수 있다.

 

피보나치수열의 예를 통해 보면, 피보나치수열에서 가장 작은 문제는 1항과 2항이다

f(1) = 1
f(2) = 1
f(n) = f(n-1) + f(n-2)

작은 문제를 기록해 두고, 큰 문제를 해결할 때 사용한다. 피보나치수열처럼 큰 문제를 해결할 때 규칙이 존재한다면 메모이제이션을 활용하자.

 

타뷸레이션?

 

상향식 접근법으로 필요한 값들을 미리 계산해 두는 방식이다. 메모이제이션이 필요할 때 계산한다면(Lazy evaluation), 타뷸레이션은 미리 계산해둔다(Eager evaluation). 보통 코딩 테스트에서는 메모이제이션을 쓰는 경우가 대부분이다.

 

DP 유형의 문제는 어떻게 접근?

 

DP 유형은 문제의 키워드 만으로 DP 문제임을 알기 어렵다. 문제의 유형을 파악하기 힘들 때 다음 2가지를 확인해본다.

1. 가장 작은 문제를 정의할 수 있는가?
2. 작은 문제를 통해 큰 문제를 해결할 수 있는 규칙이 존재하는가?

1번과 2번이 가능하다면 DP로 접근한다. 간혹 메모리를 너무 많이 사용해 통과 못하는 경우도 있지만, 코딩 테스트에서는 흔하지 않다.

 

---

부족한 점

• 재귀 호출 다루기
• DP 문제 풀이 : 단어 퍼즐
• 함수형 프로그래밍

 

느낀 점

 

"습관에 의해 틀에 박혀 있지 말자." N-Queen 문제를 풀 때 N * N 형태를 보자마자 2차원 배열로 접근해야 할 생각밖에 없었다. 다양한 문제를 풀어보지 못한 경험치 부족 탓에 1차원 배열로 해당 문제를 접근할 수 있다는 것을 전혀 생각하지 못했다. 많은 문제풀이를 통해 경험치를 쌓는 것이 중요하다고 생각된다.

 

DFS 함수를 재귀적으로 호출할 때, 꼭 종료 조건을 잘 세우도록 해야 한다. 1에서 10까지의 재귀를 한다고 치면, 1에서 3까지는 손으로, 머리로 생각하며 해결할 수 있지만 그 이후의 결과도 똑같을 것이라고만 생각하고 문제를 풀다 보니 정확한 답을 얻지 못하는 것 같다. 문제를 풀 때 어떻게 접근해야 하는지 정확하게 파악할 수 있도록 많은 연습이 필요하다.

 

오늘 이찬희 멘토님과의 커피 챗에서 알고리즘을 풀 때 이 알고리즘을 나중에 어떻게 써먹을지? 생각하는 것보다 현 상황에서는 문제를 풀이하는 "과정"에 집중하라고 말씀해 주셨다. 추후에 상태 관리를 어떻게 하면 좋을까? 와 같은 사고방식을 훈련하는 과정이라고 생각하면서.

 

자료구조, 알고리즘을 계속해서 공부하면서 부족하고 어렵다고 느꼈던 파트에서 똑같이 어렵게 느껴지고 있다. 적어도 프로그래머스 레벨 2는 겁먹지 않고, 레벨 3을 당당하게 풀 수 있을 때까지 많은 연습이 필요할 것 같다..