FrontEnd/프로그래머스

    FrontEnd/프로그래머스

    [JS] 등산코스 정하기

    푸는데 꽤나 애를 먹었던 문제였다. 문제 푸는 방법 자체는 접근을 잘했었다. 1. 문제는 코스를 왔다갔다 하는것이지만 사실 게이트 -> 봉우리까지만 체크를 하면된다. 2. 다익스트라 알고리즘을 활용해서 가중치의 합계가 아닌, 가중치가 가장 적게 나오는 값을 체크해주면 된다. 3. 만약 새 노드로 들어갔는데 내가 들어간 노드의 가중치보다 노드에서 뻗어나가는 가중치가 많다면 뻗어나가는 가중치를 사용해야 한다. 3으로 Node에 들어갔는데 해당 Node에 나가는 길의 가중치가 4,5만 있다면 각 길의 가중치는 4,5가 된다. 4. 각 게이트는 들어갈 수 없는 Node로 설정한다. 5. 산봉오리는 들어가면 나갈 수 없는 Node로 설정한다. 6. 다익스트라 알고리즘이기 때문에 최소 Heap을 활용한 우선순위큐를..

    FrontEnd/프로그래머스

    [JS] 카운트 다운

    문제 자체는 dp를 활용해서 해결할만한 문제였다. 우선 다트는 1~20까지 점수가 있는 판이란 점을 생각하자. dp를 만드는데 [Infinity,0]으로 각 칸을 dp[n] 이라면 dp[n][0]은 n이라는 점수를 만들기 위해 필요한 다트의 횟수, dp[n][1]은 싱글이나 불을 던진 횟수를 저장하면 될 것이라고 생각했다. 이런방식으로 dp를 구성하면 n이라는 점수를 만들기 위해서 이전 dp에서 2개만 합하면 된다! 또한 n이 점수이므로 dp[n]을 만들기 위해 dp[i]를 사용했다면 자연스럽게 더해줄 점수는 dp[n-i]가 된다. 이렇게 dp들을 검사하며 1. 다트를 던지는 횟수가 적은경우 2. 다트를 던지는 횟수가 같다면 싱글이나 불 다트를 던진 횟수가 많은경우 위 두 조건중 하나에 충족하면 dp를 ..

    [JS] 고고학 최고의 발견
    FrontEnd/프로그래머스

    [JS] 고고학 최고의 발견

    문제만 놓고 보면 완전탐색 문제같아 보인다. 실제로 모든 케이스를 검사한다고 생각한다면... 들어올수 있는칸이 64칸이므로 4 ^ 64 즉 절대로 시간안에 풀 수 없는 경우의 수가 나온다. 문제를 약간 생각해본다면 위 경우의 수를 획기적으로 줄일 수 있다. 만약에 퍼즐의 맨 윗칸이 고정되어 있다고 생각해보자. 01030213 해결할 수 없다면 false 반환 -> 해결할 수 있다면 돌린 횟수를 반환 3. 첫줄을 dfs를 활용해서 4가지 케이스씩 4^n의 케이스를 돌려가면서 확인 4. 나온 값들 중 가장 작은 값을 반환 function solution(clockHands) { const len = clockHands.length const dc = [0,1,0,-1,0] const dr = [0,0,1,0..

    FrontEnd/프로그래머스

    [JS] 2차원 동전 뒤집기

    동전뒤집기 문제에서 생각할 점은 어느 칸이던 같은 줄을 2번이상 뒤집는건 의미가 없다는 것이다. 즉 , 가로 1~10 세로 1~10 까지 있다고 가정한다면 가로 3번째 라인을 1번뒤집나 3번뒤집나 5번 뒤집나 해당 라인의 결과는 같게 된다. 따라서 모든 라인의 줄을 최대 1번까지만 뒤집을 수 있다고 생각할 수 있다. 그다음으로 생각해야 할점은 순서가 상관이 없다는 것이다. 가로 3번 -> 세로2번 -> 가로 6번 이런식으로 뒤집나 세로 2번 -> 가로 6번 -> 가로3번 이런식으로 뒤집나 결과가 같게 나온다. 즉 위 문제는 2^10으로 나오는 완전탐색을 할 필요가 없다! 10번의 경우만 체크하면 된다. 1. 우선 문제를 조금 간략화 하기 위해서 beginning과 target 배열을 비교해서 같으면 fa..

    FrontEnd/프로그래머스

    [JS] 부대복귀

    각 그래프의 간선의 길이가 1이므로 처음에는 단순히 bfs로 구하면 되는거 아니야? 라는 생각을 하게 되었다. function solution(n, roads, sources, destination) { const graph = [...Array(n + 1)].map((_) => []); for (const [a, b] of roads) { graph[a].push(b); graph[b].push(a); } const getDist = (start, end) => { const visited = Array(n + 1).fill(false); const que = [[start, 0]]; let idx = 0; while (que[idx]) { const [node, dist] = que[idx++]; v..

    [JS,Python] 등대
    FrontEnd/프로그래머스

    [JS,Python] 등대

    시간이 매우매우매우매우 걸렸던 문제였다. (내잘못인가 아닌가..) 먼저 필자가 문제에 접근한 방식은 아래와 같다. 1. 그래프가 최소신장트리 이므로 한점을 부모 노드로 잡고 아래로 내려가는 구조로 바꾸는 것이 가능하다. 2. 이때 자식 노드 중에 더이상 자식이 없는 뿌리노드가 포함되어 있다면 해당 부모 노드는 무조건 불이 켜져있어야 한다. 3. 자식노드 중에 뿌리가 없는 노드가 있다면 해당 노드에 불이 켜져있는 경우와 꺼져있는 경우를 비교해줘야 한다. - 이 경우 dfs탐색을 통해서 하다보면 검사한 노드를 또 검사하는 일이 계속 생기게 된다. 4. 따라서 2차원 dp[n][2] 만큼을 생성해서 노드 n이 켜져있는지 꺼져있는데 2가지 경우를 담아서 계산을 한다. - 예를 들어서 3번 노드에 불이 켜져있는지..

티스토리툴바