Algorithm/BaeKJoon

    [JS][백준]5549_행성 탐사
    Algorithm/BaeKJoon

    [JS][백준]5549_행성 탐사

    문제 번호 5549번: 행성 탐사 상근이는 우주선을 타고 인간이 거주할 수 있는 행성을 찾고 있다. 마침내, 전 세계 최초로 인간이 거주할 수 있는 행성을 찾았다. 이 행성은 정글, 바다, 얼음이 뒤얽힌 행성이다. 상근이는 이 www.acmicpc.net 알고리즘 분류 누적 합 문제 풀이 2차원 배열혹은 3차원 배열을 사용해서 누적 합을 구해야한다. 이번에는 2차원 배열을 사용했다. 각 2차원 배열의 [i][j]는 (1,1)부터 (i,j)까지의 J O I 의 갯수를 나타낸다. let sumJ = new Array(1001).fill(null).map(_ => new Array(1001).fill(0)); let sumO = new Array(1001).fill(null).map(_ => new Array..

    [JS][백준]2573_빙산
    Algorithm/BaeKJoon

    [JS][백준]2573_빙산

    문제 번호 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 알고리즘 분류 구현 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 문제 풀이 BFS를 사용하면된다. 많이 접해본 유형의 문제이다. BFS를 사용해서 상하좌우에 바다물이 있는지 확인하고 인접한 바다물의 수 만큼 빙산의 높이를 낮춰주면된다. 이때 주의할점은 모든빙산의 높이가 '동시에' 낮아져야 한다는것이다. 그래서 2개의 2차원 배열을 사용해서 모든 빙산에 대한 BFS가 끝나고 동시에 높이를 낮출 수 있도록 했다. 그리고 빙산의 높이는 0..

    [JS][백준]11057_오르막 수
    Algorithm/BaeKJoon

    [JS][백준]11057_오르막 수

    문제 번호 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 알고리즘 분류 다이나믹 프로그래밍 문제 풀이 DFS를 사용해서 풀이를 진행하려고 하였으나 그랬다면 시간초과에 걸렸을것이다. '1000자리' 수 까지 확인을 해야하기 때문이다. 그래서 2차원 배열을 사용한 DP로 풀이를 진행하였다. 우선 0으로시작하는 1자리 오르막수들부터 생각해본다. 당연히 '0' 1개 뿐이다. 그럼 0으로 시작하는 2자리 오르막수를 생각해본다. 00, 01, 02, 03............ 09 까..

    [JS][백준]9996_한국이 그리울 땐 서버에 접속하지
    Algorithm/BaeKJoon

    [JS][백준]9996_한국이 그리울 땐 서버에 접속하지

    문제 번호 9996번: 한국이 그리울 땐 서버에 접속하지 총 N개의 줄에 걸쳐서, 입력으로 주어진 i번째 파일 이름이 패턴과 일치하면 "DA", 일치하지 않으면 "NE"를 출력한다. 참고로, "DA"는 크로아티어어로 "YES"를, "NE"는 "NO"를 의미한다. www.acmicpc.net 알고리즘 분류 문자열 정규 표현식 문제 풀이 정규식을 사용하지 않아도 문제를 해결할 수 있다. '*'를 기준으로 주어진 패턴을 split 한 다음 나누어진 두개의 패턴이 주어지는 입력들과 일치하는지 확인하면된다. 그러나 문제를 처음 접했을때 '정규표현식'을 사용하여 문제풀이를 시도하였기때문에 끝까지 정규표현식을 사용해서 풀이를 진행했다. 정규식이 익숙하지 않아서 정규식을 사용함에 있어서 MDN을 많이 참고하였다. Re..

    [JS][백준]17615_볼 모으기
    Algorithm/BaeKJoon

    [JS][백준]17615_볼 모으기

    문제 번호 17615번: 볼 모으기 첫 번째 줄에는 볼의 총 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 다음 줄에는 볼의 색깔을 나타내는 문자 R(빨간색 볼) 또는 B(파란색 볼)가 공백 없이 주어진다. 문자열에는 R 또는 B 중 한 종류만 주 www.acmicpc.net 알고리즘 분류 그리디 알고리즘 문제 풀이 문제의 조건을 읽어보면 '한번 움직인공과 같은 색의 공만 옮길 수 있다' 라는것을 알 수 있다. 그래서 왼쪽이나 오른쪽에서 시작해서 반대방향으로 가면서 '내가 움직일공과 다른색'의 공이 나오면 그 이후에 등장하는 '내가 움직일 공과 같은색'의 공의 갯수를 세어주면된다. RRBRRR이 주어진다고하면 왼쪽부터 살펴보는경우, 빨간색공을 옮긴다고 하면 R , R , 'B' 이후에 나오는 3개..

    [JS][백준]5582_공톤 부분 문자열
    Algorithm/BaeKJoon

    [JS][백준]5582_공톤 부분 문자열

    문제 번호 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 알고리즘 분류 다이나믹 프로그래밍 문자열 문제 풀이 많이 접해본 문제이다. 문제를 해결하기위해서 2차원 배열을 사용할거다. 2차원배열의 x축과 y축을 각각 주어진 문자열이라고 생각한다. abcd 와 bcda가 있다면 다음과 같다. a b c d b X c d a 이제 X 지점부터 오른쪽아래로 탐색하면서 2차원 배열을 채워준다. (x,y)일때 두 문자열의 문자가 같다면 '왼쪽대각선위 + 1' 의 값을 (x,y)에 넣어주고, 서로 다르다면 0을..

    [JS][백준]13549_숨바꼭질 3
    Algorithm/BaeKJoon

    [JS][백준]13549_숨바꼭질 3

    문제 번호 채점 현황 www.acmicpc.net 알고리즘 분류 그래프 이론 자료 구조 그래프 탐색 너비 우선 탐색 다익스트라 0-1 너비 우선 탐색 문제 풀이 처음에는 일반적인 BFS를 사용해서 문제를 풀려고했다. 그런데 '순간이동'시에는 시간이 증가하지 않기때문에 일반적인 BFS를 사용할 수 없었다. BFS는 가중치가 다르다는 조건을 다루기 힘들기 때문이다. 그래서 MinHeap을 사용해서 문제를 풀기로 하였다. 시간이 가장 적게 걸린것이 가장 처음에 오도록 MinHeap을 작성한다. class Node { constructor(value, dist) { this.value = value; this.dist = dist; } } class MinHeap { constructor() { this.hea..

    [JS][백준]1753_최단경로
    Algorithm/BaeKJoon

    [JS][백준]1753_최단경로

    문제 번호 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 알고리즘 분류 그래프 이론 다익스트라 문제 풀이 다익스트라 알고리즘을 사용해야한다. 그리고 다익스트라 알고리즘을 사용하기위해서 heap자료구조를 알아야한다. 이 문제에서는 MaxHeap이 아닌 MinHeap을 사용할것이다. 알고리즘 자체에 대한 설명이나 Heap 자체에 대한 설명은 더 좋은 블로그들이 많이 있으므로 따로 작성하진 않는다. 다익스트라. 23. 다익스트라(Dijkstra) 알고리즘 다익스트라(Dijks..

티스토리툴바