4. 알고리즘

최준영·2021년 8월 25일
0

CS50

목록 보기
4/6

알고리즘 표기법


Big O

  • Big O가 알고리즘 실행 시간의 상한을 나타낸다.
  • O(n/2)는 n이 매우커지면 1/2는 의미없어지므로 O(n)이라고 본다.
  • 주로 사용하는 Big O 표기
    • O(n^2)
    • O(n log n)
    • O(n) - 선형 검색
    • O(log n) - 이진 검색
    • O(1)

Big Ω

  • Big Ω는 알고리즘 실행 시간의 하한을 나타낸다.
  • 선형 검색의 경우 n개의 항목이 있을 때 최대 n번의 검색을 해야 하므로 O(n)이지만, 한번에 검색을 끝낼 수도 있기 때문에 Ω(1)이다.
  • 주로 사용하는 Big Ω 표기
    • Ω(n^2)
    • Ω(n log n)
    • Ω(n) - 배열 안에 존재하는 값의 개수 세기
    • Ω(log n)
    • Ω(1) - 선형 검색, 이진 검색

선형 검색


  • 원하는 요소가 발견될 때까지 처음부터 마지막 자료까지 차례대로 검색한다.
  • 정확하지만 효율적이지 못하다.
  • 자료가 정렬되어있지 않거나 어떤 정보도 없어 하나씩 찾아야하는 경우에 유용하다.

구조체


  • 배열은 같은 자료형끼리 묶었다면, 구조체는 비슷한 성격을 띄는 요소들끼리 묶는다.
typedef struct
{
    string name;
    string number;
}
person;
  • 이름과 전화번호는 사람이라는 구조체로 묶을 수 있다.
  • 이름과 전화번호와 같은 속성값은 .으로 연결해서 접근할 수 있다.
  • person a 라는 변수가 있다면 a.name과 같이 이름에 접근한다.

이진 검색


  • 만약 배열이 정렬되어 있다면, 배열 중간 인덱스부터 시작하여 찾고자 하는 값과 비교하며 내가 원하는 값이 작다면 절반의 앞을 살펴보고 크다면 절반의 뒤를 살펴보는 방법을 반복하는 것을 의미한다.

버블 정렬


  • 정렬되지 않는 리스트를 탐색하는 것보다 정렬한 뒤 탐색하는 것이 효율적이다.
  • 버블 정렬은 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법을 말한다.
  • 6 3 8 5 2 7 4 1(3과 6 비교 후 교환) -> 3 6 8 5 2 7 4 1(6과 8 비교 후 넘어감. 8과 5 비교 후 교환) -> 3 6 5 8 2 7 4 1(반복)

선택 정렬


  • 배열 안의 자료 중 가장 작은 수 (혹은 가장 큰 수)를 찾아 첫번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬이다.
  • 교환 횟수를 최소화 하는 반면 각 자료를 비교하는 횟수는 증가한다.
  • 6 3 8 5 2 7 4 1(가장 작은 수인 1을 교환) -> 1 3 8 5 2 7 4 6(두번째로 작은 수인 2를 교환) -> 1 2 8 5 3 7 4 6(반복)
  • 작은 수를 찾고 교환하는 과정을 요소의 개수만큼 진행하기 때문에 소요 시간의 상한은 O(n^2), 하한은 Ω(n^2)이다.
  • 버블 정렬도 동일하다.

정렬 알고리즘의 실행시간


  • 버블정렬에서 교환이 일어나지 않을때까지만 수행하도록 한다면 하한을 Ω(n)로 개선할 수 있다.

재귀


  • 함수가 본인 스스로를 호출하는 경우를 말한다.

병합 정렬


  • 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식이다.
  • 과정
    • 7 | 4 | 5 | 2 | 6 | 3 | 8 | 1 → 가장 작은 부분 (숫자 1개)으로 나눠진 결과이다.
    • 4 7 | 2 5 | 3 6 | 1 8 → 숫자 1개씩을 정렬하여 병합한 결과이다.
    • 2 4 5 7 | 1 3 6 8 → 숫자 2개씩을 정렬하여 병합한 결과이다.
    • 1 2 3 4 5 6 7 8 → 마지막으로 숫자 4개씩을 정렬하여 병합한 결과이다.
  • 실행시간의 상한은 O(n log n)이다. 숫자를 반으로 나누는 데에 O(log n)의 시간이 들고, 나눈 부분들을 정렬해서 병합하는데 O(n)의 시간이 걸린다.
  • 하한도 O(n log n)이다.
profile
do for me

0개의 댓글