Algorithm/BaeKJoon

    [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][백준]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원을 만드는 최소 개수..

    [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..

티스토리툴바