https://school.programmers.co.kr/learn/courses/30/lessons/118668
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제분석:
문제목표: 모든 문제를 풀 수 있을때까지 알고력과 코딩력을 단련시키자!
처음에 주어지는 초기 알고력과 코딩력이 있습니다.
이 알고력과 코딩력을 증가시키기위해선 다음과 같은 (선택지)방법이있습니다.
1. 트레이닝
트레이닝의 경우는 시간 1을소비해, 알고력 또는 코딩력중 1을 높일 수 있습니다.
2. 문제풀기
문제풀기의 경우는 일정한 시간을 소비해, 효율이 좋은 알고력 , 코딩력을 얻을수 있습니다.
단, 문제를 풀려면 알고력과 코딩력의 입장제한이 있습니다.
당신은 저 2가지의 선택을 적절히 골라 최소시간으로 목표치 알고력과 목표 코딩력을 도달해야합니다.
필자가 해당 문제를 접근한 방법
1. 완전탐색
음.. 트레이닝과 문제풀기를 적절히 섞어서 사용하니 완전탐색으로 모든 경우를 구해버리면 되지않을까..?
-> 구현 시작 -> 20분뒤 -> 효율성 에러
2. 이분탐색 + 완전탐색(BFS)
효율성을 조금도 최적화시켜보고자, 시간을 이분탐색한뒤, 그 시간동안 알고력,코딩력이 도달이 가능한지(BFS) 판단하는 식으로 짜봣다.
->구현시작 -> 20분뒤 -> 아직도 효율성 에러
???????? 완전탐색없이 어떻게 하라는거지 멘탈 바사삭
https://tech.kakao.com/2022/07/13/2022-coding-test-summer-internship/
2022 테크 여름인턴십 코딩테스트 해설
2022년 카카오 여름 인턴십 코딩 테스트가 지난 5월 7일에 5시간에 걸쳐 진행되었습니다. 시간이 부족하여 문제를 풀지 못하는 아쉬움이 없도록 1시간을 늘려 테스트를 진행한 것이 작년과 조금
tech.kakao.com
그렇다 이 문제는 DP문제였다. 안그래도 DP 숙련도가 낮은데 약점공격을 당했다.
3. DP 설계 시작
DP 동적계획법은 두가지 접근이있다. Bottom_UP 으로할지 Top_Down으로 할지
전자는 작은 조각들을모아 목표치를 만드는것이고, 후자는 목표치를 잘게 쪼게어 작은조각들을 더하는식이다.
지금 우리가 정확하게아는 자료가 초기 알고력, 초기코딩력이니 Bottom_UP을 채용하자!
동적 계획법은 이미 계산한 작은 조각들을 또 다시 계산할 필요가없는 특징이 있다.
즉, 계산한 작은 조각들을 저장할 배열이 하나 필요하다라는 뜻이다.
목표치를 도달햇는지 판단하는값이 알고력, 코딩력이기 때문에
int[][] 2차 배열을통한 DP를 구현한다.
초기 DP는 모두 높은값을 부여한다. -> 그 이유는 최소횟수를 매번 갱신해야하기때문이다.
초기 스타트지점 설정 : dp[alp][cop] =0
본격적으로 DP를 구현해보자
우리는 선택지 3개가있다.
1. 알고력 트레이닝
2. 코딩력 트레이닝
3. 문제풀기
다음과같은 모든 경우를 넣어줘야한다.
1.알고력 트레이닝 : dp[i+1][j]=Math.min(dp[i+1][j],dp[i][j]+1);
2.코딩력 트레이닝 : dp[i][j+1]=Math.min(dp[i][j+1],dp[i][j]+1);
3. 문제풀기 : dp[i+alp_rwd][j+cop_rwd] =Math.min(dp[i+alp_rwd][j+cop_rwd], dp[i][j]+cost)
(단, i >= alp_req이고 j >= cop_req)
모든 경우를 탐색하면 시간복잡도가 O(목표알고력*코딩알고력*문제길이) 가 나온다.
이 과정이 끝난후 dp[목표알고치][목표코딩치] 를 반환하면된다.
----------------------------------------------------------------------------------------------------------------------------------
이게 끝일까? X
문제풀기는 다음과 같은 예외가 존재한다.
EX) 목표 코딩 20 , 목표 알고 20, 현재 알고력 18 , 현재 코딩력15 일때,
문제 1번을 풀었을때 얻는 알고력이 5 코딩력이 5라고 가정하자.
1번을 풀면 무슨일이 벌어질까, 목표 코딩, 목표알고는 20인데 자신의 스탯은 알고력 23, 코딩력 20이다.
결과적으로 dp[목표알고치][목표코딩치]를 반환해야하는데, 위에있는 케이스를 놓친다.
그렇다면 우리가 해줘야할것은 알고력이 목표알고력을 넘엇을때, 교정작업 (알고력 23= 목표알고력 20) 을 해야한다.
케이스 1. 둘다 목표치를 넘겻을때,
케이스 2. 알고력만 목표치를 넘겻을때
케이스 3. 코딩력만 목표치를 넘겻을때
케이스 4. 둘다 목표치를 안넘겻을때
아직 안끝났다.
문제에서 예시를 안들었을뿐이지, 처음부터 초기 알고력과 코딩력을 엄청 높게 잡아줄수도있다.
EX) 초기 알고력 25 초기 코딩력 25 목표 알고력 10 목표 코딩력 10
-> 이와 같은경우는 DP돌릴필요도없이 바로 0을 반환해야한다.
다음과 같은 케이스도 있을수 있다.
EX) 초기 알고력 25 초기 코딩력 0 목표 알고력 10 목표 코딩력 10
-> 이와 같은경우는 처음 DP배열을 생성할때 new dp[목표알고+2][목표코딩+2] 로 설정하는게 대부분일텐데
다음과같은 케이스를 받으면 초기 알고력 25 때문에 바로 런타임 에러가 뜰것이다. (idx 오류)
즉, 초기 알고력> 목표알고력이면, 초기알고력 =알고력으로 교정작업을 해주자.
전체 문제풀이:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
|
import java.util.*;
class Solution {
public int solution(int alp, int cop, int[][] problems) {
int goal_a=0;
int goal_c=0;
//목표치를 구하는 for문
for(int i =0; i<problems.length;i++){
goal_a=Math.max(problems[i][0],goal_a);
goal_c=Math.max(problems[i][1],goal_c);
}
if(goal_a<=alp&&goal_c<=cop){
return 0;
}
if(alp>=goal_a){
alp=goal_a;
}
if(cop>=goal_c){
cop=goal_c;
}
int[][] dp =new int[goal_a+2][goal_c+2];
for(int i=alp;i<=goal_a;i++){
for(int j=cop;j<=goal_c;j++){
dp[i][j]=Integer.MAX_VALUE;
}
}
dp[alp][cop]=0;
for(int i=alp;i<=goal_a;i++){
for(int j=cop;j<=goal_c;j++){
dp[i+1][j]=Math.min(dp[i+1][j],dp[i][j]+1);
dp[i][j+1]=Math.min(dp[i][j+1],dp[i][j]+1);
for(int[] p :problems){
if(i>=p[0]&&j>=p[1]){
if(i+p[2]>goal_a&&j+p[3]>goal_c){
dp[goal_a][goal_c]=Math.min(dp[goal_a][goal_c],dp[i][j]+p[4]);
}
else if(i+p[2]>goal_a){
dp[goal_a][j+p[3]]=Math.min(dp[goal_a][j+p[3]],dp[i][j]+p[4]);
}
else if(j+p[3]>goal_c){
dp[i+p[2]][goal_c]=Math.min(dp[i+p[2]][goal_c],dp[i][j]+p[4]);
}
else if(i+p[2]<=goal_a&&j+p[3]<=goal_c){
dp[i+p[2]][j+p[3]]=Math.min(dp[i+p[2]][j+p[3]],dp[i][j]+p[4]);
}
}
}
}
}
return dp[goal_a][goal_c];
}
}
|
cs |
'알고리즘 > 프로그래머스 Level3' 카테고리의 다른 글
| [프로그래머스,자바] Level3: 모두 0으로 만들기 (0) | 2022.08.28 |
|---|---|
| [프로그래머스 ,Java] Level3: 기지국 설치 (0) | 2022.08.25 |
| [프로그래머스 , Java] Level3: 합승 택시 요금 (0) | 2022.08.15 |
| [프로그래머스, Java] Level3: 숫자게임 (0) | 2022.08.15 |
| [프로그래머스,Java] Level3: 보석 쇼핑 (0) | 2022.08.13 |