문제https://www.acmicpc.net/problem/14503 풀이이 문제는 간단한 구현 및 시뮬레이션 문제이기에 풀이라고 할 것이 딱히 없고 조건만 잘 구현하면 된다. 1) 로봇의 현 위치에서 청소할 수 있는 칸에 있다면 청소한다.2) 동서남북 4칸중 청소할 수 있는 칸이 있다면 반시계 방향으로 돌면서 확인 한뒤 가장 먼저 발견한 칸으로 이동3) 만약 2번에서 청소할 칸이 없다고 판단되면 후진. 후진이 안되는 경우(뒤에 벽이 있다면) 로봇 청소기의 동작을 멈춘다. 코드const input = require('fs') .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt') .toString(..
코딩 테스트/백준
문제https://www.acmicpc.net/problem/14888 풀이해당 문제는 완전탐색 문제이며, 필자는 DFS와 DP를 이용해 풀이했다. 숫자의 순서는 바뀌면 안되기에 연산자를 DP 배열에 담아가며 연산을 검증을 진행했다. 이전에 풀었던 스타트와 링크 문제와 비슷한 흐름으로 해결할 수 있었다. 코드const input = require('fs') .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt') .toString().trim().split('\n').map(e => e.split(' ').map(Number))const N = input.shift()[0];const toolNum =..
문제https://www.acmicpc.net/problem/14499 풀이이 문제는 단순 구현 및 시뮬레이션 문제이다. 다만 조건이 까다로웠다. 주사위가 명령대로 굴러갔을 때의 지도 칸에 있는 숫자에 따라 주사위의 숫자가 변하는지 지도 칸의 숫자가 변하는지 조건을 걸어두는 것을 알아야한다. 코드const input = require('fs') .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt') .toString().trim().split('\n').map(e => e.split(' ').map(Number))const [N, M, y, x, cNum] = input.shift();let comm..
문제https://www.acmicpc.net/problem/14889 풀이이 문제는 완전탐색과 DFS를 이용해 팀원의 조합을 구한 뒤 각 팀원의 조합의 점수 총합을 구한 뒤 양 팀의 점수 차 중 최소 값을 구하는 문제이다. 코드const input = require('fs') .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt') .toString().trim().split('\n')const N = +input.shift();let arr = input.map(e => e.split(' ').map(Number));let answer = Infinity;let visited = new Array(..
문제 설명 https://www.acmicpc.net/problem/14501문제 풀이 방법이 문제는 DP를 이용한 풀이와 DFS를 이용한 재귀 함수로의 풀이가 가능한 문제이다.처음 이 문제를 봤을 때는 조합을 이용해 최대로 받을 수 있는 급여를 뽑아낸다 였지만, 이 문제에서 원하는 것은 근무일 수 혹은 상담 시간의 조합이 아니라 받을 총 급여의 최대값이라 DP를 이용해 풀었다. 나는 DP를 이용해 풀이를 진행해보았다. 최근 풀었던 가장 긴 바이토닉 부분 수열 문제에서 아이디어를 얻었다. 스케줄을 순회하며 급여를 체크하는 방향으로 설계했다. 이 문제에서는 주어진 스케줄의 역순으로 순회하며 값을 구했다.문제에서 처음 상담을 시작한 날짜에 따라 받게되는 급여의 최대값이 달라지기 때문이다. 정답 코드const..
문제https://www.acmicpc.net/problem/11054풀이이번 문제는 DP를 이용한 LIS 알고리즘 문제이다.처음 이 문제를 보고 바이토닉 수열이라는 개념에 대해 이해하기 쉽지 않았다... 각 자리수에서 좌/우로 증가, 감소하는 수들의 개수의 최대값을 구하는 문제이다. 좌에서 우로 이동하며 증가하는 수의 연속과 우에서 좌로 이동하며 증가하는 수의 연속을 측정한다. 이 두가지 과정의 결과를 이용해 바이토닉 수열의 최대값을 구할 수 있다. 각 과정에서 나온 증가되는 수의 개수는 dp1, dp2에 담기며, 두 배열에서 인덱스가 같은 값들을 더해주고, 이 중 최대 값을 제출한다. 코드const input = require('fs') .readFileSync(process.platform ===..
