[자료구조] 240606 학습일기 - ch1. 자료구조와 알고리즘의 이해

Rust 강의를 들으며 지금 이걸 공부할 때가 아니라는 생각이 문득 들었다.

컴싸로 전과한지 얼마 안된 나는 현재 cs 기초가 전혀 안 잡혀있다.😅

자료구조부터 뿌셔보자!

윤성우의 열혈 자료구조 - 예스24

---

1. Linear Search(순차 탐색)

#include <stdio.h>
int lSearch(int arr[], int len, int target) {
  for (int i = 0; i < len; i++) {
    if (target == arr[i]) {
      return i;
    }
  }
  return -1;
}

int main(void) {
  int arr[] = {1, 3, 5, 7, 9};

  int result = lSearch(arr, sizeof(arr) / sizeof(int), 5);
  if (result == -1) {
    printf("Linear Search 실패");
  } else
    printf("Linear Search 성공!\nIndex: %d", result);
  return 0;
}

콘솔 출력

Linear Search 성공!
Index: 2

 

---

여기서

sizeof(arr) / sizeof(int)

는 arr 내의 원소의 개수를 표현한다. 한마디로 int로만 구성된 배열의 길이.

python의 len(), javascript의 length() 같은 역할을 한다.

 

 

 

2. Binary Search(이진 탐색)

---

이진 탐색 알고리즘은 정렬된 데이터에서만 적용이 가능하다.

---

#include <stdio.h>
int bSearch(int arr[], int len, int target) {
  int first = 0;
  int last = len - 1;
  while (first <= last) {
    int mid = (first + last) / 2;
    if (arr[mid] == target) {
      return mid;
    } else if (arr[mid] < target) {
      first = mid + 1;
    } else {
      last = mid - 1;
    }
  }
  return -1;
}

int main(void) {
  int arr[] = {1, 3, 5, 7, 9};

  int result = bSearch(arr, sizeof(arr) / sizeof(int), 5);
  if (result == -1) {
    printf("Binary Search 실패");
  } else
    printf("Binary Search 성공!\nIndex: %d", result);
  return 0;
}

 

 

 

3. LS worst Op count VS BS worst Op count

#include <stdio.h>
int bsWorstOpCount(int arr[], int len, int target) {
  int first = 0;
  int last = len - 1;
  int opCount = 0;
  while (first <= last) {
    int mid = (first + last) / 2;
    if (arr[mid] == target) {
      return opCount;
    } else if (arr[mid] < target) {
      first = mid + 1;
    } else {
      last = mid - 1;
    }
    opCount += 1; // ==을 기준으로 세면 됨.
  }
  return opCount;
}

int lsWorstOpCount(int arr[], int len, int target) {
  int opCount = 0;
  for (int i = 0; i < len; i++) {
    if (target == arr[i]) {
      return opCount;
    }
    opCount += 1;
  }
  return opCount;
}

void main(void) {
  int arr1[500] = {
      0,
  };
  int arr2[5000] = {
      0,
  };
  int arr3[50000] = {
      0,
  };

  int BSopCount1 = bsWorstOpCount(arr1, sizeof(arr1) / sizeof(int), 5);
  int BSopCount2 = bsWorstOpCount(arr2, sizeof(arr2) / sizeof(int), 5);
  int BSopCount3 = bsWorstOpCount(arr3, sizeof(arr3) / sizeof(int), 5);
  int LSopCount1 = lsWorstOpCount(arr1, sizeof(arr1) / sizeof(int), 5);
  int LSopCount2 = lsWorstOpCount(arr2, sizeof(arr2) / sizeof(int), 5);
  int LSopCount3 = lsWorstOpCount(arr3, sizeof(arr3) / sizeof(int), 5);

  printf("500 length의 Worst Binary Search 연산 횟수: %d", BSopCount1);
  printf("\n5000 length의 Worst Binary Search 연산 횟수: %d", BSopCount2);
  printf("\n50000 length의 Worst Binary Search 연산 횟수: %d", BSopCount3);
  printf("\n");
  printf("\n500 length의 Worst Linear Search 연산 횟수: %d", LSopCount1);
  printf("\n5000 length의 Worst Linear Search 연산 횟수: %d", LSopCount2);
  printf("\n50000 length의 Worst Linear Search 연산 횟수: %d", LSopCount3);
}

콘솔 출력

500 length의 Worst Binary Search 연산 횟수: 9
5000 length의 Worst Binary Search 연산 횟수: 13
50000 length의 Worst Binary Search 연산 횟수: 16

500 length의 Worst Linear Search 연산 횟수: 500
5000 length의 Worst Linear Search 연산 횟수: 5000
50000 length의 Worst Linear Search 연산 횟수: 50000

---

탐색 알고리즘에서의 핵심은 동등비교를 하는 비교 연산(==)에 있다.

==을 기준으로 비교연산의 횟수를 카운트하면 된다.

값의 동등을 비교하는 ==연산을 적게 수행하는 탐색 알고리즘이 좋은 탐색 알고리즘이다.

---

O(log n)의 위력이 대단한 것 같다.

 

고딩때 수학학원 선생님께서 log n, n, nlogn, n², n³, 2의 n승의 증가율을 비교해서 설명해주셨었는데 그때 외웠던 게 은근 도움이 많이 된다.

---

**1. Binary Search에서 mid+1, mid-1이 아닌 mid로 짜면 안되는 이유

if (arr[mid] < target) {
      first = mid;
} else {
      last = mid;
}

실제로 해보면 아래와 같이 무한반복된다는 걸 알 수 있다.

근데 더 명확한 설명이 교재에 나와있다.

 

세 변수에 저장된 인덱스 값은 first <= mid <= last 를 만족하도록 알고리즘이 디자인되어 있다.
그런데 기껏 하는 연산이 mid에 저장된 값을 가감 없이 first 또는 last에 저장하는 것이 전부인데, 어떻게 first에 저장된 값이 last보다 커질 수 있겠는가?

 

 

**2. 연습문제 1-1 빅-오 구하기

 

**3. 연습문제 1-2 빅-오의 증명

 

---

Big O notation:

데이터 수의 증가에 따른 연산 횟수의 증가 형태를 표현한 것

데이터 수의 증가에 따른 연산 횟수의 증가율의 상한선을 표현한 것