backtracking

프로그래머스: 불량 사용자(JS, backtracking) feat. 현대캐피탈 2024 상반기 공개채용

알고리즘을 하도 오랜만에 풀었더니 백트래킹이라는 알고리즘을 까먹었어서 되새길겸 쓰는 글이다.문제는 간단하다. 불량 사용자 배열의 원소들이 각각 가능한 경우의 수를 구하고 이 중 중복이 존재할 수 있고, 불량 사용자 배열의 길이 및 사용자 아이디 배열의 길이가 8이하로 매우 작으니 백트래킹을 이용해 가능한 모든 경우의 수를 구하면 된다. 백트래킹을 사용하는 이유는 매번 빈 배열을 dfs에 넣어야하기 때문이다. 현대 캐피탈 2024 상반기 공채 3번이 딱 이런 문제였는데 난 그때 백트래킹을 생각을 못해서 재귀함수의 depth가 0일때 재귀함수 안에서 빈 배열을 생성하여 그 배열에 원소를 넣고 재귀함수에 다시 prop으로 넣는 방식으로 풀었었다. 참고로 1번은 구현, 2번은 그래프탐색(BFS사용), 3번은 백..