패스트캠퍼스 핵심유형 20개로 한 번에 끝내는 알고리즘 코딩테스트 with Java 강의 4주차

 

이번주도 Part5 단기완성 알고리즘을 들었다.

저번주에는 결과값을 찾기 위해 전체를 탐색하는 완전 탐색, 그 중에서도 백트래킹에 대해 배웠다.

이번주는 정렬과 이분탐색에 대한 강의를 듣고 정리해보기로 한다.

 

---

1. 정렬

* 정의

정렬이란, 어떤 자료들이 주어졌을 때 그 자료들에 대해서 오름차순, 내림차순 등의 기준이 주어졌을 때 이에 맞춰 졍렬하는 알고리즘.

 

* 정렬의 조건

1. 정렬 조건이 필요하다. (어떤 자료가 더 앞에 와야하는가?)

2. N개의 원소를 정렬하는 것의 시간 복잡도는 약 O(NlogN)이다. 

3. In-place / Stable 여부를 알아야 한다.

-> 정렬 알고리즘이 In-place(제자리) 한가?

: 정렬하는 과정에서 N에 비해 충분히 무시할 만한 개수의 메모리만큼만 추가적으로 사용하는가?

-> 정렬 알고리즘이 Stable(안정) 한가?

: 동등한 위상의 원소들의 순서 관계가 보존되는가? 즉, 비교할 수 없는 원소들은 입력에서 들어온 순서와 동일하게 출력에서 유지되는가?

 

* 정렬의 특성

1. 같은 정보들은 인접해 있을 것이다.

2. 각 원소마다, 가장 가까운 원소는 자신의 양 옆 중에 있다.

 

* 기본 형식

: Comparator 인터페이스의 comapre 메서드를 override 한다.

static class Elem implements Comparable<Elem> {

	public int num, idx;
    
    // return 음수 : 내가 먼저
    // return 양수 : 쟤(Other)가 먼저
    // return 0 : 우리는 친구
    @Override
    public int compareTo(Elem other){
    	return num - other.num; // num 값을 기준으로 오름차순 
    }
}

 

 

⭐️ 문제 풀기

 

1. [BOJ 10825] https://www.acmicpc.net/problem/10825

10825번: 국영수

* 시간, 공간 복잡도 계산하기 : 정렬만 하면 되니까 O(nlogn) = 100000 * log100000 = 1,600,600 => 1초 안에 가능

* 코드

package 정렬;

import java.util.Arrays;
import java.util.Scanner;

public class BOJ10825 {
    static StringBuilder sb = new StringBuilder();

    static class Elem implements Comparable<Elem> {

        public String name;
        public int korean, english, math;

        @Override
        public int compareTo(Elem other) {
            // 국어 점수 내림차순
            if (korean != other.korean) return other.korean - korean;
            // 영어 점수 오름차순
            if (english != other.english) return english - other.english;
            // 수학 점수 내림차순
            if (math != other.math) return other.math - math;
            return name.compareTo(other.name);
        }
    }

    static int N;
    static Elem[] a;

    static void input() {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        a = new Elem[N];
        for (int i = 0; i < N; i++) {
            a[i] = new Elem();
            a[i].name = sc.next();
            a[i].korean = sc.nextInt();
            a[i].english = sc.nextInt();
            a[i].math = sc.nextInt();
        }
    }

    static void pro() {
        Arrays.sort(a);
        for (int i = 0; i < N; i++) {
            sb.append(a[i].name).append('\n');
        }
        System.out.println(sb.toString());
    }

    public static void main(String[] args) {
        input();
        pro();
    }

}

 

 

 

---

 

2. 이분 탐색 (Binary Search)

* 정의

우선 (수열에서의) 탐색이란, 수열과 탐색 대상 X가 주어졌을 때

- X가 존재하는지?

- X[이하, 미만, 이상, 초과]의 원소는 몇 개가 있는지?

- X랑 가장 가까운 원소는 무엇인지?

를 찾는 것.

 

=> 이분 탐색은 정렬이 보장되는 배열에서 기준 X를 가지고 범위를 "이분" 하면서 탐색하는 방법.

 

* 오름차순 정렬이 된 배열의 특성

-> 임의의 M번 인덱스에 있는 A[M]이 X보다 크다면, A[M...N]은 전부 X보다 크다.

-> 임의의 M번 인덱스에 있는 A[M]이 X보다 작다면, A[1...M]은 전부 X보다 작다.

 

* 시간 복잡도  : O(logN)

 

* 용어

L = 탐색할 가치가 있는 범위의 왼쪽 끝 인덱스

R = 탐색할 가치가 있는 범위의 오른쪽 끝 인덱스

Result = 탐색한 x의 위치

M = (L+R)/2 

 

* 자주하는 실수

1) 입력된 배열에 바로 이분 탐색을 하는데, 정렬을 하지 않은 경우

2) L, R, M, Result 변수의 정의를 헷갈려서 부등호 등을 잘못 쓰는 경우

3) L, R 범위를 잘못 설정하거나 Result 초기값을 잘못 설정하는 경우

 

 

⭐️문제 풀기

1. [BOJ 7795] https://www.acmicpc.net/problem/7795

7795번: 먹을 것인가 먹힐 것인가

* 어떻게 풀까?

1) B 배열 정렬 한번 => O(MlogM)

2) 모든 A의 원소마다, B배열에 대해 이분 탐색 필요  => O(NlogM)

 

* 총 시간 복잡도 : O((N+M)logM)

 

* 코드

package 이분탐색;

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static StringBuilder sb = new StringBuilder();
    static Scanner sc = new Scanner(System.in);
    static int N, M;
    static int[] A, B;

    static void input() {
        N = sc.nextInt();
        M = sc.nextInt();
        A = new int[N + 1];
        B = new int[M + 1];
        for (int i = 1; i <= N; i++) {
            A[i] = sc.nextInt();
        }
        for (int i = 1; i <= M; i++) {
            B[i] = sc.nextInt();
        }
    }

    static int lower_bound(int[] A, int L, int R, int X) {
        // A[L...R] 에서 X 미만의 수 중 제일 오른쪽 인덱스를 return 하는 함수
        // 그런 게 없다면 L - 1 을 return 한다
        int res = L - 1;  // 만약 A[L...R] 중 X 이하의 수가 없다면 L - 1 을 return 한다.
        while (L <= R) {
            int mid = (L + R) / 2;
            if (A[mid] < X) {
                res = mid;
                L = mid + 1;
            } else {
                R = mid - 1;
            }
        }
        return res;
    }

    static void pro() {
        // 이분 탐색을 쓸 것이므로 B 배열에 대해 정렬해주자
        Arrays.sort(B, 1, M + 1);

        int ans = 0;
        for (int i = 1; i <= N; i++) {
            // A[i] 를 선택했을 때, B 에서는 A[i]보다 작은 게 몇 개나 있는 지 count
            ans += lower_bound(B, 1, M, A[i]);
        }
        System.out.println(ans);
    }

    public static void main(String[] args) {
        int TT;
        TT = sc.nextInt();
        for (int tt = 1; tt <= TT; tt++) {
            input();
            pro();
        }
    }
}

 

 

 

 

* 패스트캠퍼스 강의 링크 :  https://fastcampus.co.kr/dev_online_codingtest

핵심유형 20개로 한 번에 끝내는 알고리즘 코딩테스트 with Java 초격차 패키지 Online. | 패스트캠퍼

 

 "본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다."