Algorithm

    [JS][백준]1520_내리막 길
    Algorithm/BaeKJoon

    [JS][백준]1520_내리막 길

    문제 번호 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 알고리즘 분류 다이나믹 프로그래밍 그래프 이론 그래프 탐색 깊이 우선 탐색 문제 풀이 DFS와 DP를 사용해야하는 문제이다. 처음에는 DFS를 돌면서 도착점에 도착했을 때 카운트를 해주고 해당 카운터를 반환했는데 이럴경우 시간 초과에 걸리게 된다. 그래서 중복되는 과정을 줄일 수 있도록 이전 값들을 활용해야 겠다고 생각했다. 여기서 고민을 했던 점은 같은 (x,y) 좌표에 도착하더라도 걸리는 '칸 수'는 다를 수 있다는 점이었다. 우선 시작점에서 DFS를 ..

    [JS][백준]16198_에너지 모으기
    Algorithm/BaeKJoon

    [JS][백준]16198_에너지 모으기

    문제 번호 16198번: 에너지 모으기 N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다. i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있 www.acmicpc.net 알고리즘 분류 브루트포스 알고리즘 백트래킹 문제 풀이 처음엔 앞뒤의 곱이 가장 큰 숫자를 먼저 빼고, 만약 곱이 같다면 작은 숫자를 빼는 형식으로 생각했다. 그러나 이 경우 예외가 존재한다. 5 3 1 2 4 5 그래서 input 조건을 다시 살펴봤다. 맨앞, 맨뒤는 못 뽑으니까 완전탐색으로 진행해도 될거같다.라고 생각해서 백트래킹으로 풀면 되겠다 싶었다. 최대한 for문을 안쓰려고 했는데 백트래킹으로 바꾸면서 for문을 넣어버렸다. for문 대신..

    [JS][프로그래머스]1차_캐시
    Algorithm/Programmers

    [JS][프로그래머스]1차_캐시

    문제 번호 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 알고리즘 분류 문제 풀이 LRU가 무엇인지 알아야하는 문제다. 정확하게 알 필요는 없고 가장 오랫동안 사용되지 않은 페이지를 교체한다라는 것만 알면 된다. 그리고 검색한 도시가 캐시되어 있다면 해당 도시가 최근에 검색 되었다고 업데이트 해야한다. 예를들어 [A,B,C] 라는 순서대로 검색을 진행 했었으면, A가 가장 오랫동안 사용되지 않은 페이지에 해당된다. 이때 다음 번에 A를 검색했으면 [B,C,A]로 상태를 업데이트 해주어야 한다. cache된 데이터를 담아주는 자료구조로 배열을 선택했기 때문..

    [JS][프로그래머스]배달
    Algorithm/Programmers

    [JS][프로그래머스]배달

    문제 번호 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 알고리즘 분류 다익스트라 문제 풀이 문제를 읽어보면 1번 마을에서 다른 마을까지의 최소 경로를 알면 문제를 해결 할 수 있다는 것을 알 수 있다. 이것은 '한 정점에서 다른 모든 정점까지의 최소거리'를 구하는 다익스트라 알고리즘을 떠올리게 만든다. 다익스트라 알고리즘으로 1번 마을에서 다른 마을까지의 거리를 구하고 그 거리가 K이하가 되는 마을들을 모두 고르면 된다. 다익스트라를 사용하기 위해서 최소힙을 구현하자 class Node{ constructor(node, dist){ this.node =..

    [JS][프로그래머스]야근 지수
    Algorithm/Programmers

    [JS][프로그래머스]야근 지수

    문제 번호 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 알고리즘 분류 우선 순위 큐 문제 풀이 우선순위 큐를 활용하면 문제를 해결 할 수 있다. 문제에서 주어진 works를 살펴보면 works중 가장 큰 수가 가장 작아질 때가 정답이다. 따라서 MaxHeap을 사용해서 works에 남아있는 수 들 중에서 가장 큰 수를 1씩 줄여나가면 된다. MaxHeap class Node{ constructor(value) { this.value = value; } } class MaxHeap{ constructor(compare){ this.heap = []; th..

    [JS][프로그래머스]N-Queen
    Algorithm/Programmers

    [JS][프로그래머스]N-Queen

    문제 번호 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 알고리즘 분류 백트래킹 문제 풀이 2차원 배열을 생성해서 퀸을 놓으면서 해당 퀸이 지나가는 경로를 체크해서 다음 퀸이 해당 경로에 올 수 없도록 하려고 했다. 그러나 2차원 배열을 그때그때 지워가면서 확인하려 했으나 그렇게 되면 시간 초과에 걸리게 된다. 그래서 i번째 퀸을 놓을 수 있는지 다른 방법을 이용해서 확인해야 한다. 여기서 힌트를 읽어봤다. 1차원 배열을 사용하면 시간을 줄여서 확인할 수 있다. 예를 들어 'vailed [i] = 3'이라면 i행 3열에 퀸이 놓여있다는 뜻이다. 이를 활용..

    [JS][백준]14891_톱니바퀴
    Algorithm

    [JS][백준]14891_톱니바퀴

    문제 번호 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net 알고리즘 분류 구현 시뮬레이션 문제 풀이 구현 문제이다. 한 가지 어려웠던 점은 한개의 톱니바퀴가 돌아가면 다른 톱니바퀴에도 영향을 끼치게되는데 이 과정들이 동시에 일어난다는 것이다. 예를들어 1번 톱니바퀴를 돌리면 오른쪽 끝에있는 4번 톱니바퀴도 돌아갈 수 있는데, 1-2-3-4번 차례로 돌리는 것이 아니라 1-2-3-4번 톱니바퀴가 '동시에' 돌아가야 한다. 우선 돌리긴 돌려야하니 시계방향, 반 시계 방향으로 톱니를 돌리는 알고리즘을 작성했다...

    [JS][백준]2294_동전 2
    Algorithm/BaeKJoon

    [JS][백준]2294_동전 2

    문제 번호 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 알고리즘 분류 다이나믹 프로그래밍 문제 풀이 DP를 접할 때 거의 무조건 만나 볼 수밖에 없는 동전 문제이다. 여러 가지 형태의 동전 문제가 있지만 '동전 2'는 k원을 최소 개수의 동전을 사용해서 만들어야 한다. 이때 k원을 만들기 위해서 필요한 동전의 최소 개수를 저장하기 위해서 dp라는 배열을 사용하였다. k원 까지 만들어야 하니까 dp배열의 크기는 k+1이다.(0원도 생각해야 한다) 그리고 0원을 만드는 최소 개수..

티스토리툴바