오늘 진행된 강의에서 학습한 내용은 무엇인가요?

1. 서론

정렬 알고리즘과 이분 탐색 알고리즘에 대한 개념, 구현, 응용 등을 다룹니다. 정렬 알고리즘은 데이터를 순서대로 재배열하는 데 사용되며, 이분 탐색 알고리즘은 정렬된 데이터에서 특정 값을 빠르게 찾는 데 사용됩니다.

2. 정렬

2.1 정렬의 개념 및 중요성

정렬은 데이터를 크기 순서대로 재배열하는 알고리즘입니다. 데이터가 정렬되어 있으면 검색, 비교, 분석 등 다양한 작업을 보다 효율적으로 수행할 수 있습니다. 정렬은 컴퓨터 과학에서 매우 중요한 개념이며, 다양한 분야에서 활용됩니다. 예를 들어, 운영체제, 데이터베이스, 웹 검색 엔진, 머신 러닝 등에서 정렬 알고리즘이 사용됩니다.

2.2 Collection 정렬 방법

Java에서는 다양한 방식으로 Collection을 정렬할 수 있습니다.

2.2.1 Arrays.sort(arr): 기본 배열 정렬

  • 기본적으로 int, double, String 등의 기본 데이터 형식을 사용하는 배열을 정렬하는 데 사용됩니다.
  • O(n log n)의 시간 복잡도를 가지며, 삽입 정렬, 퀵 정렬, 병합 정렬 등의 효율적인 알고리즘을 내부적으로 사용합니다.
  • 예시: int[] arr = {5, 2, 9, 1, 5, 6}; Arrays.sort(arr);

2.2.2 Collections.sort(list): List 정렬

  • List 인터페이스를 구현하는 모든 Collection (예: ArrayList, LinkedList, Vector 등)을 정렬하는 데 사용됩니다.
  • Arrays.sort(arr)와 동일한 방식으로 작동하며, O(n log n)의 시간 복잡도를 가지고 있습니다.
  • 예시: List<Integer> list = Arrays.asList(5, 2, 9, 1, 5, 6); Collections.sort(list);

2.2.3 list.stream().sorted().toList(): Stream 활용 정렬

  • Java 8부터 도입된 Stream API를 이용하여 Collection을 정렬하는 방법입니다.
  • Stream API는 함수형 프로그래밍 방식을 제공하며, 다양한 중간 연산 (filtering, mapping 등)을 수행한 후 정렬할 수 있습니다.
  • 예시: List<Integer> list = Arrays.asList(5, 2, 9, 1, 5, 6); list.stream().sorted().toList();

2.3 추가 학습 자료

2.3.1 힙과 정렬을 언제 사용해야 하는지

힙과 정렬은 모두 데이터를 순서대로 처리하는 데 사용되는 알고리즘이지만, 서로 다른 특징과 활용 방식을 가지고 있습니다.

힙은 다음과 같은 경우에 사용하는 것이 좋습니다.

  • 데이터 삽입 및 삭제가 빈번하게 발생하는 경우: 힙은 데이터 삽입 및 삭제 연산을 O(log n)의 시간 복잡도로 수행할 수 있습니다. 반면, 정렬 알고리즘은 데이터 삽입 및 삭제 연산에 O(n)의 시간 복잡도가 걸릴 수 있습니다.
  • 우선순위 큐 구현: 힙은 데이터의 우선순위를 기반으로 데이터를 빠르게 처리하는 데 사용할 수 있습니다. 예를 들어, 네트워크 라우팅, 이벤트 처리 시스템 등에서 힙을 사용하여 우선순위가 높은 데이터를 먼저 처리할 수 있습니다.

정렬은 다음과 같은 경우에 사용하는 것이 좋습니다.

  • 데이터를 순서대로 처리해야 하는 경우: 정렬 알고리즘은 데이터를 순서대로 재배열하는 데 사용됩니다. 예를 들어, 검색 결과를 순서대로 표시하거나, 데이터를 분석하기 위해 데이터를 정렬해야 하는 경우 정렬 알고리즘을 사용할 수 있습니다.
  • 특정 값을 빠르게 찾아야 하는 경우: 이분 탐색과 같은 알고리즘을 사용하여 정렬된 데이터에서 특정 값을 빠르게 찾을 수 있습니다.

따라서 상황에 따라 힙과 정렬 중 적절한 알고리즘을 선택하는 것이 중요합니다.

2.3.2 삽입 정렬, 버블 정렬, 퀵 정렬, 병합 정렬 코드 예시 및 특징

삽입 정렬:

버블 정렬:

  • 코드 예시: https://www.geeksforgeeks.org/videos/bubble-sort-6gnt0b/
  • 특징:
    • O(n^2)의 시간 복잡도를 가지고 있어 데이터 양이 많을 때 비효율적입니다.
    • 반복적으로 인접한 두 요소를 비교하여 교환하며, 이미 정렬된 부분은 추가적으로 정렬하지 않아도 됩니다.

퀵 정렬:

  • 코드 예시: https://www.geeksforgeeks.org/quick-sort/
  • 특징:
    • O(n log n)의 평균 시간 복잡도를 가지고 있어 데이터 양이 많을 때 효율적입니다.
    • 피벗 요소를 기준으로 데이터를 두 그룹으로 나누고, 재귀적으로 그룹을 정렬합니다.

병합 정렬:

  • 코드 예시: https://www.geeksforgeeks.org/problems/merge-sort/1
  • 특징:
    • O(n log n)의 시간 복잡도를 가지고 있어 데이터 양이 많을 때 효율적입니다.
    • 데이터를 반으로 나누고, 재귀적으로 그룹을 정렬한 후 병합합니다.

3. 이분 탐색

3.1 이분 탐색의 개념 및 특징

이분 탐색은 정렬된 컬렉션에서 원하는 값을 빠르게 찾는 탐색 방법입니다. 배열의 중간 요소와 찾고자 하는 값을 비교하면서, 검색 범위를 절반으로 줄여가며 값을 찾는 방식이에요. 이분 탐색은 다음과 같은 특징을 가지고 있습니다.

  • 빠른 검색 속도: 시간 복잡도는 O(log n)으로, 매우 빠르게 값을 찾을 수 있어요.
  • 정렬된 배열에서 사용: 이분 탐색은 배열이 정렬되어 있어야 사용할 수 있어요.
  • 재귀적 접근: 재귀적으로 배열을 절반씩 나누면서 값을 찾는 방식이에요.

3.2 구현

3.2.1 Java 코드 예시

public static int binarySearch(int[] arr, int target) {
  int start = 0;
  int end = arr.length - 1;

  while (start <= end) {
    int mid = (start + end) / 2;
    if (arr[mid] == target)
      return mid;
    else if (arr[mid] < target)
      start = mid + 1;
    else
      end = mid - 1;
  }

  return -1;
}

위 코드는 정렬된 배열 arr에서 값 target을 찾는 이분 탐색 알고리즘을 나타냅니다. 코드는 다음과 같이 작동합니다.

  1. start를 0, end를 배열 길이 - 1로 설정합니다.
  2. start와 end 사이의 중간 위치 mid를 계산합니다.
  3. arr[mid]와 target을 비교합니다.
    • 만약 arr[mid] == target이면 mid를 반환합니다.
    • 만약 arr[mid] < target이면 start를 mid + 1로 설정합니다.
    • 만약 arr[mid] > target이면 end를 mid - 1로 설정합니다.
  4. start가 end보다 크거나 같아질 때까지 2~3 단계를 반복합니다.
  5. target을 찾지 못하면 -1을 반환합니다.

3.3 추가 학습 자료

3.3.1 이분 탐색의 특징

  • 이분 탐색은 정렬된 배열에서만 사용할 수 있습니다.
  • 이분 탐색은 O(log n)의 시간 복잡도를 가지고 있어 매우 빠른 속도로 값을 찾을 수 있습니다.
  • 이분 탐색은 재귀적 또는 반복적 방식으로 구현할 수 있습니다.

3.3.2 이분 탐색 코드 예시

  • 위에 제시된 Java 코드 예시는 이분 탐색 알고리즘의 기본적인 구현 방법입니다.
  • 다양한 프로그래밍 언어에서 이분 탐색 알고리즘을 구현하는 방법을 찾을 수 있습니다.
  • 이분 탐색 알고리즘은 다양한 응용 분야에서 사용됩니다.

4. 응용 알고리즘 문제

2가지 응용 알고리즘 문제를 다루었습니다. 각 문제는 다음과 같습니다.

4.1 백준 1920 수찾기

문제:

N개의 숫자로 이루어진 A 배열과 M개의 숫자로 이루어진 B 배열이 주어집니다. B 배열에 있는 각 숫자가 A 배열에 존재하는지 판별하고, 존재한다면 그 위치를 출력하는 것이 문제입니다.

해결 방식:

이 문제는 이분 탐색 알고리즘을 사용하여 해결할 수 있습니다.

  1. A 배열을 정렬합니다.
  2. B 배열의 각 숫자에 대해 이분 탐색을 수행하여 A 배열에서 그 숫자를 찾습니다.
    • 만약 찾으면 1을 출력하고, 못 찾으면 0을 출력합니다.

코드 예시 (Java):

public static void main(String[] args) {
  Scanner s = new Scanner(System.in);

  int n = s.nextInt();
  int[] arr = new int[n];
  for (int i = 0; i < n; i++) {
    arr[i] = s.nextInt();
  }
  Arrays.sort(arr); // 이분 탐색을 위해 정렬

  int m = s.nextInt();
  int[] arrM = new int[m];
  for (int i = 0; i < m; i++) {
    arrM[i] = s.nextInt();
    System.out.println(binarySearch(arr, arrM[i]));
  }
}

private static int binarySearch(
    int[] arr,
    int target
) {
  int start = 0;
  int end = arr.length - 1;

  while (start <= end) {
    int mid = (start + end) / 2;
    if (arr[mid] == target) {
      return 1;
    } else if (arr[mid] > target) {
      end = mid - 1;
    } else {
      start = mid + 1;
    }
  }

  return 0;
}

4.2 백준 1654 랜선 자르기

문제:

K개의 랜선이 있으며, 각 랜선의 길이는 다릅니다. 이 랜선들을 조각해서 N개의 같은 길이의 랜선을 만들려고 합니다. 랜선을 자르는 데는 비용이 발생하며, 랜선을 한 번 자를 때마다 1의 비용이 발생합니다. N개의 같은 길이의 랜선을 만들 수 있는 최소 비용을 찾는 것이 문제입니다.

해결 방식:

이 문제는 파라메트릭 서치 알고리즘을 사용하여 해결할 수 있습니다.

  1. 랜선의 길이를 오름차순으로 정렬합니다.
  2. 이진 탐색을 사용하여 최소 비용을 찾습니다.
    • start를 1, end를 최대 길이로 설정합니다.
    • mid를 start와 end의 중간 값으로 설정합니다.
    • mid 길이의 랜선을 N개 만들 수 있는지 확인합니다.
      • 만들 수 있다면 end를 mid로 설정합니다.
      • 못 만들 수 있다면 start를 mid + 1로 설정합니다.
    • start와 end가 같아질 때 end 값을 출력합니다.

4.2.2 백준 1654 랜선 자르기 Java 코드 예시

public static void main(String[] args) {
    Scanner s = new Scanner(System.in);

    int K = s.nextInt();
    int N = s.nextInt();
    long[] arr = new long[K];

    for (int i =0; i<K; i ++) {
      arr[i] = s.nextInt();
    }

    Arrays.sort(arr); // 랜선 길이 오름차순 정렬

    long max = Arrays.stream(arr).max().orElseThrow();

    long start = 1;
    long end = max;

    while (start <= end) {
      long mid = (start + end) /2;
      long sum = Arrays.stream(arr).map(e -> e / mid).sum();

      if (sum >= N) {
        start = mid + 1;
      } else {
        end = mid - 1;
      }
    }

    System.out.println(end);
  }

위 코드는 백준 1654 랜선 자르기 문제를 해결하는 Java 코드입니다. 코드는 다음과 같이 작동합니다.

  1. main() 함수에서 입력값 (K개의 랜선, N개의 만들 랜선)을 받습니다.
  2. arr 배열에 랜선의 길이를 저장합니다.
  3. Arrays.sort()` 함수를 사용하여 **arr 배열을 오름차순으로 정렬합니다.
  4. max 변수에 랜선의 최대 길이를 저장합니다.
  5. start 변수를 1, end 변수를 max로 설정합니다.
  6. while 루프를 사용하여 start와 end 사이의 mid 값을 찾습니다.
  7. Arrays.stream().map(e -> e / mid).sum(); 함수를 사용하여 mid 길이의 랜선을 N개 만들 수 있는지 확인합니다.
    • 만약 만들 수 있다면 start를 mid + 1로 설정합니다.
    • 못 만들 수 있다면 end를 mid - 1로 설정합니다.
  8. start와 end가 같아질 때 end 값을 출력합니다.

얻게된 인사이트는 무엇인가요?

정렬 알고리즘과 이분 탐색 알고리즘에 대한 이해를 높일 수 있었습니다. 또한, 다양한 응용 문제를 통해 이 알고리즘들이 실제 문제 해결에 어떻게 활용되는지 알 수 있었습니다.

1. 정렬 알고리즘의 중요성

정렬 알고리즘은 데이터를 순서대로 재배열하는 데 사용되는 기본적인 알고리즘입니다. 데이터를 정렬하면 검색, 비교, 분석 등 다양한 작업을 보다 효율적으로 수행할 수 있습니다. 실제로, 운영체제, 데이터베이스, 웹 검색 엔진, 머신 러닝 등 다양한 분야에서 정렬 알고리즘이 사용됩니다.

여기서는 삽입 정렬, 버블 정렬, 퀵 정렬, 병합 정렬 등 다양한 정렬 알고리즘을 다루었습니다. 각 알고리즘마다 장단점이 있으며, 상황에 따라 적절한 알고리즘을 선택하는 것이 중요합니다.

2. 이분 탐색 알고리즘의 빠른 검색 속도

이분 탐색 알고리즘은 정렬된 데이터에서 특정 값을 빠르게 찾는 데 사용되는 알고리즘입니다. 이 알고리즘은 O(log n)의 시간 복잡도를 가지고 있어, 데이터 양이 많아도 빠른 속도로 값을 찾을 수 있습니다.

백준 1920 수찾기 문제는 이분 탐색 알고리즘을 사용하여 해결할 수 있는 대표적인 문제입니다. 이 문제에서는 N개의 숫자로 이루어진 A 배열과 M개의 숫자로 이루어진 B 배열이 주어지고, B 배열에 있는 각 숫자가 A 배열에 존재하는지 판별해야 합니다. 이분 탐색 알고리즘을 사용하면 O(M log N)의 시간 복잡도로 문제를 해결할 수 있습니다.

3. 파라메트릭 서치 알고리즘의 활용

파라메트릭 서치 알고리즘은 최적의 값을 찾는 데 사용되는 알고리즘입니다. 이 알고리즘은 특정 조건을 만족하는 값의 범위를 점점 줄여나가며 최적의 값을 찾습니다.

백준 1654 랜선 자르기 문제는 파라메트릭 서치 알고리즘을 사용하여 해결할 수 있는 문제입니다. 이 문제에서는 K개의 랜선이 있으며, 각 랜선의 길이는 다릅니다. 이 랜선들을 조각해서 N개의 같은 길이의 랜선을 만들려고 합니다. 랜선을 자르는 데는 비용이 발생하며, 랜선을 한 번 자를 때마다 1의 비용이 발생합니다. N개의 같은 길이의 랜선을 만들 수 있는 최소 비용을 찾는 것이 문제입니다. 파라메트릭 서치 알고리즘을 사용하면 O(K log N)의 시간 복잡도로 문제를 해결할 수 있습니다.

4. 알고리즘 선택의 중요성

문제를 해결하기 위해서는 적절한 알고리즘을 선택하는 것이 중요합니다. 알고리즘마다 장단점이 있으며, 시간 복잡도, 데이터 양, 문제의 특성 등을 고려하여 적절한 알고리즘을 선택해야 합니다.

여기에서 다룬 정렬 알고리즘과 이분 탐색 알고리즘은 다양한 문제 해결에 활용될 수 있는 기본적인 알고리즘입니다. 앞으로 더 많은 알고리즘을 배우고, 다양한 문제에 적용해 나가면서 문제 해결 능력을 향상시키고 싶습니다.

저작자표시

'스케쥴 > 스터디' 카테고리의 다른 글

[항해99 취업리부트 TIL] 3주차 5일  (0) 2024.06.10
[항해99 취업리부트 TIL] 3주차 4일  (0) 2024.06.08
[항해99 취업리부트 TIL] 3주차 2일  (0) 2024.06.06
[항해99 취업리부트 TIL] 3주차 1일  (0) 2024.06.05
[항해99 취업리부트 TIL] 2주차 6일  (0) 2024.06.04

티스토리툴바