FrontEnd/프로그래머스
[JS] 여행 경로
graph + 백트래킹을 활용하여 해결하였다. https://school.programmers.co.kr/learn/courses/30/lessons/43164 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 먼저 그래프에 티켓들을 담는다. 이때 dfs를 활용해서 티켓의 정보를 가져오는 경우에 정렬이 되어있어야 하므로 마지막에 그래프를 정렬해준다. 이후 dfs를 활용하여 티켓을 탐색한다. dfs의 종료조건이 해당나라의 방문이 아닌 티켓의 사용 유무인 점을 알아두자. 따라서 티켓을 찢고 -> DFS 검색하고 -> 만약 해당 경로가 답이라면 그게 제일 빠르므로..
[JS] 입국심사
이분탐색을 활용하여 해결하였다. https://school.programmers.co.kr/learn/courses/30/lessons/43238 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이렇게 케이스가 10억명이 넘어가는 특수한 문제들은 대부분 이분탐색을 활용해서 푸는 방법을 생각해야 한다. 시간이라는 데이터는 이미 오름차순이 되어있는 데이터라고 생각할 수 있으므로 시간을 도출해 내는것이 아닌 시간을 하나씩 대입하여 해당 시간안에 사람을 모두 통과시킬 수 있는지 체크하는 방식으로 접근하면 쉽게 해결할 수 있다. 조금 주의할점으로는 한 사람이 검사할..
[JS] 가장 먼 노드
BFS + DP 를 조합하여 해결할 수 있는 문제였다. (3단계 치곤 쉬운것 같기도?) https://school.programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 단순하게 가장 먼 노드들을 저장하면 되기 때문에 1번 노드부터 큐를 활용한 BFS를 구현하여 해결하였다. 이때 노드의 개수와 간선의 개수가 각각 20000,50000개이므로 DP를 활용해서 방문 했는지 안했는지 체크해주면 되는데 나는 문제를 해결하기 위해서 방문한 김에 거리를 기록해줘서 후에 정답을 도출할 수 ..
[JS] 순위
DFS + 그리디 알고리즘을 활용해서 해결해보았다. 우선 그래프 두개를 두고 a > b라면 winGraph와 loseGraph를 두고 이긴쪽,진쪽만 저장했다. 이후 n번째 노드가 들어왔다면 해당 노드를 이긴사람들을 차례로 탐색했다. 또 진쪽으로도 마찬가지로 한방향만을 탐색했다. 이렇게 한 이유는 순위를 정확히 매기려면 a>b>c ... 이렇게 한 방향이 고정적으로 되어있어야 하기 때문이다. ++ DP를 사용해서 저장한다면 조금 더 효율적인 코드를 짜는것도 가능할 듯 하다. function solution(n, results) { const winGraph = [...new Array(n+1)].map(_ => []) const loseGraph = [...new Array(n+1)].map(_ => []..
[JS] 자물쇠와 열쇠
배열을 다룰 줄알아야 하는 문제였다. 1. 배열을 회전시키며 4가지 경우를 검사한다. 2. 2 * key.length + lock.length - 2만큼의 배열을 만든다. 2번과 같은 확장배열을 만들어야 key를 움직여가며 자물쇠와 키를 맞춰놓는것이 편하다. 만약 예제라면 아래와 같은 7*7 확장배열을 만들고 lock의 정보를 저장한다. (빈칸은 0이라 생각하자. 1 1 1 1 1 1 1 아래처럼 자물쇠와 키를 순회하며 검사한다. 이때, key의값을 그냥 넣는것이 아닌 더해져서 넣어야 후에 돌기와 돌기가 만난것을 검사할 수 있다. 1 1 2 1 1 1 1 1 1 1 2 2 1 1 1 1 1 1 1 2 2 1 1 1 1 1 1 1 2 1 1 1 1 1 .... 반복 3. 자물쇠와 key가 일치하는 것은 가..
![[JS] 외벽 점검](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FcoIcho%2FbtsClII6pe7%2FHVoE313GlMB2PvASuAgXn0%2Fimg.png)
[JS] 외벽 점검
까다로운 문제였고 접근할 수 있는 방법이 굉장히 많고 생각할 거리도 많은 문제였다. 1 STEP) 원형 구조를 어떻게 구현할지 코테에서 원형구조를 구현하려면 보통 2가지 방법을 많이 쓴다. 1. 원형 링크드 리스트 구현 2. 리스트 2개를 이어붙임 사실 2번이 코테볼때는 조금 더 좋은 조건인거 같긴 하다. 특히 이번문제같은 경우 리스트 2개를 이어붙인 구조의 원형리스트를 구현한다면 조금더 쉽게 해결할 수 있을 거 같다. 예를들어서 1번예제를 리스트로 표한한다면 [1, 5, 6, 10] 이므로 [0,1,0,0,0,1,1,0,0,0,1,0] 가된다. 이 를 2번 이어붙인다면 [0,1,0,0,0,1,1,0,0,0,1,0,0,1,0,0,0,1,1,0,0,0,1,0] 가 된다. 1번의 정답인 4m를 10번에, 2..