[9주차_목요일] 코딩 테스트 공부

사이트 : 프로그래머스(PG)
문제: 코딩 테스트 공부
번호: 118668
레벨: Level 3
```
### 🤔 시간복잡도 고려사항
```

💡 풀이 아이디어

🤔 시간복잡도 고려사항

알고리즘: dp
시간복잡도: 0 ≤ alp, cop, alp_req, cop_req ≤ 150 1 ≤ problems의 길이 ≤ 100 DP 로 풀이 시 O(150*150*100) > 10^6

💡 풀이 아이디어

주어진 모든 문제들을 풀 수 있는 알고력과 코딩력을 얻는 최단시간 == 문제 중 최대 알고력과 코딩력 만큼 있으면 모든 문제를 다 풀 수 있음
dp[알고력][코딩력] = 최소시간
- 특정 알고력과 코딩력일 때 최소시간 구하기
- dp[최대 알고력][최대 코딩력] = 최소시간 이 정답이 됨
알고력 또는 코딩력을 높이는 3가지 방법
- 공부하기 (2)
  1. 알고력 1을 높이기 위해서 1의 시간이 필요
  2. 코딩력 1을 높이기 위해서 1의 시간이 필요
- ⭐문제풀기 (1)
  1. 알고력을 높일 것 인지? 문제를 풀었을 때 이미 최대 코딩력을 충족했다면 더 이상 높일 필요 없으므로 알고력을 높이기
```
dp[solvedAlp][maxCop] = Math.min(dp[solvedAlp][maxCop], dp[i][j]+problem.cost);
```
  2. 코딩력을 높일 것 인지? 문제를 풀었을 때 이미 최대 알고력을 충족했다면 더 이상 높일 필요 없으므로 코딩력을 높이기
```
dp[maxAlp][solvedCop] = Math.min(dp[maxAlp][solvedCop], dp[i][j]+problem.cost);
```
  3. 둘 다 높일 것 인지? 문제를 풀었을 때 얻는 알고력과 코딩력 높이기
```
dp[solvedAlp][solvedCop] = Math.min(dp[solvedAlp][solvedCop], dp[i][j]+problem.cost);
```
  4. 둘 다 높이지 않아도 되는지? 이미 최대 알고력과 코딩력을 충족했으므로 최대 알고력과 코딩력에 대한 최소 시간 유지 또는 갱신
```
dp[maxAlp][maxCop] = Math.min(dp[maxAlp][maxCop], dp[i][j]+problem.cost);
```
문제 풀기의 모든 경우에 대해 기존 최소시간 유지 vs 현재 푼 문제의 최소 시간을 비교해서 구한다
특이사항
- 현재 알고력과 코딩력을 시작으로 최대 알고력과 코딩력 까지만 점화식을 구한다
- 따라서 현재 알고력과 코딩력이 최대 알고력과 코딩력 보다 높을 경우 최대 알고력과 코딩력으로 값을 보정해준다
- 현재 알고력과 코딩력 상태에서 공부를 하면 알고력과 코딩력 둘 다 올라갈 수 있다
- 현재 알고력과 코딩력 상태에서 풀 수 있는 여러 문제가 있을 수 있다. 또는 풀 수 없는 문제가 있을 수 있다

에어컨 하위버전으로 어려웠어요.. dp[알고력][코딩력] = 최소시간 까진 접근했는데, 이후에 문제를 풀었을 때 알고력,코딩력 에 따라 최소시간이 달라지는데 어떻게 점화실을 세워야할지 모르겠어서 해설 참고했어요😫 결국엔 최대 알고력, 코딩력에 대한 최소시간을 구하는 문제이기 때문에 이걸 기준으로 비교해서 최소시간을 유지할지 갱신할지 를 생각해야 했습니다

🤔 시간복잡도 고려사항

0 ≤ alp,cop ≤ 150
1 ≤ problems의 길이 ≤ 100
DP이용시,max_alp * max_cop * problems의 길이 → 150 150 100 =2,250,000

💡 풀이 아이디어

2차원 DP이용
- DP[i][j] = k: i알고력과 j코딩까지 가는 최소 시간
  
  처음에 dp[i][j] = k: i번째로 j번째 문제를 풀었을때 최소 시간의 형태로 잘못 점화식을 생각했었습니다..
가능한 경우의 수 1) 한시간 공부해서 1알고력 or 1코딩력 기르기 2) 특정 문제를 풀고, 해당 문제를 통해 향상할 수 있는 만큼 알고력+코딩력 기르기
주의 사항
- 최대 알고력과 코딩력의 제한
  - 모든 문제를 풀기 위한, 최대 알고력과 코딩력 이상이 되는 최소 시간을 찾는 것이므로 최대 알고,코딩력 이상 값을 처리해줘야함.
  - int nxA = Math.min(i + pb[2], mxA);
  - 경우의 수 2번에서, 실력향상된 값이 최대값을 벗어날때 continue 처리가 아닌 최대값으로 맞춰주기
  - mxA = Math.max(mxA, p[0]);
  - 초기 알고, 코딩력 또한 최대값을 넘지 않도록 처리해주기
- 시작은 0이 아닌, 초기 알고, 코딩력부터 시작

dfs를 이용한 완전탐색을 생각했다가 dp생각했다가 한,, DP공부 연습을 더더 해야겠네요 DP 공부하기에 좋은 문제인 것 같습니당

🤔 시간복잡도 고려사항

시간 복잡도 : O(목표 알고력 * 코딩 알고력 * 문제 길이) < 1억

💡 풀이 아이디어

모든 문제를 풀 수 있는 최소 시간 반환(최적의 해)
완전 탐색으로 풀기엔 능력치 증가 조건 경로 다양, 중복된 상태 계산 많음 -> DP
- int[][] dp = new int[tA + 1][tC + 1]; // dp[알고력][코딩력]
- 초기값 : dp[alp][cop] = 0 // 시작 지점 시간 0으로 설정
능력치 증가 조건

알고력+1

if (i + 1 <= tA) { // 알고력 +1 경우
 dp[i + 1][j] = Math.min(dp[i + 1][j], dp[i][j] + 1);
}

코딩력 +1

if (j + 1 <= tC) { // 코딩력 +1 경우
 dp[i][j + 1] = Math.min(dp[i][j + 1], dp[i][j] + 1);
}

문제를 풀어서 능력치 올리기

// 문제를 풀어서 능력치 올리기
for (int[] problem : problems) {
  int alp_req = problem[0]; // 변수 할당
  int cop_req = problem[1];
  int alp_rw = problem[2];
  int cop_rw = problem[3];
  int cost = problem[4];

   if (i >= alp_req && j >= cop_req) {
     int nA = Math.min(tA, i + alp_rw);
     int nC = Math.min(tC, j + cop_rw);
    dp[nA][nC] = Math.min(dp[nA][nC], dp[i][j] + cost);
  }
}

dp[tA][tC] 반환 후 종료

처음에 완전 탐색으로 접근 했었다가 고려할 경우가 많아서 다른 방법이 있는지 찾아보니까 DP로 풀 수 있었네요! DP는 처음에 떠올리기가 어려운 것 같습니다

🤔 시간복잡도 고려사항

0 ≤ alp,cop ≤ 20
1 ≤ problems의 길이 ≤ 6
DP를 이용한 탐색
완전 탐색도 가능하지만 효율성 검사에서 틀림

💡 풀이 아이디어

특정 능력치를 달성하기 위한 최소 시간 → DP

현재 값 기준으로 다음 값 결정하기

알고력 증가

// 알고력 증가
if (i < maxAlp)
  dp[i + 1][j] = Math.min(dp[i + 1][j], dp[i][j] + 1);

코딩력 증가

// 알고력 증가
if (j < maxCop)
  dp[i][j + 1] = Math.min(dp[i][j + 1], dp[i][j] + 1);

문제 풀어서 능력치 증가

// 문제 풀기
for (int[] problem : problems)
  // 풀 수 있는 문제라면
  if (i >= problem[0] && j >= problem[1]) {
      // 능력치 증가
      int nextAlp = Math.min(maxAlp, i + problem[2]);
      int nextCop = Math.min(maxCop, j + problem[3]);
      dp[nextAlp][nextCop] = Math.min(dp[nextAlp][nextCop], dp[i][j] + problem[4]);
  }

이번 문제도 현재 값을 결정하는 게 아니라 다음 값을 결정해야하는 문제였습니다

🤔 시간복잡도 고려사항

2차원 DP를 통한 문제 풀이
dp[r][c]: 알고력이 r이고, 코딩력이 c가 되기 위해 걸리는 최소 시간을 구함
- 150(alp_req) * 150(cop_req) * 6(problems)

💡 풀이 아이디어

int maxAlpReq, maxCopReq: problem 중에서 필요한 알고력, 코딩력 중 가장 큰 값
int[][] dp = new int[maxAlpReq + 1][maxCopReq + 1]
- 알고력과 코딩력이 problems 있는 최대 alp_req, cop_req가 되면 모든 문제를 풀 수 있기 때문에 크기를 [maxAlpReq + 1][maxCopReq + 1]로 설정함
alp와 cop가 dp 범위를 벗어날 수 있기 때문에 값을 재조정해 줌
dp배열 값 채우기
- r과 c에 대해 순차적으로 탐색하면서 값을 채움
- 각 지점에 대해 알고리즘을 통해 공부해서 알고력을 1 높이는 경우, 코딩 공부를 해서 코딩력을 1 높이는 경우, 풀 수 있는 문제를 풀어 알고력과 코딩력을 높이는 경우를 고려함
```
// 알고리즘을 공부해서 알고력을 1 높이는 경우
if(r + 1 < dp.length) dp[r + 1][c] = Math.min(dp[r + 1][c], dp[r][c] + 1);
```
// 코딩 공부를 해서 코딩력을 1 높이는 경우 if(c + 1 < dp[0].length) dp[r][c + 1] = Math.min(dp[r][c + 1], dp[r][c] + 1);

// 풀 수 있는 문제를 하나 풀어 알고력과 코딩력을 높이는 경우 for(int k = 0; k < problems.length; k++) { int alpReq = problems[k][0]; // 문제를 풀기 위해 필요한 알고력 int copReq = problems[k][1]; // 문제를 풀기 위해 필요한 코딩력 int alpRwd = problems[k][2]; // 문제를 풀었을 때 증가하는 알고력 int copRwd = problems[k][3]; // 문제를 풀었을 때 증가하는 코딩력 int cost = problems[k][4]; //문제를 푸는데 드는 시간

if(r < alpReq || c < copReq) continue; // 현재 알고력이나 코딩력이 부족한 경우

// 범위를 벗어나는 경우 continue를 하면 오답! // 범위를 벗어나면 무조건 문제를 풀 수 있는 것이기 때문에 maxAlpReq, maxCopReq가 된 것이라고 생각해야 됨 // if(dp.length < r + alpRwd || maxCopReq < c + copRwd) continue; // 범위를 벗어가는 경우 // dp[r + alpRwd][c + copRwd] = Math.min(dp[r + alpRwd][c + copRwd], dp[r][c] + cost); int nextAlp = Math.min(maxAlpReq, r + alpRwd); int nextCop = Math.min(maxCopReq, c + copRwd);

dp[nextAlp][nextCop] = Math.min(dp[nextAlp][nextCop], dp[r][c] + cost); }

다익스트라로도 풀린다고 하는데,,,, 잘 모르겠네요!! 리뷰 끝나고 한 번 다익스트라로 다시 풀어보겠습니당

GreatAlgorithm-Study / AlgorithmStudy

[9주차_목요일] 코딩 테스트 공부 #115

💡 풀이 아이디어

🤔 시간복잡도 고려사항

💡 풀이 아이디어

🤔 시간복잡도 고려사항

💡 풀이 아이디어

🤔 시간복잡도 고려사항

💡 풀이 아이디어

🤔 시간복잡도 고려사항

💡 풀이 아이디어

🤔 시간복잡도 고려사항

💡 풀이 아이디어