[자료구조] 1. 탐색, 배열, 시간복잡도(Big-O) 이해하기 (feat. codestates, self_tutorial)

 

 

 

 

안녕하십니까 다제입니다. 

 

이제부터는 자료구조에 대해서 공부를 진행해보고자 합니다.

 

언제나 새로운 것을 배우는 건 매우 신나는 일입니다! 특히 해당 과정은 코테(코딩테스트)를 위한 필수과정이라고 생각합니다. 

 

대부분의 코딩테스트가 알고리즘을 물어보는 것을 유추하였을 때

기업에서는 알고리즘적 사고를 하는 사람은 충분히 키울 수 있다 라고 생각하는 것 같습니다. 

 

회사를 다녀보면, 업무를 알려주는 것은 간단합니다. 

그러나, 생각의 흐름, 사고를 바꾸는 것은 매우 어려운 일이며, 배우는 사람과 가르치는 사람 모두 에너지가 많이 드는 일입니다. 

 

저희는 준비된 인재가 되기 위해 알고리즘적 사고를 갖추고자 합니다! 

 

이에, 본 포스팅에서는 아래와 같이 5가지 개념에 대해서 알아보도록 하겠습니다. 

 

1. 컴퓨터 알고리즘의 정의 

2. 탐색이란?

3. 정렬이란?

4. 알고리즘 평가방법(Big-O)

5. 배열이란?

 

 

---

 

 

1. 알고리즘의 정의 

그렇다면 과연 알고리즘이란 무엇일까요?

 

컴퓨터 알고리즘이란,

컴퓨터가 어떤 문제를 해결하기 위해서

컴퓨터가 이해할 수 있는 방식으로 정리되어 있는 해결 방법입니다.

 

그렇다면 저는 바로 이런 생각이 들었습니다. 

좋은 알고리즘은 무엇일까?

 

좋은 알고리즘이 되기 위해서는 효과적으로 문제를 해결해야합니다. 

일반적으로 저희가 코테의 문제를 풀때 시간이 오래걸리더라도 문제가 풀기는 합니다. 

그러나, 효율성 체크에서 실패가 뜨고 하지요! 바로 효율성이 떨어지기 때문입니다. 

즉, 좋은 알고리즘을 구현하지 못했다는 이야기입니다. 

 

 

---

 

 

2. 탐색의 정의 

탐색이란?

저정된 정보들 중에서 원하는 값을 찾는 것 입니다. 

 

컴퓨터에서는 탐색하는 방법이 다양하나 가장 기초가 되는 내용에 대해서만 본 포스팅에서 다루겠습니다. 

응용되는 개념은 별도의 포스팅을 진행할 예정이니 참조링크 확인 부탁드립니다.  → 참조링크 

 

일단, 기본적인 탐색은 선형탐색과 이진탐색이 있습니다. 

 

선형탐색 : 리스트의 처음부터 끝까지 순서대로 하나씩 탐색을 진행하는 알고리즘 

이진탐색 : 정렬된 리스트에서 어떤 원소가 리스트 안에 포함되어 있는지 반씩 잘라가며 확인하는 알고리즘 

 

예시코드를 한번 보도록 하겠습니다. 

 

선형탐색 코드 -> 0번 인덱스부터 순서대로 하나씩 확인하여 인덱스를 리턴해주는 함수 

def linear_search(input_data, test_list):
    for i in range(len(test_list)):
        if test_list[i] == input_data:
            return i
    return None

 

이진탐색 코드 -> 원하는 데이터를 찾는데 리스트의 중간값을 기준으로 비교 후 필요없는 부분은 버리고 나머지 부분에서 또 중간값을 찾아 원하는 데이터와 비교하는 방식 

#예시1
def binary_search(input_data, test_list):
    j=0
    while len(test_list) != 0:
        i = len(test_list)//2    
        if input_data > test_list[i]:
            test_list = test_list[i+1:]
            j = i+1
        elif input_data < test_list[i]:
            test_list = test_list[:i]
        elif input_data == test_list[i]:
            j+=i
            return j

#예시 2

def binary_search(input_data, test_list):
    start_index = 0
    end_index = len(test_list) - 1
    
    while start_index <= end_index:
        midpoint = (start_index + end_index) // 2
        if test_list[midpoint] == input_data:
            return midpoint
        elif test_list[midpoint] > input_data:
            end_index = midpoint - 1
        else:
            start_index = midpoint + 1
    return None

이해하시기 더 편한 코드로 테스트를 꼭 진행해보시는걸 추천드립니다. 

 

이 두 탐색 중 어떤 탐색(알고리즘)이 좋은가? 하는 질문에는 답을 할 수 없습니다. 

상황에 따라서 적절한 알고리즘을 선택해야합니다. 

 

한가지 극단적인 예로 facebook 유저가 대략 23억명인데, 

선형탐색으로 유저를 찾는 다면 최악의 경우 23억번 찾아야 합니다. 

이진탐색으로 경우, 31번만 하면 저희가 찾고자 하는 유저를 바로 찾을 수 있습니다. 

 

그러나, 이진탐색을 하려면 정렬이 반드시 되어 있어야 하기 때문에 정렬이 되지 않는 데이터에서는 선형탐색을 사용해야하는 것이지요!

 

 

---

 

 

3. 정렬의 정의

정렬이란?

리스트의 원소들을 특정 순서로 정리하는 것 입니다. 

 

정렬에도 여러 가지 응용되는 개념이 있으나 별도의 포스팅을 진행할 예정이니 참조링크 확인 부탁드립니다.  → 참조링크 

 

일단, 가장 기본적으로 선택정렬과 삽입정렬이 있습니다. 

 

선택정렬(selection sort) : 각 위치에 어떤 값이 들어갈지 찾는 정렬(예를 들어, 가장 찾은 값을 같아서 0번 인덱스에 넣고 0번 인덱스를 제외한 나머지 범위에서 그 다음 작은 값을 찾아 1번 인덱스에 넣는 방법입니다.)

# 선택정렬 소스코드1

def selection_sort(items):
  # 여기에서 len(items) - 1을 하는 이유는 앞에 비교하면 맨마지막꺼는 비교를 하지 않아도 되니 -1해줍니다. 
  for i in range(0, len(items)-1):
    list_index = i

    # 0번째 인덱스가 들어왔으니 비교해야할 대상은 [1:] 인덱스겠지요?
    for j in range(list_index+1, len(items)):
      if items[i] > items[j]:
      # 만약에 i보다 뒤에 있는 j번째에 있는 값이 작다면 변환을 해주면 됩니다. 
        items[j], items[i] = items[i], items[j] 
  return items  

# 선택정렬 소스코드2

def selection_sort(items):
    
  for i in range(0, len(items)-1):    # 외부 반복문(루프)

    cur_index = i
    
    for j in range(i+1, len(items)):  # 내부루프
        if items[j] < items[cur_index]:    # 최소값찾는 로직
            cur_index = j

    temp = items[i]
    items[i] = items[cur_index]
    items[cur_index]= temp 

    return items

# 선택정렬 소스코드3

def selection_sort(items):
    
  for i in range(0, len(items) - 1):    # 외부 반복문(루프)

      cur_index = i
      smallest_index = cur_index
      
      for j in range(cur_index + 1, len(items)):  # 내부루프
          if items[j] < items[smallest_index]:    # 최소값찾는 로직
              smallest_index = j

      items[smallest_index], items[cur_index] = items[cur_index], items[smallest_index]

  return items

 

삽입정렬(insertion sort) : 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘

def ins_sort(unsort_list):

    loop_number = len(unsort_list)          # 반복횟수를 위한 길이설정

    # 앞쪽에 있는 노드들을 검색하기 위한 반복문
    for compare_index in range(loop_number):    # 비교하려는 위치부터 loop_number만큼 반복
        compare_value = unsort_list[compare_index]  
        prev_position = compare_index - 1   # 이전 노드값에 대한 인덱스를 가리킴
        
        # 비교연산 후 삽입을 진행하는 반복문
        while prev_position >= 0 and unsort_list[prev_position] > compare_value:    
            unsort_list[prev_position + 1] = unsort_list[prev_position] # 1-1차작업 : swap을 위한 작업
            prev_position = prev_position - 1
        unsort_list[prev_position + 1] = compare_value    # 1-2차작업 : 비교된 더 큰 값을 (이전노드+1) 인덱스에 삽입

    return unsort_list
            
test_arr = [5,3,1,6]
ins_sort(test_arr)

* 참고사항 *

sorted 함수 : 사용하면 정렬된 새로운 리스트가 리턴되고,

sort 메소드 : 그 리스트 자체를 정렬시켜 준다는 차이점이 있습니다.

 

 

---

 

 

4. 알고리즘 평가법 

그렇다면 알고리즘의 시간에 대한 평가를 어떻게 해야할까요?

직접 구현 시켜보는 방법이 있지만 환경적인 변수(노트북 사양 등)가 고정되지 않기 때문에 정확한 평가가 어렵습니다.

이에, 시작복잡도(Time complexity)시간복잡도와 공간복잡도가 등장하였습니다. 

 

4-1. 시간복잡도

데이터가 많아질수록 걸리는 시간이 얼마나 급격히 증가하는지를 평가하는 방법입니다. 

 

4-2. 공간복잡도(메모리)

공간 복잡도(Space Complexity)는 인풋 크기에 비례해서 알고리즘이 사용하는 메모리 공간을 나타냅니다. 물론 공간 복잡도도 점근 표기법으로 표현할 수 있기 때문에 간편하게 Big-O 표기법을 사용할 수 있습니다. 공간복잡도는 추후 트리, 그래프에서 추가적으로 더 다루겠습니다. 

 

시간복잡도를 더 공부하기 전 복잡도를 표현하는 표기법에 대해서 잠깐 이야기하고 진행토록 하겠습니다. 

바로 점근 표기법이라는 개념입니다. 

 

4-3. 점근 표기법( Big - O )란?

알고리즘이 길이가 n인 input data를 얼마나 빠르게 수행하는지를 수식을 비교하는 방법입니다. 

 

접근 표기법은 3가지 가정을 하고 진행을 합니다. 

[가정1] n이 엄청 크다  

[가정2] n 앞에 있는 상수는 무시한다. 

[가정3] n의 차수가 가장 높은 값이 해당 알고리즘을 대표한다. 

 

n이 엄청 클수록 $n^2$이 급격하게 증가하기 때문에 n의 영향력이 가장 많이 받는 부분이 해당 알고리즘의 성능을 대표할 수 있다라고 생각하는 것입니다. 즉, 알고리즘은 input data의 크기가 클 수록 오래걸린다고 유추를 해볼 수 있습니다. 

소요시간	점근 표기법(Big-O)
$n^2 + 30n + 100$	$O(n^2)$
$200n + 3189$	$O(n)$
$200$	$O(1)$

이진탐색의 경우 반복문을 진행할때마다 리스트의 길이가 반씩 줄어들기 때문에 n번 시행했을 때 시간복잡도는 $lg n$이 된다는 점 꼭 숙지해주세요. 나중에 갑자기 로그를 보게되면 햇갈리실 수 있습니다. 

 

4-4. 시간복잡도에 따른 예시코드

# O(n) 함수
def n_2_time_complexity_samlpe(ex):
    for i in range(len(ex)):
        print(ex[i])

    for i in range(len(ex)):
        print(ex[i])

    for i in range(len(ex)):
        print(ex[i])

 

# O(n^2) 함수
def n_2_time_complexity_samlpe(ex):
    for i in range(len(ex)):
        for j in range(len(ex)):
            print(ex[i], ex[j])

 

# O(n^3) 함수
def n_3_time_complexity_samlpe(ex):
    for i in range(len(ex)):
        for j in range(len(ex)):
            for k in range(len(ex)):
                print(ex[i], ex[j], ex[k])

 

# O(lg n) 함수
# 2의 거듭제곱을 출력하는 함수
# (이번에는 인풋이 리스트가 아니라 그냥 정수입니다)
def log_n(n):
    i = 1
    while i < n:
        print(i)
        i = i * 2

 

# O(nlgn)
def n_log_n(n):
    for i in range(n): # 반복횟수: n에 비례
        j = 1
        while j < n: # 반복횟수: lg n에 비례
            print(i, j)
            j = j * 2

 

이 외에도 훌륭하신 선배님들께서 파이썬 내장함수에 따른 시간복잡도를 표로 정리해신 내용을 아래 그림을 정리를 해보았습니다. 

해당 글을 보고 싶은 분들은 링크를 참조해주세요

출처 : 위 링크 참조

출처 : 위 링크 참조

출처 : 위 링크 참조

 

 

---

 

 

5. 배열

정적 배열 : C언어처럼 리스트를 만들기 전 메모리를 어느정도 사용할지 메모리 크기를 미리 정해놓은 배열

동적 배열

 -. 파이썬 리스트가 바로 동적 배열  

 -. 배열을 위해 메모리에 크기를 미리 정해놓지 않아도 됨

 -. 그러게 데이터가 저장되어 있지 않은 메모리 공간에는 우리가 접근 할 수 없음 

 -. 추가 연산 시간 복잡도 : 최고의 경우O(1), 최악의 경우 : O(n)

 

* 참고사항(지극히 참고사항이니 그냥 읽어만 주세요) *

분할 상환 분석

시간복잡도에서 최고의 경우와 최악경우 중 최고의 경우가 더 빈번하게 발생되는데 시간복잡도를 최악의 경우로 설정하면 비합리적이다. (일반적으로 시간복잡도는 최악을 경우 많이 설정하는 것이 관례이기 때문이다. )

 

이에, 이런 문제점을 해결하기 위해 분할 상환 분석을 사용하게 된다. 

쉽게 이야기하면 분할 상환 분석은 시간 복잡도를 최악으로 경우로 설정하지 않고 평균을 내어 사용하는 것을 말합니다. 

즉, 같은 동작을 n번 했을 때 드는 총 시간이 X일때 동작을 한번 하는데 걸린 시간(X/n)으로 시간복잡도를 설정하는 것을 말합니다. 

구분	정적배열	동적배열
접근(access)	O(1)	O(1)
탐색(search)	O(N)	O(N)
삽입(insert)	N/A	최대 : O(N), 최소 : O(1)
삭제(delete)	N/A	최대 : O(N), 최소 : O(1)

 

지금까지 자료구조를 배우기 위한 기본적인 개념에 대해서 알아보았습니다. 

 

사실 간단한 내용인데 이를 갑작스럽게 들으면 괜시리 어렵게 다가올 수 있습니다. 

 

함께 차근차근 앞으로도 공부를 진행해보겠습니다. 

 

오늘도 방문해주셔서 감사드립니다.