Algorithm

    [JS][백준]2493_탑
    Algorithm/BaeKJoon

    [JS][백준]2493_탑

    문제 번호 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 알고리즘 분류 자료 구조 스택 문제 풀이 문제를 읽어보면 i번째 타워에서 왼쪽으로 검색해서 가장 먼저 만나는 i번째 타워의 높이보다 크거나 같은 타워를 찾으면 된다. 근데 i번째 타워마다 매번 검색을 하기엔 500,000개의 타워를 검색해야 하기 때문에 시간 초과에 걸릴 것이라 생각했다. 그렇다면 어떻게 빠르게 검색을 할것인가에 대해서 고민했다. 처음에는 높이 순으로 이분 탐색을 진행하려 하였으나 타워들의 높이가 정렬된 순서가 아니니 불가능했다. 우..

    [JS][백준]1504_특정한 최단 경로
    Algorithm/BaeKJoon

    [JS][백준]1504_특정한 최단 경로

    문제 번호 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 알고리즘 분류 그래프 이론 데이크스트라 문제 풀이 문제에서 요구하는 것이 '최단 경로'이기 때문에 다익스트라 알고리즘과 플로이드와샬 알고리즘을 생각해봤다. 플로이드와샬을 먼저 생각해봤는데 주어지는 정점의 개수가 최대 800개 이므로 아슬아슬하게 시간 초과에 걸릴 것 같았다. 그래서 다익스트라 알고리즘을 사용하기로했다. 다익스트라 알고리즘을 알고 있다면 문제는 매우 쉽다. 다익스트라 알고리즘은 출발점을 기준으..

    [JS][백준]14499_주사위 굴리기
    Algorithm/BaeKJoon

    [JS][백준]14499_주사위 굴리기

    문제 번호 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 알고리즘 분류 구현 시뮬레이션 문제 풀이 구현 문제에서 자주 등장하는 배열을 돌리는 방법을 알고 있다면 어렵지 않게 풀 수 있다. 그러니 우선 배열을 돌리는 방법에 대해서 생각해보자. 배열은 두 가지 방향으로 돌릴 수 있다. 오른쪽, 왼쪽 말이다. 우선 오른쪽으로 돌려본다. 왼쪽에 있던 내용물은 한 칸 오른쪽으로 이동해야 하고 가장 마지막 칸에 있는 내용물은 0번 인덱스로 가야 한다. 돌..

    [JS][백준]1916_최소비용 구하기
    Algorithm/BaeKJoon

    [JS][백준]1916_최소비용 구하기

    문제 번호 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 알고리즘 분류 그래프 이론 데이크스트라 문제 풀이 모든 도시에서 모든 도시까지의 최소비용을 구하는 문제인 줄 알고 플로이드 와샬 알고리즘을 쓰려했으나 문제를 잘 읽어보니 A->B로의 최단거리만 구하면 되는 문제였다. 만약 플로이드와샬을 사용했었다면 O(N^3)의 시간 복잡도가 소요되므로 시간 초과에 걸렸을 것이다. 다익스트라알고리즘을 사용했다. 다익스트라의 시간 복잡도는 O(N*logN)이므로 시간제한인 0.5초 안에..

    [JS][백준]1107_리모컨
    Algorithm/BaeKJoon

    [JS][백준]1107_리모컨

    문제 번호 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 알고리즘 분류 브루트포스 알고리즘 문제 풀이 채널의 범위가 왜 무제한까지 있는지와 몇 가지 경우만 잘 생각한다면 브루트포스 알고리즘을 사용해서 쉽게 풀 수 있다. N의 범위는 최대 500,000 이지만 채널의 범위는 무제한이다. 이는 500,000보다 큰 채널에서 500,000 채널로 올 수 있다는 뜻이다. 이점을 놓치면 탐색하는 채널의 범위를 500,000으로 제한하는 실수를 할 수 있다. 시작 채널이 100이므로 500,000 -1..

    [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이라고 생각..

티스토리툴바