백준

[백준 / Java] 1504번 : 특정한 최단 경로

문제 방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다. 세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지..

[백준]1107번 리모컨

문제 https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 문제 풀이 필자는 해당 문제를 처음에는 수학적으로 접근을 하였다. 하지만 계속되는 예외 케이스들에 걸려 계속 오답처리가 되었다. 6번을 틀리고 나서 문제 풀이 방법을 변경하였다. 해당 문제의 제시된 조건을 보면 제한 시간이 2초였다. 그래서 브루트포스로 접근해보았다. 최대 목표 채널은 500,000 이므로 최대 자리수를 10의 6승에서 내려가는 것이 최대 크기일 것이다. 즉 ..

[백준] 1072번 Z _ Node_js

문제 https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 문제 풀이 해당 문제는 규칙을 찾아 해당 규칙을 통해 답을 구하는 수학 문제이다. 숫자의 진행 방향은 Z모양으로 2^n X 2^n 단위로 진행이 된다. 그렇기에 여기서 규칙을 찾을 수 있다. 아래 그림을 보자. Z모양의 크기는 2^2k만큼 증가하는데 이를 x축과 y축 별로 증가하는지 작성해보았다. 각 x축은 2^2x, y축은 2^(1+2y)만큼 씩 증가한다. 그렇기에 시작점을 수학적..

[백준] 1003번 피보나치 함수 _ Node.js

문제 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 문제풀이 해당 문제를 조금 잘라서 나타냈는데 결국 피보나치 수열을 진행하면서 f(0)과 f(1)을 각 몇 번씩 사용하는지 출력하는 문제이다. 해당 문제는 피보나치 수열을 구하는 DP문제에서 값을 저장하는 것이 아닌 f(0)과 f(1)을 사용하는 횟수를 저장하면 된다. 제출 코드 const fs = require('fs'); const stdin = (process.platform === 'linux'? fs.readFileSync('/dev/stdin').toString() : `2 6 ..

[뻘글]백준 solved.ac Class 2++ 달성!

코딩테스트 대비한다고 어려운 문제들만 풀다가 생각나서 하루에 한두개씩 천천히 풀기 시작했는데 드디어 class 2++ 달성했다. class 2문제는 가끔 어려운 문제가 있는 정도라 어렵진 않았지만 문제가 꽤 많아 오래걸린 것 같다. 바로 class3 달성을 목표로 시작해야겠다. class3 문제부터는 슬슬 어려워지는 것 같아 도움이 많이 될 것 같다.

[백준] 18111번 마인크래프트 _ Node.js

문제 https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 문제 풀이 해당 문제는 문제가 길지만 정리하면 간단한 수학 문제이다. 땅을 캐는데는 2라는 시간이 소모되고, 땅을 채우는데는 1이라는 시간이 소모된다. 이 때 땅을 채우기 위해서는 인벤토리에 땅 블록이 있어야지만 가능하다. 문제는 최대 층에서 최소층까지 진행하며 해당 층을 만들기 위해서는 얼마의 시간이 필요한지 확인하면 된다. x라는 층을 만들기 위해서는 x보다 높은 블록을 제거하고, x ..