개발개발

1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/12907 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이 DP를 이용해 문제를 풀이한다. DP[N]이 N에 해당하는 거스름돈을 구하는 방법의 갯수를 의미한다면. DP[N]은 DP[N-화폐 종류 1] + DP[N-화폐 종류 2] + DP[N-화폐 종류 3]....이라고 생각할 수 있다, 위 내용을 for문을 사용해 구현하면 아래의 코드와 같다. 이 때, 화폐 하나로만 거스름돈을 채울 수 있는 경우를 포함하기 위해 DP[0] = 1로 ..

1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/12971?language=java# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이 스티커 판이 원형이므로 sticker[0]을 선택할 경우 sticker[n-1](n은 길이) 값을 선택할 수 없으며, sticker[n-1]을 선택할 경우 sticker[0]을 선택할 수 없다 따라서, sticker[0]을 선택하는 경우와 그렇지 않은 경우로 나눠 DP를 계산한다. 기본적으로 현재 위치에서 두 경우 중 유리한 값을 선택한다. 현재 위..

1. 문제 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 2. 풀이 DP를 이용해 풀이한다. 2차원 배열로 DP를 진행한다. 첫번째 인덱스는 무게를 의미한다. dp[k][n]일 경우, k 무게 만큼 버티고 있을 때다. 두번째 인덱스는 물품의 인덱스를 의미한다. dp[k][n]일 경우, n번째 물건까지를 고려했을 때다. 즉, DP 배열에 저장되는 값은 인덱스에 해당하는 물건들의 ..

1. 문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 2. 풀이 입력 받은 수부터 연산을 수행해가며 가장 횟수가 적은 경우를 얻기 위해 DP 배열에 각 경우의 값을 저장한다. 입력 받는 수를 X라 했을 때, X/3, X/2 X-1로 총 3가지 연산이 가능하다. 세 연산이 모두 가능한 상황 일 경우 X-1이 가장 큰 연산횟수가 드는 것이 확실히며 X-1 연산은 모든 경우에 가능하므로 X-1 연산을 한 경우의 값을 DP 배열에 가장 먼저 저장한다. X-1 연산을 수행할 경우의 결과를 기본 값으로 두고 두 연산이 가능할 경우에 각각의 연산을 수행해 두 연산(..