프로그래머 스 코딩 테스트 공부 - peulogeulaemeo seu koding teseuteu gongbu

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

당신은 코딩 테스트를 준비하기 위해 공부하려고 합니다. 코딩 테스트 문제를 풀기 위해서는 알고리즘에 대한 지식과 코드를 구현하는 능력이 필요합니다.

알고리즘에 대한 지식은 알고력, 코드를 구현하는 능력은 코딩력이라고 표현합니다. 알고력과 코딩력은 0 이상의 정수로 표현됩니다.

문제를 풀기 위해서는 문제가 요구하는 일정 이상의 알고력과 코딩력이 필요합니다.

예를 들어, 당신의 현재 알고력이 15, 코딩력이 10이라고 가정해보겠습니다.

• A라는 문제가 알고력 10, 코딩력 10을 요구한다면 A 문제를 풀 수 있습니다.
• B라는 문제가 알고력 10, 코딩력 20을 요구한다면 코딩력이 부족하기 때문에 B 문제를 풀 수 없습니다.

풀 수 없는 문제를 해결하기 위해서는 알고력과 코딩력을 높여야 합니다. 알고력과 코딩력을 높이기 위한 다음과 같은 방법들이 있습니다.

• 알고력을 높이기 위해 알고리즘 공부를 합니다. 알고력 1을 높이기 위해서 1의 시간이 필요합니다.
• 코딩력을 높이기 위해 코딩 공부를 합니다. 코딩력 1을 높이기 위해서 1의 시간이 필요합니다.
• 현재 풀 수 있는 문제 중 하나를 풀어 알고력과 코딩력을 높입니다. 각 문제마다 문제를 풀면 올라가는 알고력과 코딩력이 정해져 있습니다.
• 문제를 하나 푸는 데는 문제가 요구하는 시간이 필요하며 같은 문제를 여러 번 푸는 것이 가능합니다.

당신은 주어진 모든 문제들을 풀 수 있는 알고력과 코딩력을 얻는 최단시간을 구하려 합니다.

초기의 알고력과 코딩력을 담은 정수 alp와 cop, 문제의 정보를 담은 2차원 정수 배열 problems가 매개변수로 주어졌을 때, 모든 문제들을 풀 수 있는 알고력과 코딩력을 얻는 최단시간을 return 하도록 solution 함수를 작성해주세요.

모든 문제들을 1번 이상씩 풀 필요는 없습니다. 입출력 예 설명을 참고해주세요.

제한사항

• 초기의 알고력을 나타내는 alp와 초기의 코딩력을 나타내는 cop가 입력으로 주어집니다.
  • 0 ≤ alp,cop ≤ 150
• 1 ≤ problems의 길이 ≤ 100
• problems의 원소는 [alp_req, cop_req, alp_rwd, cop_rwd, cost]의 형태로 이루어져 있습니다.
• alp_req는 문제를 푸는데 필요한 알고력입니다.
  • 0 ≤ alp_req ≤ 150
• cop_req는 문제를 푸는데 필요한 코딩력입니다.
  • 0 ≤ cop_req ≤ 150
• alp_rwd는 문제를 풀었을 때 증가하는 알고력입니다.
  • 0 ≤ alp_rwd ≤ 30
• cop_rwd는 문제를 풀었을 때 증가하는 코딩력입니다.
  • 0 ≤ cop_rwd ≤ 30
• cost는 문제를 푸는데 드는 시간입니다.
  • 1 ≤ cost ≤ 100

정확성 테스트 케이스 제한사항

• 0 ≤ alp,cop ≤ 20
• 1 ≤ problems의 길이 ≤ 6
  • 0 ≤ alp_req,cop_req ≤ 20
  • 0 ≤ alp_rwd,cop_rwd ≤ 5
  • 1 ≤ cost ≤ 10

효율성 테스트 케이스 제한사항

• 주어진 조건 외 추가 제한사항 없습니다.

입출력 예

입출력 예 설명

입출력 예 #1

1. 코딩력 5를 늘립니다. 알고력 10, 코딩력 15가 되며 시간이 5만큼 소요됩니다.
2. 1번 문제를 5번 풉니다. 알고력 20, 코딩력 20이 되며 시간이 10만큼 소요됩니다. 15의 시간을 소요하여 모든 문제를 풀 수 있는 알고력과 코딩력을 가질 수 있습니다.

입출력 예 #2

1. 1번 문제를 2번 풉니다. 알고력 4, 코딩력 2가 되며 시간이 4만큼 소요됩니다.
2. 코딩력 3을 늘립니다. 알고력 4, 코딩력 5가 되며 시간이 3만큼 소요됩니다.
3. 2번 문제를 2번 풉니다. 알고력 10, 코딩력 7이 되며 시간이 4만큼 소요됩니다.
4. 4번 문제를 1번 풉니다. 알고력 10, 코딩력 11이 되며 시간이 2만큼 소요됩니다. 13의 시간을 소요하여 모든 문제를 풀 수 있는 알고력과 코딩력을 가질 수 있습니다.

제한시간 안내

• 정확성 테스트 : 10초
• 효율성 테스트 : 언어별로 작성된 정답 코드의 실행 시간의 적정 배수

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 오류) 

즉, 초기 알고력> 목표알고력이면,   초기알고력 =알고력으로 교정작업을 해주자.

전체 문제풀이: