문제 설명 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 ===..
문제 설명https://www.acmicpc.net/problem/13414문제 풀이 방법이번 문제는 중복 처리 알고리즘 문제이다. 원래는 객체 리터럴을 이용해 인덱스를 저장해 풀이를 진행했지만, 케이스가 길어지면 시간 초과 에러가 발생할 수 있다 생각했다. 그래서 Set 객체를 이용해 다시 풀어봤다. Set은 먼저 나온 요소만 저장하기 때문에 원본 요소의 뒤에 나온 중복 요소를 순서대로 처리할 수 있다.정답 코드const input = require('fs') .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt') .toString().trim().split('\n')const [N, L] = in..
문제 설명 https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 문제 풀이 방법 이 문제는 기본적으로 완전탐색 알고리즘의 일종인 브루트포스 문제이다. 각 기준 높이에 맞는 시간과 최대 높이를 측정하여 정답을 도출한다. 블럭의 최대 높이는 256까지 이므로 반복문을 이용해 0부터 256까지의 기준 높이를 설정하며 각 블럭에서의 기준 높이까지 맞추기위해 필요한 제거 횟수와 채움 횟수를 측정, 제거한 블럭과 기존에 갖고있던 블럭의 수가 넣어야 하는 블럭..
문제 설명 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제 풀이 방법 미로탐색(최단거리 탐색)은 BFS의 대표적인 문제 풀이 방법이다. 이전에 풀었던 문제중 비슷한 문제를 참고해 문제를 풀었다. 코드 const path = __dirname + '/예제.txt'; // /dev/stdin let input = require('fs').readFileSync(path).toString().trim().split('\n').map(e => e.split(' ').map(e ..
문제 설명 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제 풀이 방법 이 문제는 꽤나 유명한 DP문제 중 배낭문제이다. 처음 문제에 접근할 때 DFS으로 접근했지만 시간초과 에러가 발생해 DP 풀이를 참고했다. 물건의 총 갯수 n, 넣을 수 있는 총 무게 maxWeight를 이용해 각 물건을 넣는 시도를 할 때마다 각 무게에서의 최대 가치값을 측정하기 위해 가로가 maxWe..
