Algorithm/BaeKJoon

    [JS][백준]1238_파티
    Algorithm/BaeKJoon

    [JS][백준]1238_파티

    문제 번호 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 알고리즘 분류 그래프 이론 데이크스트라 문제 풀이 처음엔 플로이드 와샬로 문제를 풀 수 있을 줄 알았다. 그런데 입력을 살펴보니 N의 최댓값이 1000 이였으므로 O(N^3)인 플로이드 와샬은 시간 초과에 걸림이 눈에 보였다. 그렇다면 다음생각은 다익스트라였다. 각집(i)에서 X까지의 최단거리를 다익스트라를 통해서 구한다. X에서 각 집까지의 거리도 마찬가지로 다익스트라로 구하면 된다. 다익스트라의 결괏값은 d라는 2차원..

    [JS][백준]16236_아기 상어
    Algorithm/BaeKJoon

    [JS][백준]16236_아기 상어

    문제 번호 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 알고리즘 분류 구현 그래프 이론 그래프 탐색 너비 우선 탐색 시뮬레이션 문제 풀이 상어 시리즈 문제이다. BFS에 약간의 구현을 곁들이면 쉽게 풀 수 있다. 우리의 아기 상어는 자신보다 작은 물고기를 먹을 수 있고, 더 큰 물고기는 통과하지 못한다. 문제에서 주어진 먹을 수 있는 물고기의 조건을 확인하여 BFS로 먹을 수 있는 물고기를 찾아보자. 우선적으로 가장 가까운 위치의 물고기를 목표로 하기 때문에 BFS에서 최단거리에 있는 물고기를 발견한..

    [JS][백준]2252_줄 세우기
    Algorithm/BaeKJoon

    [JS][백준]2252_줄 세우기

    문제 번호 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 알고리즘 분류 그래프 이론 위상 정렬 문제 풀이 학생들을 '순서'가 있는 방법으로 줄을 세워야 한다. 그래서 위상 정렬을 사용하면 된다. 위상 정렬은 순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 결정해 준다. 항상 알고리즘들이 어떤 조건에서 어떤 결괏값을 내는지(무엇을 구하는 알고리즘인지) 정확히 알고 사용해야 한다. 앞에 서야 하는 학생을 front, 뒤에 서야하는 학생을 back이라고 생각..

    [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)로 끝나는 경우를 생각하지 못해서 생각보다 오래걸렸다. 문제에서 입력받은 오델로 게임판을 탐색하다가 빈 공간을 발견하면 해당 공간에 검을돌을 놓았을때 몇개의 흰돌을 뒤집을 수 있는지 확인한다...

티스토리툴바