Dart 100제 41 ~ 45 (알고리즘)

41. 정렬 알고리즘 구현하기: 버블 정렬

버블 정렬(Bubble Sort)은 인접한 두 요소를 비교하고, 정렬이 완료될 때까지 반복하여 정렬하는 간단한 정렬 알고리즘입니다.

문제

버블 정렬 알고리즘을 구현하고 테스트하세요.

코드

// 버블 정렬 구현
List<int> bubbleSort(List<int> arr) {
  int n = arr.length;
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        // 스왑
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
}

void main() {
  List<int> data = [64, 34, 25, 12, 22, 11, 90];
  print('Original list: $data');
  List<int> sortedData = bubbleSort(data);
  print('Sorted list: $sortedData');
}

설명

버블 정렬 알고리즘은 리스트를 반복하면서 인접한 요소를 비교하여 정렬합니다. 이 과정은 리스트가 정렬될 때까지 계속됩니다. 위 코드에서 bubbleSort 함수는 리스트를 받아 정렬된 리스트를 반환합니다.

테스트 결과

Original list: [64, 34, 25, 12, 22, 11, 90]
Sorted list: [11, 12, 22, 25, 34, 64, 90]

42. 이진 검색 구현하기

이진 검색(Binary Search)은 정렬된 리스트에서 특정 값을 찾기 위해 사용하는 효율적인 검색 알고리즘입니다.

문제

정렬된 리스트에서 이진 검색을 구현하고 테스트하세요.

코드

// 이진 검색 구현
int binarySearch(List<int> arr, int target) {
  int left = 0;
  int right = arr.length - 1;
  
  while (left <= right) {
    int mid = left + (right - left) ~/ 2;
    
    if (arr[mid] == target) {
      return mid;
    }
    if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return -1; // 찾지 못한 경우
}

void main() {
  List<int> data = [11, 12, 22, 25, 34, 64, 90];
  int target = 25;
  int result = binarySearch(data, target);
  print('Index of $target: $result');
}

설명

이진 검색 알고리즘은 정렬된 리스트를 반으로 나누어 검색 범위를 줄여가며 효율적으로 값을 찾습니다. 위 코드에서 binarySearch 함수는 리스트와 검색할 값을 받아 인덱스를 반환합니다.

테스트 결과

Index of 25: 3

43. 정렬된 리스트 병합하기

두 개의 정렬된 리스트를 병합하여 정렬된 리스트를 만드는 문제입니다.

문제

두 개의 정렬된 리스트를 병합하여 정렬된 리스트를 만드세요.

코드

// 정렬된 리스트 병합하기
List<int> mergeSortedLists(List<int> list1, List<int> list2) {
  List<int> mergedList = [];
  int i = 0, j = 0;

  while (i < list1.length && j < list2.length) {
    if (list1[i] <= list2[j]) {
      mergedList.add(list1[i]);
      i++;
    } else {
      mergedList.add(list2[j]);
      j++;
    }
  }

  while (i < list1.length) {
    mergedList.add(list1[i]);
    i++;
  }

  while (j < list2.length) {
    mergedList.add(list2[j]);
    j++;
  }

  return mergedList;
}

void main() {
  List<int> list1 = [1, 3, 5, 7];
  List<int> list2 = [2, 4, 6, 8];
  List<int> mergedList = mergeSortedLists(list1, list2);
  print('Merged list: $mergedList');
}

설명

두 개의 정렬된 리스트를 병합할 때, 각 리스트의 요소를 비교하며 더 작은 요소를 결과 리스트에 추가합니다. 리스트의 끝까지 도달하면 남은 요소를 모두 추가합니다.

테스트 결과

Merged list: [1, 2, 3, 4, 5, 6, 7, 8]

44. 최대 공약수 계산하기

유클리드 알고리즘을 사용하여 두 숫자의 최대 공약수를 계산하는 문제입니다.

문제

유클리드 알고리즘을 사용하여 두 숫자의 최대 공약수를 계산하세요.

코드

// 유클리드 알고리즘으로 최대 공약수 계산
int gcd(int a, int b) {
  while (b != 0) {
    int temp = b;
    b = a % b;
    a = temp;
  }
  return a;
}

void main() {
  int num1 = 48;
  int num2 = 18;
  int result = gcd(num1, num2);
  print('GCD of $num1 and $num2: $result');
}

설명

유클리드 알고리즘은 두 숫자의 나머지를 반복적으로 계산하여 최대 공약수를 찾습니다. gcd 함수는 두 숫자를 받아 최대 공약수를 반환합니다.

테스트 결과

GCD of 48 and 18: 6

45. 소수 판별하기

주어진 숫자가 소수인지 판별하는 문제입니다.

문제

주어진 숫자가 소수인지 판별하세요.

코드

// 소수 판별하기
bool isPrime(int number) {
  if (number <= 1) return false;
  if (number <= 3) return true;
  
  if (number % 2 == 0 || number % 3 == 0) return false;
  
  for (int i = 5; i * i <= number; i += 6) {
    if (number % i == 0 || number % (i + 2) == 0) return false;
  }
  
  return true;
}

void main() {
  int number = 29;
  bool result = isPrime(number);
  print('$number is prime: $result');
}

설명

소수는 1과 자기 자신 외에는 아무로 나눠지지 않는 수입니다. isPrime 함수는 입력된 숫자가 소수인지 판별합니다. 효율적인 소수 판별을 위해 제곱근까지 나눠 보며 나머지가 0인지 확인합니다.

테스트 결과

29 is prime: true

 

이상으로 Dart를 이용한 여러 가지 알고리즘 문제 해결 방법을 소개했습니다.

각 문제에 대한 설명과 코드를 통해 문제를 해결하는 방법을 익힐 수 있기를 바랍니다.

질문이나 추가적인 도움이 필요하시면 언제든지 댓글로 남겨주세요!