4주차. 알고리즘

홍석범·2022년 1월 14일
0

CS50 4주차 알고리즘강좌 링크 📚
이번주 강좌는 배열내의 특정값을 찾는 탐색방법과 배열을 정렬하는 것에대한 강좌이다.

검색 알고리즘 🖥

컴퓨터는 사람과 다르게 배열의 값들을 한번에 파악할 수 없고 배열속에서 특정값을 찾기 위해서는 전체 배열안의 인덱스값들을 하나씩 검색해야한다. 그렇다면 만약 배열내에서 특정 숫자를 찾는다면 어떠한 방법이 있고 어떤 방식이 유리할까?

  • 선형탐색
    배열의 처음부터 하나씩 검색하면서 특정숫자가 나올때까지 찾는 방법. 가장 단순하고 편한 방법이지만 숫자가 정렬되어있지 않을경우 모든 인덱스를 검색해야 될 수 있다.
  • 이진탐색
    배열의 중간값을 탐색하고 해당 값을 비교하여 찾고자 하는 값과 비교하며 그보다 작은(작은 값이 저장되어 있는) 인덱스 또는 큰 (큰 값이 저장되어 있는) 인덱스로 이동을 반복하여 특정값을 찾는다.
    -> 해당 배열이 정렬이 되어있는지에 따라 어떠한 탐색알고리즘을 사용할것인가를 선택하는 것이 효율적인 측면에서 유리하다.

알고리즘 표기법

Big-O 표기법

알고리즘을 수행하는 데 필요한 시간의 상한선. 컴퓨터과학자들이 코드의 효율성을 표현하기 위해 사용한다. 위의 그림에서 O(n/2)은 O(n)으로 표기되는데 이유는 값이 무한히 커진다면 두개의 선은 같아 보이기 때문이다. 이를 바탕으로 다음과같이 실행시간을 표현할수있다.

  • O(n2n^2) - 버블정렬,선택정렬
  • O(nlognnlogn) - 병합정렬
  • O(nn) - 선형 검색
  • O(lognlogn) - 이진 검색
  • O(1)

Big-Ω 표기법

Big-O와 마찬가지로 알고리즘을 수행하는데 필요한 시간의 하한선을 표기하는 방법이다.

  • Ω(n2n^2) - 선택정렬
  • Ω(nlognnlogn) - 병합정렬
  • Ω(nn) - 버블정렬
  • Ω(lognlogn)
  • Ω(1) - 선형 검색, 이진 검색

Omega는 알고리즘을 나타내는 좋은 도구이지만 코드를 구현할 때는 Big-O를 조금 더 신경써야한다.

선형검색

원하는 원소가 발견될때까지 처음부터 마지막 자료까지 차례대로 검색하는 알고리즘. 선형 검색은 자료가 정렬되어 있지 않거나 그 어떤 정보도 없어 하나씩 찾아야 하는 경우에 유용하다. 선형검색은 정확하지만 효율적이지 못한 방법이며 검색을 수행하기 이전에 배열을 정렬해 주는것이 효율적이다.
배열을 정렬하는 여러방법중에서 버블정렬, 선택정렬,병합정렬에 관하여 작성하였다.

버블정렬

두개의 인접한 자료값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법.
ex)

위의 예시를 의사코드로 표현한다면,

Repeat n–1 times
	For i from 0 to n–2
  		If i'th and i+1'th elements out of order
        		Swap them

각각의 루프는 n-1번,n-2번 실행되기 때문에 n23n+2n^2-3n+2번의 비교가 필요하다. 이를 바탕으로 버블정렬의 Big-O를 표시해본다면 n의 값이 무수히 커졌을때 결국 n2n^2에 수렴하기 때문에 O(n2n^2)로 표기할 수 있다. 마찬가지로 만약 배열이 모두 정렬되있을 경우를 감안하면 Ω(nn)이다.

선택정렬

배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식.선택 정렬은 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가한다.
ex)

이를 버블정렬과 마찬가지로 의사코드로 표현한다면,

For i from 0 to n–1
    Find smallest item between i'th item and last item
    Swap smallest item with i'th item

이며, 여기서 n(n+1)/2n(n+1)/2번 만큼 실행되기 때문에, Big-O,Big-Ω 표기법으로 표시한다면 O(n2n^2) , Ω(n2n^2)이다.

병합정렬

앞서 정리한 버블/선택 정렬보다 기능적으로 좋은 정렬 방식이다.
ex)

이를 의사코드로 표현하면

On input of n elements
	if n < 2
		return
	else
		sort left half of elements
		sort right half of elements
		merge sorted halves

이며 해당 코드를 분석해 보면 배열을 반으로나눠서 왼쪽,오른쪽 값들을 정렬하고 두배열을 병합한다. 여기서 병합이란 단순히 두개의 배열을 합치는것이 아닌 내부의 값들을 작은값부터 차례대로 정렬하여 하나의 배열로 만드는것을 의미한다. 병합정렬을 Big-O,Big-Ω 표기법으로 표시한다면 O(nlognnlogn) , Ω(nlognnlogn)이다. 물론 시간의 하한선측면에서 보았을때는 선택정렬(Ω(n2n^2))이 우세하지만 최악의 경우에는 병합정렬의 속도가 더 빠르기때문에 어느정도의 희생은 불가피하다.

강의완료!!💯

profile
코딩하는 주니어개발자

0개의 댓글