이 알고리즘 문제는 인프런의 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 (김태원)의 문제입니다.

문제 설명

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class sec06_09 {
    public static int count(int[] arr, int mid)
    {
        int count = 1;
        int sum = 0;
        for(int i = 0; i < arr.length; ++i)
        {
            if(sum + arr[i] > mid)
            {
                ++count;
                sum = arr[i];
            }
            else sum += arr[i];
        }
        return count;
    }

    public static int solution(int[] arr, int N, int M)
    {
        int lPtr = Arrays.stream(arr).max().getAsInt();  // 배열의 최대값
        int rPtr = Arrays.stream(arr).sum();  // 배열의 총합
        int answer = 0;

        while(lPtr <= rPtr)
        {
            int mid = (lPtr + rPtr) / 2;
            if(count(arr, mid) <= M)
            {
                answer = mid;  // 가능한 답을 저장하고, 더 작은 값으로 탐색
                rPtr = mid - 1;
            }
            else lPtr = mid + 1;  // 중간값이 작아서 구간 수가 M보다 많다면, 더 큰 값 탐색
        }
        return answer;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) arr[i] = Integer.parseInt(st.nextToken());
        System.out.println(solution(arr, N , M));
    }
}

설명

• count 메서드는 주어진 배열을 특정 값(mid)보다 큰 구간 합이 없도록 나누었을 때, 몇 개의 구간이 필요한지 계산하는 역할을 한다. 배열을 순차적으로 더해 가다가 구간 합이 mid를 넘으면 새로운 구간을 시작하고, 구간의 수를 하나 증가시킨다.
  
  
• solution 메서드는 이진 탐색을 사용하여 구간의 최대 합이 최소가 되도록 mid 값을 조정하는 역할을 한다. mid 값을 배열의 최대값과 총합 사이에서 탐색하며, count 메서드로 구간의 수를 계산해가면서 적절한 mid 값을 찾아낸다.

이 알고리즘 문제는 인프런의 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 (김태원)의 문제입니다.

문제 설명

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class sec06_08 {
    public static int solution(int[] arr, int M) {
        Arrays.sort(arr);
        return Arrays.binarySearch(arr, M) + 1;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        for (int i = 0; i < N; ++i) arr[i] = Integer.parseInt(st.nextToken());
        System.out.println(solution(arr, M));
    }
}

이진탐색 구현

public static int solution(int[] arr, int M) {
    Arrays.sort(arr);
    int lPtr = 0; int rPtr = arr.length - 1;
    while(lPtr <= rPtr)
    {
        int mid = (lPtr + rPtr) / 2;
        if(arr[mid] == M) return mid + 1;
        else
        {
            if(arr[mid] > M) rPtr = mid - 1;
            else lPtr = mid + 1;
        }
    }
    return -1;
}

설명

• 이진 탐색을 수행하기 위해서는 배열이 반드시 정렬되어 있어야 한다.
• 이진 탐색은 정렬된 배열에서 중앙값을 기준으로 탐색 범위를 줄여나가는 방식이기 때문에, 정렬되지 않은 배열에서는 제대로 작동하지 않는다.
• Arrays.binarySearch(arr, M)는 arr 배열에서 값 M을 찾는 이진 탐색 메서드이다. 반환 값은 M의 인덱스이다.
  만약 M을 찾지 못한다면 음수를 반환한다.

이 알고리즘 문제는 인프런의 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 (김태원)의 문제입니다.

문제 설명

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class sec06_07 {

    public static class Point{
        private int x;
        private int y;

        public Point(int x, int y)
        {
            this.x = x;
            this.y = y;
        }
    }

    public static ArrayList<Point> solution(ArrayList<Point> list) {
        Collections.sort(list, (a , b) ->{
            if (a.x == b.x) return a.y - b.y;
            else return a.x - b.x;
        });
        return list;
    }



    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        ArrayList<Point> list = new ArrayList<>();
        for(int i = 0; i < N; ++i)
        {
            StringTokenizer st = new StringTokenizer(br.readLine());
            Point newPoint = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            list.add(newPoint);
        }
        for (Point point : solution(list)) System.out.println(point.x + " " + point.y);
    }
}

설명

• 두 좌표 객체 a와 b의 x 값이 다를 경우, a.x - b.x를 반환하여 x 값이 작은 순서대로 정렬한다.
  즉, a.x < b.x이면 a가 b보다 앞에 오도록 한다.
• 만약 x 값이 같다면, y 값을 비교하여 y 값이 작은 순서대로 정렬한다.
  이는 a.y - b.y를 통해 이루어진다. 예를 들어, a.y < b.y이면 a가 b보다 앞에 오도록 한다.

이 알고리즘 문제는 인프런의 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 (김태원)의 문제입니다.

문제 설명

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class sec06_06 {
    public static ArrayList<Integer> solution(int[] arr)
    {
        int[] copy = arr.clone();
        ArrayList<Integer> answer = new ArrayList<>();

        Arrays.sort(copy);
        for (int i = 0; i < arr.length; ++i) if(arr[i] != copy[i]) answer.add(i + 1);
        return answer;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; ++i) arr[i] = Integer.parseInt(st.nextToken());
        for (int i : solution(arr)) System.out.print(i + " ");
    }
}

설명

• 얕은 복사 후 정렬을 수행하면 원본 배열은 정렬되지 않고 복사된 배열만 정렬된다.
• 원본 배열과 복사된 배열을 준비하고, 복사된 배열을 정렬한다.
• 각각의 인덱스를 돌면서 값이 다른 부분을 출력한다.

이 알고리즘 문제는 인프런의 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 (김태원)의 문제입니다.

문제 설명

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;

public class sec06_05 {
    public static char solution(int[] arr) {
        HashSet<Integer> set = new HashSet<>();
        for (int i : arr) set.add(i);
        return (arr.length == set.size()) ? 'U' : 'D';
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        for (int i = 0; i < arr.length; ++i) arr[i] = Integer.parseInt(st.nextToken());
        System.out.println(solution(arr));
    }
}

설명

• 배열 arr에 있는 모든 값을 HashSet에 추가한다.
• 만약 배열 arr의 길이와 HashSet의 크기가 같으면 중복이 없다는 뜻이므로 ‘U’를 반환한다.
• 배열의 길이와 HashSet의 크기가 다르면 중복이 있다는 뜻이므로 ‘D’를 반환한다.
• HashSet에 값을 추가하는 연산은 평균적으로 O(1)이므로 배열의 크기가 N일 때 전체 시간 복잡도는 O(N)이다. 이는 매우 효율적이다.

이 알고리즘 문제는 인프런의 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 (김태원)의 문제입니다.

문제 설명

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class sec06_04 {
    public static int[] solution(int S, int[] arr) {
        int[] cache = new int[S];
        for (int i : arr)
        {
            int pos = -1;
            for(int j = 0; j < cache.length; ++j) if(cache[j] == i) pos = j; //캐시 히트인지 미스인지 탐색
            if(pos == -1) //Cache Miss
            {
                for(int j = cache.length - 1; j > 0; --j) cache[j] = cache[j - 1]; //모든 작업을 한 칸씩 당긴다.
            }
            else //Chche Hit
            {
                for(int j = pos; j > 0; --j) cache[j] = cache[j - 1]; //pos 부터 맨 앞까지 작업을 한 칸씩 당긴다.
            }
            cache[0] = i; //새로운 작업을 맨 앞에 삽입
        }
        return cache;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int S = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < arr.length; ++i) arr[i] = Integer.parseInt(st.nextToken());
        for (int i : solution(S, arr)) System.out.print(i + " ");
    }
}

설명

• 캐시 히트/미스 확인
  -arr의 각 작업을 순서대로 탐색하여, 해당 작업이 캐시 내에 있는지(히트) 없는지(미스)를 확인한다.
  -이를 위해 캐시 배열을 탐색하고, 작업이 캐시에 있으면 그 인덱스를 pos에 저장한다. 만약 캐시에 없으면 pos는 -1이 된다.
• 캐시 미스 처리
  -만약 해당 작업이 캐시에 없으면(미스), 캐시 내 모든 항목을 한 칸씩 뒤로 밀어낸 후, 새로운 작업을 캐시의 맨 앞에 삽입한다.
• 캐시 히트 처리
  -작업이 이미 캐시에 있을 경우(히트), 그 작업을 캐시의 맨 앞으로 이동시키기 위해 해당 위치에서부터 앞으로 한 칸씩 당겨온다.

이 알고리즘 문제는 인프런의 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 (김태원)의 문제입니다.

문제 설명

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class sec06_03 {
    public static int[] solution(int[] arr) {
        for(int i = 1; i < arr.length; ++i)
        {
            int targetValue = arr[i];
            int j = i - 1;
            for(; j >= 0; --j)
            {
                if(arr[j] > targetValue) arr[j + 1] = arr[j];
                else break;
            }
            arr[j + 1] = targetValue;
        }
        return arr;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        for (int i = 0; i < N; ++i) arr[i] = Integer.parseInt(st.nextToken());
        for (int i : solution(arr)) System.out.print(i + " ");
    }
}

설명

2023.08.21 - [자료구조 & 알고리즘/알고리즘] - [알고리즘] 삽입 정렬과 빅 오(Big O)

이 알고리즘 문제는 인프런의 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 (김태원)의 문제입니다.

문제 설명

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class sec06_02 {
    public static int[] solution(int[] arr) {
        for(int i = 0; i < arr.length - 1; ++i)
        {
            for(int j = 0; j < arr.length - 1 - i; ++j)
            {
                if(arr[j] > arr[j + 1])
                {
                    int tmp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = tmp;
                }
            }
        }
        return arr;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        for (int i = 0; i < N; ++i) arr[i] = Integer.parseInt(st.nextToken());
        for (int i : solution(arr)) {
            System.out.print( i + " ");
        }
    }
}

설명

• 외부 루프 (i)
  -배열을 여러 번 순회하며 정렬을 반복한다.
  -첫 번째 순회가 끝나면 배열에서 가장 큰 값이 배열의 마지막으로 “버블”처럼 올라간다.
  -이 과정을 배열의 길이 arr.length - 1 만큼 반복하면서 정렬이 완료된다.
  
  
• 내부 루프 (j)
  -배열의 인접한 두 요소를 비교하는 역할을 한다.
  -배열의 j번째 요소와 j+1번째 요소를 비교하여 arr[j]가 arr[j+1]보다 크면 두 값을 교환한다.
  -각 반복(iteration)마다 가장 큰 요소가 배열의 마지막 부분으로 이동하기 때문에, 내부 루프의 범위는 arr.length - 1 - i로 점점 줄어든다. 즉, 이미 정렬된 부분은 다시 확인하지 않는다.
  
  
• 교환 작업
  -내부 루프에서 arr[j] > arr[j + 1] 조건이 성립하면 두 요소의 값을 서로 교환한다. 이를 통해 작은 값이 앞으로, 큰 값이 뒤로 이동하게 된다.