Algorithm

    [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); } 이제 모든 작업이 마감시간 안에 끝날 수 있는지 판단해야 한다. 마감시간이 빠른 순서로 정렬해 두었기 때문에 작업에 소요되는 시간을 누적으로 더하면서 마감시간 이전에 끝낼 수 있는지 확인한다. 이 과정을 진행하면서 누적된 작업시간과 마감시간의 차이가 최소가 될 때를 기억해둔다. 이 값이 '존'이 최대한 늦게 일어날 수 있는 시간이다. 누적시간이 마감시간을 넘기면 해당 일들을 제때 진행할 수 ..

    [JS][백준]17845_수강 과목
    Algorithm/BaeKJoon

    [JS][백준]17845_수강 과목

    문제 번호 17845번: 수강 과목 첫줄에 서윤이의 최대 공부시간 N (1 ≤ N ≤ 10,000), 과목 수 K (1 ≤ K ≤ 1,000)이 공백을 사이에 두고 주어진다. 이후 K개의 줄에 중요도 I (1 ≤ I ≤ 100,000), 필요한 공부시간 (1 ≤ T ≤ 10,000)이 www.acmicpc.net 알고리즘 분류 다이나믹 프로그래밍 배낭 문제 문제 풀이 처음엔 그리디를 활용한 문제인 줄 알았다. 그래서 단위 시간당 중요도를 계산해서 그 결과값이 높은 순서로 수강 과목을 선정하려 했으나 오답인걸 알았다. 문제를 다시 살펴보니 DP를 사용해야 하는 문제라는 생각이 들었고 중요도와 공부시간이라는 2개의 입력이 있는 걸 보고 Knapsack을 사용할 수 있을지 생각해보았다. Knapscak 알고리..

티스토리툴바