문제https://www.acmicpc.net/problem/2003 풀이투포인터의 기본 문제이며, 주어지는 수열에서 연속된 수들의 합이 M이 되면 카운트를 올리는 문제이다. 이 문제에서 while 문을 이용해 반복해주는 부분이 있는데, 이 while 문의 조건에 원래는 lp 코드const input = require('fs') .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt') .toString().trim().split('\n');const [n, m] = input.shift().split(' ').map(Number);const arr = input[0].split(' ').map(Num..
코딩 테스트/백준
문제https://www.acmicpc.net/problem/5972 풀이다익스트라다와 BFS 알고리즘을 이용한 문제이며, 필자는 큐를 이용한 풀이를 진행했다. 1번부터 시작하며 큐에 시작하는 위치를 저장하고 순회를 시작한다. 순회하며 각 지점에 도달하기 까지의 최소 비용을 측정한다. 최단 거리의 경우 st 지점부터 ed 지점까지 소요되는 비용을 더하며 최소 비용을 구한다. 코드const input = require('fs') .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt') .toString().trim().split('\n').map(e => e);const [n, m] = input.shi..
문제https://www.acmicpc.net/problem/9655 풀이이 문제는 수학적으로 접근했다. 문제에서 나오는 두 인물은 오직 1개 혹은 3개만 가져갈 수 있으며, 주어지는 돌의 갯수에 따라 승자가 결정된다.홀수의 경우 먼저 돌을 가져간 사람이 이기며, 짝수의 경우 나중에 돌을 가져간 사람이 이기게 된다. 코드const input = require('fs') .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt') .toString().trim().split('\n').map(e => e);const n = input.shift();console.log(n % 2 === 1 ? 'SK' :..
문제https://www.acmicpc.net/problem/2493 풀이이 문제를 처음 풀때는 순회 방식을 이용해 풀이했지만, 시간초과가 발생했다. 이 문제를 풀려면 스택 알고리즘을 이용해야 한다. 스택에 차례대로 타워들을 넣어야 하는데, 이때 기존 스택 마지막에 있던 타워보다 작은 타워는 스택에 들어가지 않고 바로 수신을 받는(스택에 있는 타워) 위치 번호를 답으로 저장한다. 만약 현재 타워가 더 크다면 기존에 있던 타워들 중 현재 타워보다 작은 타워들을 모두 pop해준다. 이때 중의해야할 것은 현재 타워보다 작은 타워들만 없애줘야한다. 이유는 다음에 올 타워들 중 현재 타워보다는 크고 기존 스택의 타워보다 작은 타워가 올 수 있기 때문이다. 코드const input = require('fs') ...
문제https://www.acmicpc.net/problem/2230 풀이전형적인 투 포인터 알고리즘을 이용해 두 수를 이용하는 문제다. 이 문제는 약간의 수학적인? 사고가 필요하다.입력으로 받는 수열의 경우 정렬되지 않은 상태이다. 이런 수열 그대로를 투 포인터를 이용해 문제풀이 한다면 모든 경우의 수를 탐색해야 하기에 시간복잡도가 커질 수 있다. 이런 문제는 수열을 오름차순으로 정렬해주면 해결할 수 있다. 위의 경우에서 m보다 두 수의 차가 커졌다고 생각하자. 그렇다면 현제 lp에서 rp가 오른쪽의 수는 탐색할 이유가 있는가? 절대로 없다. 이유는 차가 가장 작은 수를 찾아야 하기 때문에 rp가 증가해 현제 lp와의 차가 커지는 수는 탐색할 필요가 없기 때문이다. 코드const input = requ..
문제https://www.acmicpc.net/problem/2579 풀이처음 이 문제를 풀때는 BFS로 접근했지만 나는 풀이 방법을 찾지 못했다... 시간초과 에러가 발생했다.... 그래서 순수하게 동적 계획법을 사용해 풀이하기로 결정했다. 이 문제를 잘 보면 특정 패턴이 보일 것이다. n 번째에 도달하는 방법은 두가지가 있다. 첫 번째로는 n-1 번째에서 한칸 뛰어넘어 온 경우이고, 두 번째는 n-2 번째에서 두칸을 넘어온 경우이다. 이때 두칸을 넘어온 경우는 문제가 되지 않지만, 한 칸을 넘어온 경우는 3칸을 연속해서 넘으면 안된다는 제한이 있다. 위와 같은 제한을 피하는 방법은 n-3칸에서 두칸 넘고 n-1칸에서 한칸 넘는 방법이 있다. 코드const input = require('fs') .r..
