Algorithm

    [JS][백준]1197_최소 스패닝 트리
    Algorithm/BaeKJoon

    [JS][백준]1197_최소 스패닝 트리

    문제 번호 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 알고리즘 분류 그래프 이론 최소 스패닝 트리 문제 풀이 유니온 파인드와 MST의 개념을 알고 있으면 쉽게 풀 수 있다. 문제에서 주어진 간선의 정보들을 MinHeap에 저장해준다. let graph = new MinHeap(); for (let i = 1; i < input.length; i++) { let [start, end, cost] = input[i].split(' ').map(Number); g..

    [JS][백준]1052_물병
    Algorithm/BaeKJoon

    [JS][백준]1052_물병

    문제 번호 1052번: 물병 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번 www.acmicpc.net 알고리즘 분류 수학 구현 그리디 알고리즘 비트마스킹 문제 풀이 처음에는 구입한 물병의 개수를 0개부터 1개씩 늘려가면서 조건에 맞는 답을 찾으려했다. 근데 이렇게 진행하면 시간초과에 걸린다. 문제를 풀고나서 다른언어들 풀이도 봤는데 다른언어들은 시간초과에 걸리지 않는거같았다.(왜 JS만....ㅠ) 그래서 2진법을 활용해야한다. 주어진 N을 2진법으로 바꾸면 몇개의 물병을 들고가야하는지 알 수 있다. 만약 N이 8이라면 2진법으로 바꿨을때 1000(2) 가 ..

    [JS][백준]1647_도시 분할 계획
    Algorithm/BaeKJoon

    [JS][백준]1647_도시 분할 계획

    문제 번호 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 알고리즘 분류 그래프 이론 최소 스패닝 트리 문제 풀이 최소 스패닝 트리(MST)를 이용하는 문제이다. MST를 사용하기 위해서는 Union-Find 알고리즘을 알아야 한다. 왜냐하면 MST를 만들 때 MST에 사이클(cycle)이 존재하는지 확인해야 하는데 이때 Union-Find 알고리즘이 사용되기 때문이다. Union-Find 알고리즘 코드. function getParent(x, parent) { if (p..

    [JS][백준]회장뽑기
    Algorithm/BaeKJoon

    [JS][백준]회장뽑기

    문제 번호 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 플로이드–워셜 문제 풀이 플로이드 워셜 알고리즘을 사용해서 문제를 풀었다. 플로이드 워셜 알고리즘을 사용해서 각 회원별로 다른 모든 친구까지 몇 다리를 건너서 친구가 될 수 있는지를 조사하면된다. 그 후에 각 회원들별로 가장 많은 친구를 건너서 알 수 있는 친구가 있을때, 이 친구와 몇명의 친구를 통해서 알 수 있는지 찾아보면된다. 예를들어 3번회원이 다른 회원들과 [1, 2, 3, 3, 2, 1..

    [JS][백준]23081_오델로
    Algorithm/BaeKJoon

    [JS][백준]23081_오델로

    문제 번호 23081번: 오델로 첫째 줄에 흑돌을 놓았을 때 가장 많은 백돌을 뒤집을 수 있는 곳을 \((x, y)\) 좌표 순으로 공백으로 구분하여 출력한다. 둘째 줄에 그 좌표에 돌을 두었을 때 뒤집히는 백돌의 개수를 출력한다. www.acmicpc.net 알고리즘 분류 구현 브루트포스 알고리즘 문제 풀이 문제 자체는 어렵지않다. 그냥 시키는 대로 구현만 하면된다. 그런데 검은돌(B)과 검은돌(B)사이에 흰돌(W)만 있어야 하는데 빈공간(.) 다음에 빈공간이 이어지고, 그 뒤에 흰돌(W)가 이어진뒤, 검은돌(B)로 끝나는 경우를 생각하지 못해서 생각보다 오래걸렸다. 문제에서 입력받은 오델로 게임판을 탐색하다가 빈 공간을 발견하면 해당 공간에 검을돌을 놓았을때 몇개의 흰돌을 뒤집을 수 있는지 확인한다...

    [JS][백준]1749_점수따먹기
    Algorithm/BaeKJoon

    [JS][백준]1749_점수따먹기

    문제 번호 1749번: 점수따먹기 동주는 항상 혼자 노느라 심심하다. 하지만 혼자 놀기의 고수가 된 동주는 매일매일 게임을 개발하여 혼자놀기의 진수를 우리에게 보여준다. 어느 날 동주는 새로운 게임을 개발하였다. 바로 점 www.acmicpc.net 알고리즘 분류 다이나믹 프로그래밍 브루트포스 알고리즘 누적 합 문제 풀이 2차원 배열을 활용한 누적합을 사용해야 한다. 그리고 그 누적합들을 모두 살펴보면서 가장 큰 값을 갖는 영역을 찾아야 한다. 우선 2차원 배열을 사용한 누적합이 잘 기억이 안나서 해당 부분만 찾아보았다. 2차원 배열을 사용한 누적합은 가로로의 합, 세로로의 합을 모두 구해야 한다. 따라서 문제에서 주어진 게임판의 크기보다 가로 세로가 1칸씩 더 킨 sum 배열을 만들어서 누적합을 저장할..

    [JS][백준]1495_기타리스트
    Algorithm/BaeKJoon

    [JS][백준]1495_기타리스트

    문제 번호 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 알고리즘 분류 다이나믹 프로그래밍 문제 풀이 처음엔 DFS, BFS를 생각했다. 그러나 시간 초과와, 메모리 초과에 직면했다. 그래서 2차원 배열을 사용해야 한다는 것을 알았다. 세로축을 노래, 가로축을 볼륨으로 생각하자. let dp = new Array(51).fill(null).map(_ => new Array(1001).fill(false)); 이제 주어진 노래만큼 탐색하면서 해당 노래를 시작할 때 해당 볼..

    [JS][백준]1166_선물
    Algorithm/BaeKJoon

    [JS][백준]1166_선물

    문제 번호 1166번: 선물 민식이는 아이들에게 선물할 같은 크기의 작은 박스를 N개 가지고 있다. 모든 작은 박스는 정육면체이고, 크기는 A × A × A 이다. 민식이는 이 작은 박스를 크기가 L × W × H 인 직육면체 박스에 www.acmicpc.net 알고리즘 분류 이분 탐색 문제 풀이 문제를 보자마자 A를 이분 탐색으로 구해야겠구나 싶었다. 근데 A가 정수단위가 아니었다. 그래서 고민을 좀 해봤는데 문제에서 오차는 10^-9까지 허용한다고 되어있다. 그래서 이분 탐색을 진행하되, end - start가 오차보다 작을 때까지만 진행하면 되겠다는 생각이 들었다. function binarySearch() { let ret = 0; let left = 0; let right = Math.max(L..

티스토리툴바