문제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..
문제https://www.acmicpc.net/problem/1926 풀이이 문제는 BFS 알고리즘을 이용해 그래프 탐색을 진행해야 한다. 그림은 연결되어 있기 때문에 연결된 노드를 탐색하며 방문했음을 기록해야합니다. 코드const input = require('fs') .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt') .toString().trim().split('\n').map(e => e.split(' ').map(Number));const [y, x] = input.shift();const map = input;const check = Array.from({ length: y }, () ..
문제https://www.acmicpc.net/problem/20056 풀이데이터 구조부터 확인하자. 우선 화염구가 들어갈 지도를 배열을 만들어준다.이때 각 위치에는 화염구의 데이터가 담긴 배열을 담을 수 있는 배열을 추가해준다.이렇게 한다면 위치별 화염구의 정보를 저장할 수 있다. 화염구의 방향은 0부터 7까지 12시 방향부터 10시 방향까지 정해진다.화염구가 진행할 방향을 dir 변수에 2차원 좌표에서의 백터를 저장해준다. 화염구는 한 구역에 여러개 존재할 수 있으며, 2개 이상의 화염구는 서로 합쳐지게된다.이후 4개의 화염구로 나눠지게 되는데, 이때 화염구의 질량, 속도, 방향이 변하게 된다. 질량은 모든 화염구의 질량을 더한 값을 5로 나누고 나머지는 버린 값이 된다.문제에 ⌊(합쳐진 파이어볼 ..
