FrontEnd/프로그래머스
[JS] 가장 긴 팰린드롬
3단계 치고는 간단(?) 한 문제였다. https://school.programmers.co.kr/learn/courses/30/lessons/12904 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 사실 특별한 알고리즘 기법이 들어가진 않았다. 펠린드롬은 짝수인 경우와 홀수인 경우 두가지가 존재한다. 문자열을 처음부터 순회하며 해당 점을 꼭지점으로 삼아 만들 수 있는 홀수인 펠린드롬과 짝수인 펠린드롬의 개수를 갱신해나가면 된다. function solution(s) { const getPalindromeCnt = (start,end) => { let l..
[JS] 거스름돈 (자세한 설명)
까다로운 dp문제였다. https://school.programmers.co.kr/learn/courses/30/lessons/12907 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제에서 보여지는게 dp문제였기 때문에 고민을 많이 해봤다. dp[n]을 n원을 만들기 위한 경우의 수라고 생각을 해보자. 단순하게 생각한다면 5라는 놈을 만들기 위해서 dp[1]*dp[4] + dp[2]*do[3] 과 같은 조합으로 만들수 있지 않나? 라는 생각을 했다. dp[n] = dp[n-1]*dp[n] + dp[n-2] + dp[n-3] + ... [dp[n-n/2..
[JS] 선입선출 스케줄링
이분탐색으로 해결할 수 있는 문제였다. https://school.programmers.co.kr/learn/courses/30/lessons/12920# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제는 단순한데 비해서 시간은 굉장히 오래걸린 문제였다. 효율성 부분이 굉장히 악독했다... 처음에는 우선순위 큐를 활용하여 선입선출 과정을 직접 구현하여 해결하려 했다. class minQue { constructor() { this.ary = [0]; } swap(a, b) { [this.ary[a], this.ary[b]] = [this.ary[b],..
[JS] 스티커모으기(2)
dp를 활용하여 해결하였다. https://school.programmers.co.kr/learn/courses/30/lessons/12971 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 처음에 dp를 활용하여 해결하려 했다. 2차원 배열의 dp를 활용하여 dp[i] = [a,b] 라는 꼴을 두었을때 i번째 스티커까지의 최고합 = [ i번째 스티커를 찢은경우 , i번째 스티커를 찢지 않은경우 ] 이런식으로 스티커를 찢은 경우와 안찢은 경우를 기록해나가며 문제를 해결하였다. 이때 dp[i][0] = dp[i-1][1] + sticker[i] 라는 점화식이..
[JS] 기지국 설치
그리디를 활용하여 해결하였다! https://school.programmers.co.kr/learn/courses/30/lessons/12979# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 먼저 stations 배열을 정렬을 해준다. 이후 기지국을 넣어줘야하는 구간을 구해준 후 해당 구간에 설치해야 하는 기지국 수를 더해주면서 구해줬다. 여기까진 크게 어렵지 않은데 신경써야할 부분이 2가지 정도가 있다. 1. 구간이 음수로 나오는 경우 기지국 설치가 필요없는 경우이므로 패스해준다. 2. 마지막 기지국부터 마지막 아파트까지의 부분을 생각해줘야 한다. f..
[JS] [1차] 추석 트래픽
누적합과 Map 자료형을 활용해서 해결하였다. https://school.programmers.co.kr/learn/courses/30/lessons/17676 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제는 단순하지만 ms까지 시간이 주어지는 바람에 조금 까다로웠고 생각할 거리가 조금 있는 문제였다. 해당 문제를 해결하기 위해서 누적합 개념을 적용해볼 수 있다. 시간은 0부터 1씩 증가하는 형태의 데이터로 생각할 수 있다. 0ms부터 10ms까지의 상태를 배열로 나타낸다면 0,0,0,0,0,0,0,0,0,0,0 과 같은 형태로 나타낼 수 있다. 여..