프로그래머스
[JS] 사칙연산
까다로운 DP문제였다. https://school.programmers.co.kr/learn/courses/30/lessons/1843# 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 이전부터 느낀거지만 이런 유형의 DP가 정말 까다로운 것 같다. 문제에서 제공한 1번예제를 분석해보면서 풀이를 생각해보자. ["1", "-", "3", "+", "5", "-", "8"] 먼저 i,j를 왼쪽부터의 인덱스라고 생각해보자. 예를들어 i : 0, j : 1 이라면 1-3까지를 나타낸다고 생각해보자. 그리고 i와 j의 차를 step이라고 생각해보자. ij수0011..
[JS] 도둑질
DP를 활용한 문제였다. https://school.programmers.co.kr/learn/courses/30/lessons/42897 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 직선형인 집이었다면 조금더 쉬웠겠지만 원형이기때문에 조금 생각을 해줘야 하는 DP문제였다. 1. 첫집을 터는 경우 -> 마지막 집과 두번째 집을 털면 안된다. 2. 첫집을 털지 않는 경우 -> 두번째 집 ~ 마지막집까지만 계산하면 된다. dp를 이차원 배열로 두고 dp[i][0] -> i번째 집을 털었다고 가정했을 때의 최댓값 dp[i][1] -> i번째 집을 털지 않았다..
[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] 스티커모으기(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] 셔틀버스 (2018 카카오)
이분탐색을 활용해서 해결하였다. https://school.programmers.co.kr/learn/courses/30/lessons/17678 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 사실 지금생각하면 굳이 이분탐색이 필요할 것 같지는 않고 시뮬레이션을 돌리며 답을 도출해도 될 것 같다. 하지만 시간을 구하는 문제가 나올때 이분탐색을 활용하면 훨신 구조적으로 프로그램을 짤 수 있다. 시간이란 데이터는 항상 정렬되어 있기 때문이다. 이분탐색을 활용하면 문제접근법 자체는 매우 단순해진다. 1. 이분탐색으로 시간 검색 2. 해당 시간에 셔틀을 탈 수 ..
[JS] 매칭 점수
소요시간이 많이 걸린 구현 문제였다. https://school.programmers.co.kr/learn/courses/30/lessons/42893 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 특별한 알고리즘이 필요한 문제는 아니었고 문제에서 구현하라는 대로 풀면 되는 문제였는데 예외 케이스 때문에 스스로는 해결하지 못한 문제였다. 문제의 풀이 자체는 아래와 같다. 1. meta 태그에서 현재 url을 가져옴 2. a태그들을 파싱하여 외부 링크를 가져옴 3. 현재 기본 점수들을 확인함 4. 객체 형태로 외부링크,점수,최종 점수를 저장함. 이때 최종점..