문제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') ...
문제 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이이 문제는 DP 알고리즘을 이용해 풀이하는 문제이다. 이 문제를 보면 홀수 길이의 경우 절대 조건을 만족하는 경우가 없기에 0을 반환한다. 짝수 길이의 경우 점화식이 존재한다. 처음에는 어떻게 점화식을 만들지 잘 몰랐다. 하지만, 조금 더 생각해보면 짝수 길이만 되며, 이전의 경우를 이용한 경우를 추가하며 이전 값들을 이용하는 DP 알고리즘의 이용이 필요하다는 것을 알게되었다. 점화식은 ((dp[i - 1] * 4)) - (dp[i - 2]) % 1000000007 이지만, 이 경우는 dp[i - 1]..
문제 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이이 문제와 같이 큰 범위내에서 특정 조건을 만족하는 최소값 혹은 최대값을 찾는 탐색 문제의 경우 완전 탐색을 진행하면 시간초과가 발생할 수 있기에 이분탐색 알고리즘을 이용해 풀이해야 한다. 사실 이 문제는 이분탐색 알고리즘만 잘 구현하면 어려운 부분은 없다. 그나마 문제를 틀렸을 경우 시간을 더해주는 로직 구현에 시경을 써야 한다는 점 빼면 그렇게 어려운 문제는 아닌것같다. 코드const solution = (diffs, times, limit) => { let [lp, rp] = [1, diffs.r..
문제https://school.programmers.co.kr/learn/courses/30/lessons/150369?language=javascript 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이이번 문제는 단순한 수학을 통해 풀 수 있는 문제다. 문제를 파악해 보면, 결국 맨 끝 집은 찍어야 하므로 필자는 맨 끝집부터 탐색을 시작했다. 끝에서 부터 배달 및 수거한 갯수를 측정해 이 값들이 모두 양수일 때 까지 cap 만큼 더해주는 과저을 반복한다. 코드function solution(cap, n, deliveries, pickups) { le..
문제https://school.programmers.co.kr/learn/courses/30/lessons/250136 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이그냥 일반적인 BFS 문제로 처음 파악을 했다. 근데 풀어보니 틀리기도 했고 효율성 검사도 통과하지 않았다.const bfs = (arr, x) => { const start = Array.from({length: arr.length}, (_, i) => [i, x]); for(let i = 0; i = 0 && ny >= 0 && nx 1) continue; ..
