exe파일이므로 윈도우에서 실행하면
input를 묻고

IDA를 키면

input을 묻는 부분을 바로 찾을 수 있다.

메인함수를 디컴파일해보니 위와 같다.
추정컨대 sub_140011B0으로 인풋 메시지를 출력하고
sub_14001210으로 값을 받아서 저장하는 것으로 보인다.

우리가 알아야 하는것은 Correct가 뜨는 조건인데 그 조건과 관련된 함수는
sub_14001000으로 보인다.

그 함수도 디컴파일했는데 결과가 위와 같다. 인풋값을 ac배열과 비교하는 로직이다.
따라서 ac배열을 조사해볼 필요가 있다.

ac배열을 클릭해서 들어가보면
Comp4re_the_arr4y를 확인할 수 있다.

• 탐색 알고리즘이란
• 순차 탐색
• 이진 탐색

탐색 알고리즘

탐색 알고리즘이란 어떤 데이터셋에서 특정한 요소를 찾아내는 것이다. 여기서 말하는 데이터셋은 배열이나 리스트나, 트리나 무엇이든 될 수 있으나, 특정 알고리즘은 링크드 리스트나 이진 트리에만 사용할 수 있는 등 제약이 있을 수 있다.

순차 탐색(Linear Search)

처음부터 끝까지 모든 요소를 비교하여 원하는 데이터를 찾는 탐색 알고리즘이다. 어느 한 방향으로만 탐색할 수 있는 알고리즘이므로 선형 탐색(linear search)라고 하기도 한다.

절차는 매우 단순한데, 정리하자면
처음부터 시작해서->찾을 값과 해당 위치 값 비교->같으면 찾은 것, 아니면 이동해서 다시 찾기

예시를 들어 살펴보자.
30을 {10, 50, 30, 70, 80, 60, 20, 90, 40} 배열에서 찾을 것이다.

• 30은 10과 같지 않다. 넘어가서,

• 마찬가지로 50도 30과 같지 않다.

• arr[2]의 값은 30과 같다. 찾았다.

순차 탐색의 구현

간단한 알고리즘인만큼 구현도 매우 간단한 편이다.

#include <stdio.h>

int linearSearch(int arr[], int N, int x) {
  for (int i = 0; i < N; i++)
    if (arr[i] == x)
      return i;
  return -1;
}

int main(void) {
  int arr[] = {2, 3, 4, 10, 40};
  int x = 10;
  int N = sizeof(arr) / sizeof(arr[0]);

  int result = linearSearch(arr, N, x);
  (result == -1) ? printf("찾지못함\n") : printf("arr[%d]\n", result);
  return 0;
}

순차 탐색의 분석

시간 복잡도

• Best Case: 첫번째에서 바로 찾으면 $O(1)$
• Worst Case: $O(N)$
• Average: $O(N)$

장점

• 말그대로 그냥 하나하나 처음부터 비교하는 것이므로 데이터셋이 어떤 상태이든지 상관없다. 정렬이 되어있든, 되어있지 않든

단점

• 하나하나 처음부터 찾을 때까지 비교해가는 것이므로 비효율적이고, 데이터셋이 크면 쓰기 어렵다.

이진 탐색(Binary Search)

이진 탐색은 정렬된 배열에서 쓸 수 있는 탐색 알고리즘이다.

과정은 다음과 같다.

• 데이터셋을 가운데 인덱스를 기준으로 반으로 나눈다.
• 가운데 인덱스의 요소와 찾을 값(key)를 비교한다.
• 정확히 가운데에서 찾았다면 탐색을 종료하고, 그렇지 않다면
• 키가 앞쪽 반에 있다면 뒤쪽 반을 버리고 뒤쪽에 있다면 앞쪽 반을 버린다.
• 키의 후보 구역에서 위 과정을 반복해서 찾는다.

예를 들어,

위 그림과 같은 배열에서 23을 찾는다고 가정해보자.
위 배열의 가운데 인덱스는 arr[4], 16이다.

23은 16보다 크다. 따라서 뒤쪽(오른쪽) 반을 탐색하자.

다시, 뒤쪽 반의 가운데 요소는 56이다. 23은 이보다 작다. 그러면 이제 앞쪽 반을 탐색하자.

구역을 좁혀나가는 방식으로 23을 찾는 데에 성공했다.

이진 탐색의 구현

#include <stdio.h>

int binarySearch(int arr[], int low, int high, int x) {
  while (low <= high) {
    int mid = low + (high - low) / 2;
    //가운데 인덱스가 키일때
    if (arr[mid] == x)
      return mid;
    //일치하지 않는 경우 값을 비교하여 구역을 좁힘
    else if (arr[mid] < x)
      low = mid + 1;
    else
      high = mid - 1;
  }
  //배열 내에 없음.
  return -1;
}

int main(void) {
  int arr[] = {2, 3, 4, 5, 6, 7, 8, 9};
  int n = sizeof(arr) / sizeof(arr[0]);
  int x = 10;
  int result = binarySearch(arr, 0, n - 1, x);
  if (result == -1)
    printf("없음\n");
  else
    printf("arr[%d]\n", result);
}

이진 탐색 분석

시간복잡도:

• Best case: $O(1)$
• Average case: $O(logN)$
• Worst Case: $O(log N)$

장점

• 순차 탐색보다 빠르다.
• 따라서 더 큰 데이터셋에 사용하기 적합하다.

단점

• 배열이 정렬되어있어야한다.
• 찾으려는 값이 비교할 수 있는 값이어야한다. 순차 탐색에서는 일치 여부만 찾으면 되므로 크고 작음을 비교할 수 없어도 된다.

• 버블 정렬
• 선택 정렬
• 삽입 정렬

정렬 알고리즘

정렬(sorting)이란 기준에 따라 데이터를 순서대로, 체계적으로 정리하는 것이다. 정렬에도 여러 가지 방법들이 있는데 대표적으로 버블 정렬, 선택 정렬, 삽입 정렬이 있다.

버블 정렬(Bubble sort)

버블 정렬은 가장 간단한 정령 알고리즘 중 하나이다.
간단하게, 옆에 위치한 두 개끼리 비교하여 정렬하는 것을 반복하는 것이다.

예시를 들어

arr[] = {6,0, 3, 5}
이면

• 1. 가장 큰 element가 끝으로 위치하게 된다.

• 2. 두 번째 큰 element도 제 위치를 찾아가게 된다.

• 3. 세 번째 큰 element도 제 자리를 찾아가므로, element개수가 총 4개인 이 배열은 정렬이 완료되었다.

버블 정렬의 구현

#include <stdbool.h>
#include <stdio.h>

void swap(int *xp, int *yp) {
  int temp = *xp;
  *xp = *yp;
  *yp = temp;
}

// 버블 정렬
void bubbleSort(int arr[], int n) {
  bool swapped;
  for (int i = 0; i < n - 1; i++) {
    swapped = false;
    for (int j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(&arr[j], &arr[j + 1]);
        swapped = true;
      }
    }
    // 이 경우 처음부터 정렬되어있었음
    if (swapped == false)
      break;
  }
}

// 배열 출력
void printArray(int arr[], int size) {
  for (int i = 0; i < size; i++)
    printf("%d ", arr[i]);
}

int main(void) {
  int arr[] = {64, 34, 25, 12, 22, 11, 99};
  int n = sizeof(arr) / sizeof(arr[0]);
  bubbleSort(arr, n);
  printArray(arr, n);
  return 0;
}

위와 같이 구현할 수 있다.
실행 시 작은 값부터 출력된다.

버블 정렬 분석

이중반복문을 돌기 때문에 시간복잡도는 $$ O(N^2) $$

장점

• 가장 간단한 정렬 알고리즘 중 하나이다.
• 추가적인 메모리 공간이 필요없다.
• stable하다.

단점

• $O(N^2)$의 시간복잡도
• comparison operator가 요구됨.

stable

크기가 같은 값이 있을 때, 예를 들어 12가 두 개면 하나를 a1, 남은 하나를 a2라 하자.
정렬은 크기를 기준으로 하기 때문에 값이 같은 a1과 a2는 경우에 따라 서로 위치가 a2, a1처럼 바뀔 수도 있는데, 바뀌지 않는 경우를 stable하다고 한다.

선택 정렬(Selection Sort)

선택 정렬도 마찬가지로 간단하고 효과적인 정렬 알고리즘 중 하나이다. 선택 정렬은 계속해서 가장 작은 값 또는 가장 큰 값을 뽑아내서 끝의 위치로 옮겨준다.

마찬가지로 예시를 보면
arr = {64, 25, 12, 22, 11}

• 1. 최솟값을 탐색한다. 가장 작은 값은 11이다.

• 2. 11을 64의 자리로 옮긴다. 11은 정렬되었으니 건드리지 말고 다음 작은 값을 찾는데 이건 12이다.

• 3. 과정은 계속 같다...이번에는 22가 가장 작다. 22를 25와 교환해준다.

• 4. 25가 최솟값이고, 이미 4번째 자리에 있어서 교환해줄 필요는 없다.

• 5. 이미 위에서 3번 시점에서 이 배열은 정렬된 상태이지만, 이러한 과정을 통해 최종적으로 가장 큰 값이 자동적으로 맨 뒤에 오게되면서 정렬이 완료된다.

선택 정렬의 구현

#include <stdio.h>

void swap(int *xp, int *yp) {
  int temp = *xp;
  *xp = *yp;
  *yp = temp;
}

void selectionSort(int arr[], int n) {
  int min_idx;
  for (int i = 0; i < n - 1; i++) {
    min_idx = i;
    for (int j = i + 1; j < n; j++)
      if (arr[j] < arr[min_idx])
        min_idx = j;
    if (min_idx != i)
      swap(&arr[min_idx], &arr[i]);
  }
}

void printArray(int arr[], int size) {
  for (int i = 0; i < size; i++)
    printf("%d ", arr[i]);
  printf("\n");
}

int main(void) {
  int arr[] = {190, 90, 120, 1, 3, 2};
  int n = sizeof(arr) / sizeof(arr[0]);
  selectionSort(arr, n);
  printArray(arr, n);
  return 0;
}

선택 정렬 분석

시간복잡도는 이중반복문을 돌게 되므로
$$O(N^2)$$

장점

• 간단하다. 버블정렬과 마찬가지로..
• 작은 데이터셋에서 잘 작동한다.

단점

• 시간복잡도.
• 큰 데이터셋에서는 좋지 못하다.
• stable하지 않다.

삽입 정렬(Insertion Sort)

삽입 정령은 자료구조를 순차적으로 순회하면서 순서에 어긋나는 element를 찾고, 그 element를 올바른 위치에 다시 삽입해나가는 정렬 알고리즘이다.

1. 첫 번째 요소가 정렬이 되어있다고 가정하고 두 번째 요소부터 살펴본다.
2. 첫 번째 요소와 두 번째 요소를 비교한다. 비교 후 swap으로 정렬
3. 세 번째 요소와 두 번째 요소를 비교하고, 다음으로 첫 번째 요소와 비교한다. 그리고 세 번째 요소를 맞는 위치에 끼워넣는다.
4. 이런 식으로 완전히 정렬되기 전까지 반복한다.

사진의 예시를 살펴보고 위 절차대로 수행해보자.

23이 정렬되어있다고 가정하고 1과 23을 비교
-> 1을 23 앞에 끼워넣기
-> 10과 23 비교, 10과 1 비교. 1과 23 사이에 끼워넣음
-> 5도 마찬가지로 비교해서 끼워넣음.
-> 2도 순차적으로 비교해서 맞는 위치에 끼워넣음.
-> 정렬 완료

삽입 정렬의 구현

#include <stdio.h>

void insertionSort(int arr[], int n) {
  for (int i = 0; i < n; i++) {
    int key = arr[i];
    int j = i - 1;

    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
}

void printArray(int arr[], int n) {
  for (int i = 0; i < n; i++)
    printf("%d ", arr[i]);
  printf("\n");
}

int main(void) {
  int arr[] = {12, 11, 13, 5, 6};
  int n = sizeof(arr) / sizeof(arr[0]);
  insertionSort(arr, n);
  printArray(arr, n);
  return 0;
}

삽입 정렬 분석

• Best Case: $O(N)$
• Average Case: $O(N^2)$
• Worst Case: $O(N^2)$

이미 전부 정렬되어 있는 경우 O(N)이지만 랜덤하게 되어있거나, 역순으로 되어있는 최악의 경우일 때는 $O(N^2)$

장점

• 간단하다.
• stable
• 작은 크기의 리스트에 적합하다.

단점

• 큰 크기에서는 적합하지 않음
• 위 두 알고리즘에 비교한 단점은 아니나 일반적으로 머지 소트나 퀵 소트가 더 효율적이다.