📕학습 개요

유니티 캠프 20일차.

날씨도 많이 풀리고, 연휴 기간이 다가오다 보니 마음이 해이해지고 집중력이 떨어지는 느낌이다.

📖학습 내용

문제 1: 지폐 접기 (Java)

문제 요약

  • 지갑 크기 (wallet)와 지폐 크기 (bill)가 주어질 때, 지폐를 규칙에 맞게 접어 지갑에 넣기 위한 최소 접기 횟수를 구하는 문제.

규칙 및 조건

  • 접기: 항상 지폐의 긴 쪽을 기준으로 반으로 접는다.
  • 홀수 처리: 접기 전 길이가 홀수였다면, 접은 후 소수점 이하는 버린다 (정수 나눗셈).
  • 종료 조건: 접힌 지폐를 그대로 또는 90도 돌려서 지갑에 넣을 수 있으면 멈춘다.
    • 이는 지폐의 긴 쪽이 지갑의 긴 쪽보다 작거나 같고 AND 지폐의 짧은 쪽이 지갑의 짧은 쪽보다 작거나 같으면 만족 (bill_large <= wallet_large && bill_small <= wallet_small).

접근 방식 및 개선

  • 초기 코드 분석: 가로/세로 중 더 긴 값과 짧은 값의 인덱스를 추적 (walletBigIndex, billSmallIndex 등)하여 구현. 로직은 정확했으나 인덱스 관리 부분이 다소 복잡하게 느껴질 수 있음.
  • 개선 아이디어: Math.max, Math.min을 사용하여 지갑과 지폐의 긴/짧은 길이를 값 자체로 직접 다루는 것이 가독성 측면에서 더 유리함.
  • 핵심 로직: while 루프를 사용하여 지폐가 지갑에 들어갈 수 있을 때까지 (max(bill) <= max(wallet) && min(bill) <= min(wallet)) 반복하며, 매번 현재 지폐의 긴 쪽 길이를 /= 2 연산으로 줄이고 접은 횟수를 증가시킴.
int walletLarge = Math.max(wallet[0], wallet[1]);
int walletSmall = Math.min(wallet[0], wallet[1]);
int currentBillW = bill[0];
int currentBillH = bill[1];
int foldCount = 0;

while (true) {
    int billLarge = Math.max(currentBillW, currentBillH);
    int billSmall = Math.min(currentBillW, currentBillH);

    if (billLarge <= walletLarge && billSmall <= walletSmall) {
        break;
    }
    foldCount++;
    if (currentBillW >= currentBillH) { // 같을 땐 아무 쪽이나 접어도 됨
        currentBillW /= 2;
    } else {
        currentBillH /= 2;
    }
}

문제 2: 돗자리 깔기(Java)

문제 요약

  • 장애물(‘X’ 또는 다른 문자)과 빈칸(‘-1’ 또는 ‘.’)으로 이루어진 공원 지도(park)와 여러 크기의 정사각형 돗자리(mats)가 주어질 때, 공원에 깔 수 있는 가장 큰 돗자리의 한 변 길이를 구하는 문제.

접근 방식: 동적 프로그래밍 (DP)

  • DP 최적화: dp[i][j]를 (i, j)를 오른쪽 아래 꼭짓점으로 하는 가장 큰 빈 정사각형의 한 변 길이로 정의.
  • DP 점화식:
    • park[i][j]가 장애물이면: dp[i][j] = 0
    • park[i][j]가 빈칸이면:
    • i == 0 또는 j == 0 (가장자리): dp[i][j] = 1
    • 그 외: dp[i][j] = Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1])) + 1
  • 최종 답 찾기:
    • DP 테이블을 채우면서 가능한 최대 빈 정사각형 크기 maxSize를 구한다.
    • mats 배열을 내림차순으로 정렬한다. (또는 오름차순 정렬 후 역순으로 순회)
    • 정렬된 mats를 순회하며 mat_size <= maxSize인 첫 번째 값 (가장 큰 값)을 찾아 반환한다.

  • 트러블슈팅:

    • 언어 혼용 실수: 초기 코드 작성 시 C#과 Java 문법 혼용 (e.g., Math.Min/min, foreach :/in, Array.Reverse/Reverst typo) -> Java 문법으로 통일 및 수정.
    • Java 특징: 문자열 비교는 .equals(), 배열 길이는 .length, Math.min은 두 인자만 받으므로 중첩 필요, 기본 타입 배열(int[]) 내림차순 정렬 시 Integer[] 변환 후 Collections.reverseOrder() 사용 또는 오름차순 정렬 후 역순 반복.
    • 로직 오류 디버깅:
    • 문제: mats를 오름차순 정렬 후, 앞에서부터 순회하며 조건을 만족하는 첫 번째 값에서 break하여 가장 작은 돗자리가 반환됨.
    • 해결: 오름차순 정렬 후 뒤에서부터 순회하거나, 내림차순 정렬 후 앞에서부터 순회하여 maxSize 이하인 가장 큰 돗자리 크기를 찾아야 함.
    public int solution(int[] mats, String[][] park) {
      int answer = -1;
      int maxSize = 0;
      int h = park.length;
      int w = park[0].length;
      int[][] dp = new int[h][w];

      for(int i = 0; i < h; i++){
          for(int j = 0; j < w; j++){
              String rect = park[i][j];

              if(!rect.equals("-1")){
                  dp[i][j] = 0;
              }
              else if(i == 0 || j == 0){
                  dp[i][j] = 1;
              }
              else{
                  dp[i][j] = Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1])) + 1;
              }
              if(dp[i][j] > maxSize) maxSize = dp[i][j];
          }
      }
      if(maxSize > 0){
           Arrays.sort(mats);


          for (int k = mats.length - 1; k >= 0; k--) {
              int mat_size = mats[k];
              if (mat_size <= maxSize) {
                  answer = mat_size;
                  break;
              }
          }
      }


      return answer;
  }

🏁오늘 배운 핵심 내용 정리

  • 알고리즘 선택: 문제의 제약 조건과 특성을 파악하여 적절한 알고리즘(단순 반복 vs DP)을 선택하는 것이 중요.
  • DP 패턴: ‘최대 정사각형 찾기’ DP 문제는 유사한 다른 문제에도 적용 가능한 유용한 패턴. 점화식을 정확히 세우는 연습 필요.
  • 배열 처리: 정렬 후 원하는 값을 찾기 위해 순회하는 방향(앞->뒤, 뒤->앞)이 로직의 정확성에 큰 영향을 미친다는 것을 디버깅을 통해 명확히 인지함.
  • 언어 정확성: 사용하는 프로그래밍 언어의 문법과 표준 라이브러리 함수 사용법을 정확히 아는 것이 중요 (e.g., Math.min 인자 개수, 정렬 방법).
  • 디버깅: 코드가 컴파일되더라도 논리적인 오류가 있을 수 있음. 예제 입력을 통해 단계별로 값을 추적하며 예상과 다른 부분을 찾아내는 것이 중요.

태그: ,

업데이트:

댓글남기기

참고