백트래킹

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

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

백준 1987번: 알파벳(javascript, DFS, 백트래킹)

말이 지날 수 있는 최대의 칸 수를 구하는 문제이다. 최대의 칸을 구해야 하기 때문에 단순 BFS가 아닌 완전탐색 혹은 백트래킹을 이용해 문제를 풀어야 하겠다고 생각했다. 왜냐하면 DFS나 BFS는 한번 방문한 곳은 다시 방문하지 않는데 이 때문에 방문경로에 따라 최대값이 달라지는 경우가 생기기 때문이다. 백트래킹 풀이를 위해서 방문배열을 만들었는데 아스키코드를 이용해 방문을 체크하였다. 왜냐하면 Set자료형에 방문한 알파벳을 넣을수도 있지만 Set은 원소를 집어넣을 때 O(n)이 필요하지만 아스키코드를 이용해 배열의 인덱스에 바로 접근하면 O(1)로 시간복잡도를 줄일 수 있기 때문이다. 그리고 DFS의 인수로 cnt를 주어서 DFS가 재귀할 때마다 cnt에 1을 더해 최대값을 구하고자 했다. 이를 이용..

백준 2529번: 부등호 (javascript, DFS, 백트래킹)

완전탐색을 해야하는 문제이며 나는 백트래킹을 이용해서 풀었다. 백트래킹은 DFS의 응용으로 방문하면 안되는 곳은 방문하지 않는 방식으로 탐색범위를 줄이며 탐색표시를 하고 다시 탐색표시를 해제함으로써 모든 범위를 탐색하는 알고리즘이다. 일전에 백트래킹으로 한 문제를 푼 적이 있는데 그 때는 queue에 방문 원소를 넣고 다시 빼고, 방문표시까지 해제하는 식으로 문제를 풀었었다. 그러나 꼭 queue에서 방문 원소를 빼야 하는 것은 아니라는 것을 깨닫고 이 글을 쓰게 되었다. 풀이는 다음과 같다. queue의 길이가 문제에서 주어진 숫자의 개수인 k+1이 되면 queue가 꽉찼다는 의미이므로 배열에 그 값을 넣고 함수를 끝낸다. 그리고 백트래킹의 핵심은 backtract함수에서 보이듯이 for문으로 0~9까..

프로그래머스: 여행 경로 (파이썬, DFS, 백트래킹)

꽤나 어려운 문제였다. 코드를 짜는 것 자체는 어렵지 않았으나 문제의 엣지케이스를 생각하는데 어려움이 있어 처음에 접근을 잘못한 문제다. 주어진 항공권을 모두 써야 하므로 DFS로 접근을 해야함을 알 수 있다. 이때 가능한 경로가 여러 개일수도 있는데 나는 tickets배열을 lambda식으로 정렬하면 알파벳 순서가 앞서는 경로를 탐색할 것이라 생각했다. 그러나 그렇게 풀면 테스크 케이스1에서 계속 실패했는데 이에 대한 엣지케이스를 생각하는 것이 쉽지 않았다. 특정한 엣지 케이스를 생각하진 못했지만 여러개의 경로를 비교해야 하므로 백트래킹을 이용해 풀어야겠다고 생각했다. 백트래킹은 DFS의 응용으로 분기점에서 다른 경로들또한 탐색하도록 하는 알고리즘이다. 문제에서 여행 경로의 길이는 tickets배열의 ..