알고리즘 정복기 - 완전탐색

PCCP 도전 ❓ 6월 18일 ( 실패 😢 )

PCCP라는 민간 자격증에 도전했다. PCCP는 프로그래머스에서 주관하는 코딩 자격 시험이다. 필자는 Lv2를 목표로 시험에 응시했지만.. 1문제밖에 풀지못했고 점수는 300점에 그쳤다.. 총 600점을 받아야 lv2이고 400점부터 lv1 이다.

흠.. 분명 프로그래머스에서 문제를 풀 때 level2~level3를 풀어나가고 있는데 아직 시간도 많이 걸리고 지금 푸는 나의 실력이 100프로 내것이 아님을 깨달았다.

앞으로 수학문제를 푸는 것 처럼 개념을 확실히 알고 또 문제를 보고 어떤 방식으로 문제를 풀어야할 지 생각하는 연습이 필요해보인다. 즉, 무작정 푸는 거 보다 정말 생각을 하는 연습과 복습이 필요해보인다.

코딩 테스트 학습 방법 변경 ❓

앞으로는 코드를 먼저 들이밀기보다. 문제와 출제자의 의도를 분석해야겠다. 수학문제처럼 말이다. 후기를 보니 한 문제를 오래푸라는 분도 계시고 여러문제를 풀어보라는 분도 계신다. 내 생각엔 딱 그 중간으로 하면 될 거 같다. 3시간 이상 고민해보고 안된다면 살짝 힌트를 보자. 죄책감없이!

대신 망각의 곡선을 참고해서

1일차 3문제 (새로운 문제 2문제 복습문제 1~2문제)

이때 복습문제는 7일차가 됐을 때 다시 한번 풀어야겠다. 한달 뒤에는 정답을 보고 풀었던 문제만 다시 풀어야겠다. 🔥

문제로 돌아와서 ❗️

PCCP는 시험 문제지를 공유하지 않는다. 대충 기억을 되새겨 문제를 재구성했을 때 문제는 다음과 같았다.

이 카드를 순차적으로 고르는데 최대한 뽑는 카드에서 안겹치게 내가 갖는거다 카드를 각 n 번의 회수 만큼 뽑는다
뽑았을 때 내가 가지고 있는 카드와 비교했을 때 가지고있는 카드의 개수 만큼 점수가 + 된다.

let cards = [
[1, 3, 2, 4, 5],
[1, 2, 2, 4, 5],
[2, 3, 4, 1, 2],
[4, 2, 6, 3, 2],
[4, 2, 3, 5, 1],
];

다음과 같은 카드 배열에서 각 index에 담긴 배열 중 한 개의 카드를 뽑아야한다.
내가 가지고있는 카드 중 새롭게 뽑는카드와 겹치게 된다면. 겹치는 카드 중 내가 가지고 있는 카드의 수를 더하게된다.

각종 방법을 떠올렸지만 (다 논리적으로 불가능한 로직..) 완전탐색으로 풀고싶었다.

그리고 시도했지만 끝내 풀지못했다.. 너무 속상하고 정말 풀 수 있을 거 같아서 시험이 끝나고 바로 도서관으로 향했다. 그 날 역시 문제를 해결하지 못했다.

그렇게 2일이 지나갔고 결국 이렇게 한 로직만 붙들고있다간 스스로 너무 힘들 거 같아. 다음 문제로 넘어갔었다. 필자는 결국 프로그래머스 커뮤니티의 도움을 받았고 그 방법 중 한 가지를 알게되었다.

필자도 재귀로 이 구현이 가능함을 알았지만 실제 재귀적으로 생각하려니 참..풀릴거 같으면서도 안풀렸다. 필자는 수많은 시도를 했다..

// 문제를 가져올 수 없어 기억으로 다시 문제를 복기해보기
// 이 카드를 순차적으로 고르는데 최대한 뽑는 카드에서 안겹치게 내가 갖는거다 카드를 각 n 번의 회수 만큼 뽑는다
// 뽑았을 때 내가 가지고 있는 카드와 비교했을 때 가지고있는 카드의 개수 만큼 점수가 + 된다.

let cards = [
  [1, 3, 2, 4, 5],
  [1, 2, 2, 4, 5],
  [2, 3, 4, 1, 2],
  [4, 2, 6, 3, 2],
  [4, 2, 3, 5, 1],
];
// 배열에서 하나씩 고른다고 생각을 해보자
// 분리해서 생각
// 하나씩골라
// 그리고 또 하나씩골라
// 또 하나씩골라
// 그거를

function solution(cards) {
  const visited = [];
  cards.forEach((item) => {
    const visitedArr = Array.from({ length: item.length }, () => false);
    visited.push(visitedArr);
  });

  const dfs = (sum) => {
    console.log(sum);
    if (sum.length === cards.length) {
      return;
    }
    for (let i = 0; i < cards[0].length; i++) {
      for (let j = 0; j < cards.length; j++) {
        if (!visited[i][j]) {
          visited[i][j] = true;
          dfs(sum + cards[j][i]);
        }
      }
    }
  };
  dfs(``);
}
solution(cards);

function solution(cards) {
  const dfs = (sum, index1, index2) => {
    console.log(sum);
    if (
      index1 === cards.length - 1 ||
      index2 === cards[0].length ||
      sum.length === cards.length - 1
    ) {
      return;
    }

    dfs(sum + cards[index1][index2], index1 + 1, index2);
    dfs(sum + cards[index1][index2], index1, index2 + 1);
  };
  dfs(``, 0, 0);
}
solution(cards);

function solution() {
  let numArr = [1, 2, 3, 4];
  let visited = Array.from({ length: numArr.length }, () => false);
  const dfs = (sum) => {
    if (sum.length === 4) {
      return;
    }

    for (let i = 0; i < numArr.length; i++) {
      if (!visited[i]) {
        visited[i] = true;
        dfs(sum + numArr[i]);
        visited[i] = false;
      }
    }
  };
  dfs("");
}
solution();

결국 정답은 재귀에 있었고 재귀는 다음과 같다.

완전탐색 (재귀를 사용해서 ❗️)

let cards = [
  [1, 3, 2, 4, 5],
  [1, 2, 2, 4, 5],
  [2, 3, 4, 1, 2],
  [4, 2, 6, 3, 2],
  [4, 2, 3, 5, 1],
];
const answer = [];
const seq = (choice, depth) => {
  if (depth === cards.length) {
    answer.push(choice);
    return;
  } else {
    for (let i = 0; i < cards[depth].length; i++) {
      seq(choice+cards[depth][i], depth + 1);
    }
  }
};

seq("", 0);
console.log(answer);

로직을 보고나서 조금 아 그렇구나 생각하지, 아직도 사실 헷갈린다. 그만큼 재귀에 대한 이해가 부족한 거 같다. 재귀는 그때를 기억한다. 이렇게 생각하고 이해했다.

천천히 하나씩 생각해보자 내가 원하는 모습은
11244, 11242, 11243, 11245, 11241, 11224 ===>>>
이다. 그럼 일단 for문은 어디에 적용이 되어야할까?

for문은 막혀있다가 재귀가 return 될때 그때 다음 i를 찾아간다. 그러니 두 번째 인덱스 즉 cards[i][j] 에서 index j가 될것이다.

그럼 다음과 같이 생각 할 수 있다.

let cards = [
  [1, 3, 2, 4, 5],
  [1, 2, 2, 4, 5],
  [2, 3, 4, 1, 2],
  [4, 2, 6, 3, 2],
  [4, 2, 3, 5, 1],
];
const answer=[]

const dfs=(sum,dep)=>{
  
  if(dep===cards.length){
    answer.push(sum)
    return;
  }
  for(let i = 0; i <cards[dep].length; i++){
  dfs(sum+cards[dep][i],dep+1)  
  }
  
  return answer
}
dfs(``,0)

위 코드는 필자가 다시 생각해서 만든 코드이다.

천천히 생각해보면 dep이 5가 되면 탈출되어 다음 for문이 진행된다.

즉,
dfs(sum+cards[dep][0],dep+1)
dfs(sum+cards[dep][1],dep+1)
dfs(sum+cards[dep][2],dep+1)
dfs(sum+cards[dep][3],dep+1)
dfs(sum+cards[dep][4],dep+1)
가 실행되는 것이다. dep이 4일때가 return되면?

dep은 3이되고 for문이 또 실행된다. 그때는 i가 1이다.

그럼 다시 dep은 +1이 되어 4가되고 다시 for문이 실행된다.

이렇게해서 answer을 출력해보니 배열의 크기가 약 3000이다.

재귀의 return에 대해 다시 한 번 생각해보고
또, 학습해야겠다. 사실 이번 dfs 정복기는 시작일 뿐이고, 다시 알고리즘을 학습하고 또 문제를 풀고하는 방식으로 공부를 전개해나가야겠다.

지금까지는 알고리즘의 학습보다는 문제를 더 많이 풀어보자라는 주의였는데, 역시 알고리즘을 더 익혀야 이게 술술나올 거 같다. 다시 알고리즘 개념부터 시작해보자. 할수있다.