Algorithm/BaeKJoon

    [JS][백준]14627_파닭파닭
    Algorithm/BaeKJoon

    [JS][백준]14627_파닭파닭

    문제 번호 14627번: 파닭파닭 첫째 줄에 승균이가 시장에서 사 온 파의 개수 S(1 ≤ S ≤ 1,000,000), 그리고 주문받은 파닭의 수 C(1 ≤ C ≤ 1,000,000)가 입력된다. 파의 개수는 항상 파닭의 수를 넘지 않는다. (S ≤ C) 그 후, S 줄에 www.acmicpc.net 알고리즘 분류 이분 탐색 문제 풀이 문제의 알고리즘은 어렵지 않은 이분 탐색이다. 처음엔 주어진 파들을 무조건 사용해야 하는줄 알고 이분탐색의 최대 범위를 가장 짧은 파의 길이로 두고 했다가 틀렸었다. 그런데 수의 범위가 크기 때문에 BigInt를 사용해야 한다. 이때 BigInt의 연산 시간은 상수 시간이 아니므로 무분별하게 BigInt를 사용한다면 같은 알고리즘 이더라도 시간 초과에 걸리게 된다. 때문에..

    [JS][백준]7682_틱택토
    Algorithm/BaeKJoon

    [JS][백준]7682_틱택토

    문제 번호 7682번: 틱택토 틱택토 게임은 두 명의 사람이 번갈아가며 말을 놓는 게임이다. 게임판은 3×3 격자판이며, 처음에는 비어 있다. 두 사람은 각각 X 또는 O 말을 번갈아가며 놓는데, 반드시 첫 번째 사람이 X를 놓고 www.acmicpc.net 알고리즘 분류 구현 문제 풀이 게임이 끝날 수 없는 경우의 수를 생각하여 'invalid'를 반환해준다. 전체코드 const input = require('fs').readFileSync('dev/stdin').toString().trim().split('\n'); function main() { let answer = ''; for (let testCase = 0; testCase < input.length; testCase++) { if (inp..

    [JS][백준]16935_배열 돌리기3
    Algorithm/BaeKJoon

    [JS][백준]16935_배열 돌리기3

    문제 번호 16935번: 배열 돌리기 3 크기가 N×M인 배열이 있을 때, 배열에 연산을 R번 적용하려고 한다. 연산은 총 6가지가 있다. 1번 연산은 배열을 상하 반전시키는 연산이다. 1 6 2 9 8 4 → 4 2 9 3 1 8 7 2 6 9 8 2 → 9 2 3 6 1 5 1 8 3 4 2 9 → www.acmicpc.net 알고리즘 분류 구현 문제 풀이 문제를 잘 읽고 하라는대로 하면된다. 배열을 돌렸을때 가로와 세로가 바뀌는 것에 주의한다. 정확히 중간에 위치한 값들은 뒤집는 연산을 진행해도 그대로 유지되기 때문에 'parseInt(N/2)'와 'Math.ceil(N/2)'를 적절하게 사용하여 정 가운데 위치한 값은 건드리지 않도록 하였다. 전체코드 const input = require('fs..

    [JS][백준]14699_관악산 등산
    Algorithm/BaeKJoon

    [JS][백준]14699_관악산 등산

    문제 번호 14699번: 관악산 등산 서울대학교에는 “누가 조국의 미래를 묻거든 고개를 들어 관악을 보게 하라”라는 유명한 문구가 있다. 어느 날 Unused는 Corea에게 조국의 미래를 물었고, Corea는 직접 관악산에 올라가 조국의 미 www.acmicpc.net 알고리즘 분류 다이나믹 프로그래밍 그래프 이론 문제 풀이 모든 정점마다 BFS를 시도했을 때는 메모리 초과에 걸렸고, DFS를 시도했을 때는 시간 초과에 걸렸다. 그래서 위상 정렬을 생각해 봤는데 이 문제에 어떻게 활용해야 할지 모르겠어서 다른 방법을 생각해봤다. 각 노드 까지의 거리가 아니라 각 노드부터 위로 올라가는 형식이기 때문에 위에서부터 거꾸로 내려오면서 쉼터의 개수를 세어보기로 했다. 생각해보니 탐색의 시작을 위에서 부터 할 ..

    [JS][백준]17352_여러분의 다리가 되어 드리겠습니다!
    Algorithm/BaeKJoon

    [JS][백준]17352_여러분의 다리가 되어 드리겠습니다!

    문제 번호

    [JS][백준]14600_샤워실 바닥 깔기 (Small)
    Algorithm/BaeKJoon

    [JS][백준]14600_샤워실 바닥 깔기 (Small)

    문제 번호 14600번: 샤워실 바닥 깔기 (Small) 첫 번째 줄에는 바닥의 한 변의 길이를 표현하는 자연수 K(1 ≤ K ≤ 2) 가 주어진다. 이때 바닥의 크기는 2K 가 됨에 유의하라. 두 번째 줄에는 배수구의 위치를 나타내는 자연수 x, y (1 ≤ x, y ≤ 2K) www.acmicpc.net 알고리즘 분류 구현 분할 정복 문제 풀이 백트래킹, 브루트포스를 사용하면 된다. 빈 공간을 발견할때마다 4가지 도형을 넣어보면서 문제에서 주어진 조건대로 모든 칸을 채울 수 있는지 백트래킹으로 확인해보면 된다. 그래서 주어진 4가지 도형을 나타낼 배열을 사용했다. (가운데가 현재 좌표이다) // 1,2,3,4 모양 let dx = [[0, 0, 1], [0, 1, 1], [0, 0, -1], [0, ..

    [JS][백준]15724_주지수
    Algorithm/BaeKJoon

    [JS][백준]15724_주지수

    문제 번호 15724번: 주지수 네모 왕국의 왕인 진경대왕은 왕국의 영토를 편하게 통치하기 위해서 1X1의 단위 구역을 여러 개 묶어서 하나의 거대 행정구역인 주지수(州地數, 마을의 땅을 셈)를 만들 예정이다. 진경대왕은 www.acmicpc.net 알고리즘 분류 다이나믹 프로그래밍 누적 합 문제 풀이 누적 합을 이용하여 풀 수 있다. 주어진 문제의 영토의 각 줄마다 가로의 누적합을 구해준다. function makeSum(){ for(let i=0; i

    [JS][백준]6068_시간 관리하기
    Algorithm/BaeKJoon

    [JS][백준]6068_시간 관리하기

    문제 번호 6068번: 시간 관리하기 성실한 농부 존은 시간을 효율적으로 관리해야 한다는 걸 깨달았다. 그는 N개의 해야할 일에 (1 { let A = a[1]; let B = b[1]; if(A B) return 1; return 0; }) sol(works); } 이제 모든 작업이 마감시간 안에 끝날 수 있는지 판단해야 한다. 마감시간이 빠른 순서로 정렬해 두었기 때문에 작업에 소요되는 시간을 누적으로 더하면서 마감시간 이전에 끝낼 수 있는지 확인한다. 이 과정을 진행하면서 누적된 작업시간과 마감시간의 차이가 최소가 될 때를 기억해둔다. 이 값이 '존'이 최대한 늦게 일어날 수 있는 시간이다. 누적시간이 마감시간을 넘기면 해당 일들을 제때 진행할 수 ..

티스토리툴바