[CodeKata] 프로그래머스 : 2.26(금), 타겟 넘버, 카펫

🥋 Ooooth!! (Level 2) : 1️⃣ 타겟 넘버

 

🧮 풀이

function solution(numbers, target) {
  let answer = 0;
  function DFS(idx, now, acc) {
    acc += now;
    if (idx === numbers.length - 1) {
      answer = acc === target ? answer + 1 : answer;
      return;
    }
    DFS(idx+1, numbers[idx+1], acc)
    DFS(idx+1, -numbers[idx+1], acc)
  }
  DFS(-1, 0, 0);
  return answer;
}

1. answer는 최종정답이자, 누적값(acc)과 target이 일치할 때 1을 더하는 변수가 될 것이다.
2. DFS() 깊이우선탐색 함수를 만들어준다. 변수는 idx(numbers 배열 인덱스), now(현재 더하거나 뺄 값), acc(현재 누적값) 3개!
3. 이 함수는, acc(누적값)과 now(현재값)을 더한다. 그리고, idx 조건문과 DFS 함수반복이 진행된다.
4. idx가 (numbers길이 - 1) 과 같다면, 모든 배열값을 탐색했다는 의미로 종료조건이다. 여기서, 누적값과 target이 같으면 answer에 1을 더하는 것이다. (이후 return)
5. 종료조건이 아니라면, DFS를 반복한다. 더하거나 빼야 하므로, now값이 numbers[idx+1]이 +, - 로 두 번 들어간다.
6. DFS() idx가 0으로 시작해도 되나, now에 numbers[0], -numbers[0] 2번 적용해야하므로 idx -1 시작(첫 시행은 누적없음)

 

🖇 리뷰

function solution(numbers, target) {
    let answer = 0;
    dfs(0, 0);
    
    function dfs(index, sum) {
        if(index === numbers.length) {
            if (sum === target) {
                answer++;
             }
            return;
        }
        dfs(index + 1, sum + numbers[index]);
        dfs(index + 1, sum - numbers[index]);
    }
    
    return answer;
}

더 간결한 풀이가 가능했다! now값이 필요없이, acc(누적값)에 numbers[index]를 더한 경우, 뺀 경우를 각각 직접 넣었다.

큰 틀의 컨셉은 비슷하며, 그래프 분석 알고리즘인 DFS(깊이 우선 탐색), BFS(너비 우선 탐색) 에 대해 복습 필요성을 느꼈다.

 

 

📍 그래프 탐색 알고리즘

출처: https://mygumi.tistory.com/102

그래프는 위처럼 정점(node)과 간선(edge)으로 이루어진 자료구조의 일종이다. (G = V * E)

그래프 탐색이라는 것은, 하나의 정점으로부터 모든 정점을 방문하면서 탐색하는 알고리즘을 일컫는 말이다.

이 그래프 탐색의 대표적인 2가지 패턴이 바로 DFS(깊이 우선 탐색), BFS(너비 우선 탐색) 인 것이다.

 

1) 깊이 우선 탐색(DFS, Depth-First Search)

출처: https://developer-mac.tistory.com/64

루트 노드(혹은 다른 임의노드)에서 시작해서, 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식이다.

미로찾기를 예로 들면, 최대한 한 방향으로 쭉 가다가 막다른 길인 경우 다시 가까운 갈림길로 돌아와 다른 경로를 탐색하는 진행방식인 것이다.

• 모든 노드를 방문하고자 하는 경우 선택되는 방법
• 너비 우선 탐색(BFS)에 비해 로직이 간단함
• 너비 우선 탐색(BFS)에 비해 검색속도 자체는 느림 (모든 노드를 방문하므로)
• 자기 자신을 호출하는 순환 알고리즘 형태. 스택(Stack) 혹은 재귀함수로 구현
• 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다(인덱스 활용 등). 그렇지 않으면 무한루프에 빠질 위험이 있다.

2) 너비 우선 탐색(BFS, Breadth-First Search)

루트 노드(혹은 다른 임의노드)에서 시작해서, 인접한 노드를 먼저 탐색하는 방법으로 가까운 노드순으로 먼저 방문하는 순회방식이다.

주로, 두 노드 사이의 최단경로를 찾고자 할 때 이 방법을 선택한다.

• 두 노드 사이의 최단경로 혹은 임의의 경로를 찾고자하는 경우 선택되는 방법
• BFS는 재귀적으로 동작하지 않는다. 각각 방문노드를 차례로 저장 및 불러오는 큐(Queue), 선입선출(FIFO) 구조이다.
• Queue에 각 노드정보를 기록해야 하므로 메모리를 많이 잡아먹는다.

---

🥋 Ooooth!! (Level 2) : 2️⃣ 카펫

다음 문제 컨셉을 잡다가 풀이가 떠올라서 바로 풀었더니 금방 정답을 구할 수 있었다.

 

🧮 풀이

function solution(brown, yellow) {
  for (let yh = 1 ; yh <= yellow ; yh++) {
    if (yellow % yh !== 0) {
      continue;
    }
    const yw = yellow / yh;
    if ((yw + yh + 2) === brown/2) {
      return [yw+2, yh+2];
    }
  }
}

1. yh(노란박스 높이), yw(노란박스 너비) 변수를 활용해 구한다. yellow = yw * yh, brown = 2 * (yw + yh + 2) 원리를 활용한다.
2. yh를 기준으로 잡은 것은, yw >= yh이므로 작은쪽에서부터 조건을 검색하려면 더 작은값인 yh를 활용해야했기 때문이다.
3. yh는 1부터 yellow까지 순회하되, 약수가 아니라면 yw가 정수가 안나오므로 생략(continue)한다.
4. yw, yh가 yellow 조건에 맞다면, 이들이 brown 조건을 검사한다. 만족시, 2씩 더한 테두리 박스길이를 튜플로 반환 및 종료한다.

 

🖇 리뷰

brown, yellow 조건을 고민하다가 바로 생각이 나서 코드를 작성해보았고 생각보다 빨리 답을 도출할 수 있어 2개를 정리했다.