Skip to content

2023.11.02 ‐ 2023.11.08

Jump to bottom
yumyeonghan edited this page Dec 29, 2023 · 4 revisions

유명한

랜선 자르기

🦊 문제 해결 과정

  1. 이진 탐색으로 풀며, 조건에 만족하는 랜선의 최댓값(mid) 구하는 문제
  2. 시작 값(start)을 가장 작은 수인 1, 끝 값(end)을 가장 긴 랜선 길이로 셋팅
  3. 시작 값이 끝 값을 넘기 전까지 반복
    1. mid 값 구하기
    2. 각 랜선을 순회하며, 만들 수 있는 랜선 개수를 구함
    3. 만약, 만들 수 있는 랜선 개수가 필요한 랜선 개수 이상이면, start = mid + 1
    4. 아니라면, end = mid - 1

🐥 코드 풀이 과정

   // 2번 과정
   for (int i = 0; i < k; i++) {
      arr[i] = Integer.parseInt(br.readLine());
      if (end < arr[i]) {
        end = arr[i];
      }
    }

   // 3번 과정
   while (!(end < start)) {
      long mid = (start + end) / 2;
      long sum = 0;
      for (int i = 0; i < k; i++) {
        sum += (arr[i] / mid);
      }
      if (sum >= n) {
        start = mid + 1;
        result = mid;
      } else {
        end = mid - 1;
      }
    }

경로 찾기

🦊 문제 해결 과정

  1. 플로이드 워샬 알고리즘 사용
  2. 출력 할 2차원 배열 초기화 result
  3. 입력 값은 항상 갈 수 있는 경로이므로 result 배열에 바로 1로 정답 처리
  4. 플로이드 워샬 알고리즘 사용
    1. 시작점(i)에서 중간지점(k)를 지나고, 중간지점(k)에서 도착지점(j)로 경로가 이어지면, result[i][j] 값 1로 정답 처리

🐥 코드 풀이 과정

   // 3번 과정
   // 입력 값은 항상 지나기 때문에 바로 정답 처리
   for (int i = 0; i < n; i++) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      for (int j = 0; j < n; j++) {
        result[i][j] = Integer.parseInt(st.nextToken());
      }
    }

   // 4번 과정
   // k를 지남
   for (int k = 0; k < n; k++) {
      // i에서 시작
      for (int i = 0; i < n; i++) {
        // j에 도작
        for (int j = 0; j < n; j++) {
          if (result[i][k] == 1 && result[k][j] == 1) {
            result[i][j] = 1; // i 에서 k 를 지나 j 로 갈 수 있으므로 정답 처리
          }
        }
      }
    }

정경원

유기농 배추

🦊 문제 해결 과정

  1. 주어진 배추밭의 세로 길이, 가로 길이, 배추가 심어진 위치 를 이용하여 배열 초기화
  2. 구역별 필요한 지렁이의 수를 구하기 위해 인접해 있는 배추들을 대상으로 dfs 수행
    1. 배추가 심어져 있는 위치 → 상,하,좌,우 dfs 실행
      1. 만약 배추가 심어져 있으면 1 → 0으로 치환 후 dfs 반복
      2. 더이상 심어져 있는 배추가 없으면 dfs 종료

🐥 코드 풀이 과정

  1. 코드 단락, 이유 1
    // 1번 해결 과정
    int n = sc.nextInt(); //배추밭 세로 길이
    int m = sc.nextInt(); //배추밭 가로 길이
    int k = sc.nextInt(); //배추가 심어져 있는 위치의 개수

    arr = new int[n][m];

    for (int j = 0; j < k; j++) {
        int x = sc.nextInt();
        int y = sc.nextInt();

        arr[x][y] = 1;
    }
  1. 코드 단락, 이유 2
        // 2번 해결 과정
        int eartWarm = 0; //구역별 필요한 지렁이의 수

        for (int s = 0; s < arr.length; s++) {
            for (int j = 0; j < arr[s].length; j++) {
                if (arr[s][j] == 1) {
                    eartWarm += 1;
                    dfs(s, j);
                }
            }
        }
		.
		.
		.

	static void dfs(int y, int x) {
        arr[y][x] = 0; // 배추가 심어져 있는 땅을 방문함을 표시 -> dfs 종료 조건

        //현재 좌표에서 이동할 수 있는 경우의 수(동, 서, 남, 북)
        int[][] xy = new int[][]{{x - 1, y}, {x + 1, y}, {x, y - 1}, {x, y + 1}};

        for (int[] ints : xy) {
            int distance_x = ints[0];
            int distance_y = ints[1];

            // 이어진 배추밭 부분까지 dfs 실행
            if (distance_x >= 0 && distance_x <= arr[0].length - 1 &&
                    distance_y >= 0 && distance_y <= arr.length - 1) {
                if (arr[distance_y][distance_x] == 1) {
                    dfs(distance_y, distance_x);
                }
            }
        }
    }

공유기 설치

🦊 문제 해결 과정

  1. 주어진 집의 개수, 공유기의 개수를 이용하여 배열 초기화
    1. 이분 탐색을 위한 배열 정렬
  2. 탐색 범위 start, mid ,end 설정
    1. 이때, 공유기의 최소 거리는 1이므로 start = 1
    2. end= 배열의 마지막 요소로 초기화
  3. 이분 탐색 수행
    1. count = 필요한 공유기의 개수 → 첫 집에 공유기 설치를 base으로 설정
    2. 필요한 공유기 개수(count)와 주어진 공유기의 개수(c)를 비교 반복
      1. count < c : 공유기 개수가 적음 → 범위를 줄임
      2. count ≥ c : 공유기 개수가 많음 → 범위를 늘림
    3. end(최대값)을 리턴

🐥 코드 풀이 과정

  1. 코드 단락, 이유 1
// 1번 해결 과정
int n = sc.nextInt(); //집의 개수
int c = sc.nextInt(); //공유기의 개수

int[] modem = new int[n];
for (int i = 0; i < n; i++) {
    modem[i] = sc.nextInt();
}
Arrays.sort(modem); //이분 탐색을 위한 정렬
  1. 코드 단락, 이유 2
//탐색 범위 시작은 1: 공유기의 최소 거리, 끝은 배열의 마지막 요소
long start = 1;
long mid = 0;
long end = modem[modem.length - 1];
  1. 코드 단락, 이유 3
//3번 해결 과정

int count; //필요한 공유기의 개수

while (start <= end) {
    mid = (start + end) / 2; //c에 대한 최대 목표 거리

		count = 1; //첫 집에 공유기 설치

    int tmp = modem[0];
    for (int i = 1; i < modem.length; i++) {
        if (modem[i] - tmp >= mid) {
            count += 1;
            tmp = modem[i];
        }
    }

    //필요한 공유기 개수와 주어진 공유기 개수 비교
    if (count >= c) {
        start = mid + 1;
    }
    else {
        end = mid - 1;
    }
}

숫자 변환하기

🦊 문제 해결 과정

  1. y+1 크기의 배열 설정 & 최댓값(상수)으로 초기화
    1. x번째 배열은 0으로 초기화 → x부터 다이내믹 프로그래밍을 시작하므로
  2. x+1부터 다이내믹 프로그래밍 실행 (bottom up)→ 조건문에 따른 연산 횟수 비교
    1. x에 n을 더하는 경우
    2. x에 2를 곱하는 경우
    3. x에 3을 곱하는 경우
  3. 마지막 y번째 배열의 값이 상수이면 -1으로 치환하여 리턴

🐥 코드 풀이 과정

  1. 코드 단락, 이유 1
// 1번 해결 과정
int[] dp = new int[y + 1]; //y+1 크기의 배열 설정
Arrays.fill(dp, INF);

dp[x] = 0;
  1. 코드 단락, 이유 2
for (int i = x + 1; i <= y; i++) {

    int a = INF; //x에 n을 더함
    int b = INF; //x에 2를 곱함
    int c = INF; //x에 3을 곱함

    if (i % 3 == 0) {
        c = dp[i / 3] + 1;
    }
    if (i % 2 == 0) {
        b = dp[i / 2] + 1;
    }
    if (i - n >= x) {
        a = dp[i - n] + 1;
    }
    int min = Math.min(a, Math.min(b, c));
    dp[i] = Math.min(INF, min);
}

return dp[y] == INF ? -1 : dp[y];
Clone this wiki locally