Algorithm

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

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

프로그래머스: 단속카메라(javascript, greedy)

문제는 쉬우나 처음 접근을 잘못해 헤맨 문제이다. 이전에 호텔방 예약하는 문제와 비슷하여 시작 시간과 끝시간만 비교했으나 다음 차의 범위가 이전 차의 범위안에 들더라도 비교가 계속 되면 과거 차들의 정보가 반영이 안되는 문제를 고려 안했다. 그 부분을 수정하기 위해 시작 시간과 끝 시간을 계속 변경 시키는 알고리즘을 추가하여 문제풀이에 성공하였다. greedy algorithm은 떠올리기는 쉬우나 그것이 절대해인지 증명하는 것이 매우 어려워 사실상 운에 맡기거나 반례를 열심히 생각해내야 한다.. function solution(routes) { let answer = 0; routes.sort((a,b)=>a[0]-b[0]) let start = 30001 let end = -30001 routes.fo..

프로그래머스: 숫자 변환하기(javascript, deque, bfs)

BFS를 이용해 푼 문제이다. 처음에 BFS로만 풀려 했으나 계속 시간초과가 나서 백준 소꿉놀이처럼 미리 배열을 선언해두고, 시작점을 1로 해둔다. 그리고 방문안한 점을 방문할 때만 이전 지점에 1을 더해서 연산 횟수를 기록하는 방식이다. 글까지 써가며 기록하게 된 이유는 자바스크립트의 배열은 shift와 unshift연산이 모두 되는 deque이기에 bfs를 쓸 때 그냥 배열에 저장했었는데 테스트 케이스 두개가 계속 시간초과가 나서 자료구조를 다른 사람이 구현해놓은 deque을 사용했는데 훨씬 빠르게 통과돼서 놀랐었다. 왜냐하면 보통 내장함수나 내장 자료구조보다 잘 구현하기는 힘들기 때문이다. 앞으로 deque이나 queue자료구조가 필요한 알고리즘 문제는 자료구조를 직접 구현해서 써야겠다. class..

프로그래머스: 프렌즈 4 블록(javascript, 구현)

애니팡같은 게임을 구현하는 문제이며 구현문제이나 javascript는 문자열이 immutable이라서 처리하는데 조금 애를 먹었던 문제였다. 파이썬으로는 되게 쉽게 풀었던것 같은데.. 로직은 간단하다. 2차원 배열을 2x2 정사각형으로 탐색하며 2x2블록안의 문자가 모두 같다면 배열에 그 위치를 모두 저장하면 된다. 배열에 저장하는 이유는 한 위치가 두 블록에 중복되게 포함될 수 있으므로 위치들을 모두 저장했다가 탐색이 끝나면 한번에 지워야 한다. 그 후 빈 블록을 제외한 나머지 블록들을 아래로 내리는 작업을 반복하면 된다. javascript의 문자열이 immutable이라서 문자열을 [행,열]로 접근하지 않고 행을 통채로 교체하는 방식으로 배열을 바꿨다. function solution(m, n, b..

프로그래머스: 파일명 정렬(javascript, 구현)

문제는 구현하기 쉬웠으나 배울만한 점 두가지가 있어 글을 남기게 된다. 문제는 기본적인 정렬 문제로 간단한 구현 문제였다. 주어지는 파일명마다 head와 number로 나누고 tail부분은 무시 후, head를 대소문자 구분없이 기준삼아 정렬 후 두번째 정렬기준으로 number로 정렬하면 된다. head와 number를 구분하기 위해 javascript의 내장함수인 isNaN함수를 사용하고, number이후의 tail를 무시하기 위해 number가 빈값이 아닐때 알파벳이 들어오면 파일명 저장을 멈추도록 하였다. 그 후 head와 number, 원래 파일명을 배열로 하여 빈배열에 저장하였다. 파일명들을 head, number, 원래 파일명으로 나누어 모두 저장하고 나면 배열을 정렬하기만 하면 된다. 이를 ..

백준 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까..

백준 13913번: 숨바꼭질4 (javascript, BFS)

숨바꼭질 문제의 변형판이다. 최단경로와 그 경로를 출력해야 한다. 최단경로는 이전에 구한 것처럼 BFS를 이용해 구할 수 있다. 새로운 배열을 선언하고 방문한 점의 위치에 이전 점의 위치를 저장하고, 목표 위치인 K에 도착했을 때 반복문으로 이전 좌표들을 따라감으로써 방문경로를 확인하였다. 코드는 다음과 같다. const fs = require('fs'); let [N, K] = fs.readFileSync("/dev/stdin").toString().trim().split(' ').map(a => Number(a)) function BFS(x, k){ let queue = [x] let array = new Array(MAX).fill(0) let path = new Array(MAX).fill(0) ..