모임사진

14:00~15:30 백준 과제 문제 코드, 알고리즘 리뷰

• 11501 주식

  • 앞에서부터
    • 시간초과가 뜸
    • 자료구조를 엄청 많이 쓰면 가능하지만, 다른방법이 너무 쉬워서 굳이
  • 뒤에서부터
    • 아주쉬움

• 2805 나무자르기

  • 이분탐색
    • 파이썬쓰면 시간초과가 난다.

• 14891 톱니바퀴

  • 삼성기출문제
  • 쉬운 구현

• 4179 불!

  • 불이 번진곳을 visit으로 처리 하면 됨.
  • 불이번진것과 지훈이가 이동하는것을 따로 bfs하면 된다.

• 2616 소형기관차

  • 소형기관차가 1대, 2대, 3대 있을 때 각각 최대로 운송할 수 있는 승객 수를 저장해나가며 dp테이블을 채우면 된다.

  

  

  

  

• 지난 주 카카오 문제 풀이 (https://school.programmers.co.kr/learn/challenges?order=recent&partIds=37527 - 미로 탈출 명령어)

  • 민제
  • 현진

15:00~17:00 코딩테스트 기출문제 풀이

• 1주차 오프라인 코딩테스트 문제 (카카오)

• 풀이방법 (chatGPT 답안)

def solution(alp, cop, problems):
    max_alp = max(max(problem[0] for problem in problems), alp)
    max_cop = max(max(problem[1] for problem in problems), cop)
    
    # DP 배열 초기화: 무한대로 설정하여 최소값 갱신이 용이하도록 함
    dp = [[float('inf')] * (max_cop + 1) for _ in range(max_alp + 1)]
    dp[alp][cop] = 0 # 초기 상태
    
    for cur_alp in range(alp, max_alp + 1):
        for cur_cop in range(cop, max_cop + 1):
            if cur_alp < max_alp:
                dp[cur_alp + 1][cur_cop] = min(dp[cur_alp + 1][cur_cop], dp[cur_alp][cur_cop] + 1)
            if cur_cop < max_cop:
                dp[cur_alp][cur_cop + 1] = min(dp[cur_alp][cur_cop + 1], dp[cur_alp][cur_cop] + 1)
                
            for alp_req, cop_req, alp_rwd, cop_rwd, cost in problems:
                if cur_alp >= alp_req and cur_cop >= cop_req:
                    next_alp = min(max_alp, cur_alp + alp_rwd)
                    next_cop = min(max_cop, cur_cop + cop_rwd)
                    dp[next_alp][next_cop] = min(dp[next_alp][next_cop], dp[cur_alp][cur_cop] + cost)
                    
    return dp[max_alp][max_cop]

# 예시
print(solution(10, 10, [[10,15,2,1,2],[20,20,3,3,4]]))
print(solution(0, 0, [[0,0,2,1,2],[4,5,3,1,2],[4,11,4,0,2],[10,4,0,4,2]]))

모두가 못 푼 첫 문제

다들 집에서 풀어보길

• 종빈

  import java.util.*;
  class Solution {
      public int solution(int alp, int cop, int[][] problems) {
          int alpMax = 0;
          int copMax = 0;
          for (int[] ints : problems) {
              alpMax = Math.max(ints[0], alpMax);
              copMax = Math.max(ints[1], copMax);
          }
          alpMax = Math.max(alpMax,alp);
          copMax = Math.max(copMax,cop);
          if(alp>=alpMax&&cop>=copMax) return 0;
          int[][] dp = new int[alpMax + 1][copMax +1];
          for (int i = 0; i < alpMax+1; i++) {
              Arrays.fill(dp[i], Integer.MAX_VALUE-10000);
          }
          dp[alp][cop] = 0;
          for (int i = alp; i <= alpMax; i++) {
              for (int j = cop; j <= copMax; j++) {
                  if (i < alpMax) {
                      dp[i + 1][j] = Math.min(dp[i + 1][j], dp[i][j] + 1);
                  }
                  if (j < copMax) {
                      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 next_alp = Math.min(alpMax, i + problem[2]);
                          int next_cop = Math.min(copMax, j + problem[3]);
                          dp[next_alp][next_cop] = Math.min(dp[next_alp][next_cop], dp[i][j] + problem[4]);
                      }
                  }
              }
  
          }
          return dp[alpMax][copMax];
      }
  }
  

각자 공부 사항 및 소감