[파이썬] 알고리즘(algorithm) / 선형 탐색 / 이진 탐색 / 선택 정렬 / 삽입 정렬 / 알고리즘의 평가 - 시간 복잡도 & Big-O 점근표기법

2023.02.22 ~ 2023.02.23 코드잇 학습내용

 

🔎 알고리즘(algorithm)

수학과 컴퓨터과학, 언어학 또는 엮인 분야에서 어떠한 문제를 해결하기 위해 정해진 일련의 절차

계산을 실행하기 위한 단계적 절차를 의미하기도 함

즉, 문제 풀이에 필요한 계산절차 또는 처리 과정의 순서를 뜻함

알고리즘은 연산, 데이터 마이닝(기계 학습) 또는 자동화된 추론을 수행

 

좋은 알고리즘은 아래 두 가지 조건을 만족해야 함

1. 문제를 해결하는 것

2. 문제를 더 잘 해결하는 것

 

🔎 컴퓨터 알고리즘

컴퓨터가 어떤 문제를 해결하기 위해 컴퓨터가 이해할 수 있는 방식으로 정리되어 있는 일련의 과정 혹은 방법

알고리즘을 설계할 때 시간과 공간 복잡성을 고려하는 것이 중요함

 

📖 알고리즘 수업 듣기 전 복습

⚙ 팰린드롬 문제(for 반복문 사용)

(위의 문제는 Manacher's Algorithm과 관련이 있다고 한다)

 

▼▼▼ 모범답안 ▼▼▼

for 문을 사용하였고 변수를 인덱스로 설정해서 문제를 풀었음

 

▼▼▼ 내가 푼 답안 ▼▼▼

①번 방법 : left, right 변수에 n번까지의 문자열 지정(슬라이싱 활용), n은 word의 중간 인덱스

② 두 번째는 left, right 변수에 i번 문자열 지정

 

🔎 대표적인 컴퓨터 알고리즘

📖 탐색 알고리즘(search algorithm)

⚙ 선형 탐색 알고리즘(linear search algorithm)

리스트에서 특정한 요소를 찾는 데 사용되는 간단한 알고리즘

원하는 요소를 찾을 때까지 리스트의 각각의 요소를 처음부터 끝까지 하나씩 탐색하는 알고리즘

선형 탐색 알고리즘 steps
① 0번 인덱스에서 시작
② 현재의 인덱스와 원하는 요소를 비교
③ 만약 원하는 요소가 현재의 인덱스에 있으면 현재의 인덱스를 return
④ 그렇지 않으면 현재 인덱스를 증가시키고 2단계부터 프로레스를 반복

 

▼▼▼ 선형 탐색 알고리즘을 코드로 작성해 보기 ▼▼▼

 

⚙ 이진 탐색 알고리즘(binary search algorithm)

정렬된 리스트에서 특정한 요소를 찾는 알고리즘 (선형 탐색 알고리즘과 달리 정렬된 리스트를 전제로 함. 정렬된 리스트가 아니면 이 알고리즘은 적용 불가능). 중간 값을 통해 탐색할 범위를 반씩 제외시켜 가며 범위를 좁혀 원하는 값을 찾는 알고리즘

※ 이진 탐색이란 이름을 가지고 있는 이유 : 1회 비교를 거칠 때마다 탐색 범위가 대략 절반으로 줄어들기 때문

 

이진 탐색 알고리즘 steps
① 탐색 간격의 가장 왼쪽 포인트(리스트의 첫번째 인덱스)와 가장 오른쪽 포인트(리스트의 마지막 인덱스)로
    'left'와 'right' 값 설정. 즉, left = 0, right = len(list) - 1
② 'left'가 'right'와 같거나 더 작을 때 아래의 단계를 반복
    → 탐색 간격의 중간 인덱스 계산 mid = (left - right) // 2
    → 만약 중간 인덱스의 값이 목표로하는 값과 같다면 중간 인덱스 return
           if list[mid] == elements:
              return mid
    → 만약 중간 인덱스의 값이 목표로 하는 값보다 크다면, right는 중간 인덱스보다 1 작아짐
           if list[mid] > elements:
               right = mid - 1
        그리고 나서 중간 인덱스의 왼쪽 절반 부분만 다시 탐색
     → 만약 중간 인덱스의 값이 목표로 하는 값보다 작다면, left는 중간 인덱스보다 1 커짐
            if list[mid] < elemnets:
                left = mid + 1
         그리고 나서 중간 인덱스의 오른쪽 절반 부분만 다시 탐색
      → 위의 과정을 반복하며 원하는 값을 찾음 (반복문) 

 

▼▼▼ 이진 탐색 알고리즘을 코드로 작성해 보기 ▼▼▼

 

▼▼▼ 내가 작성한 틀린 코드 ▼▼▼

- 처음에는 while문 아래에서 변하는 변수를 mid_index 자체로 두고, if 문 안에 mid_index = len(some_list) // 2를 실행하도록 하였음. 이렇게 하게 되면 mid_index 자체의 값이 변하게 되므로 처음의 인덱스 번호를 찾을 수 없게 됨. 

- 그래서 그 다음에는 i를 변하는 변수로 두고 작성. 이렇게 작성하게 되면 리스트 요소의 개수가 늘어나게 되면 무한 반복 발생. 왜냐하면 element가 some_list[i]보다 작아서 i를 2로 나눴는데, 그다음 진행 시 element가 some_list[i]보다 클 경우 i는 다시 2배가 되어 앞의 명령을 반복하게 되기 때문

 

⚙ 탐색 알고리즘 비교

선형 탐색은 리스트의 길이가 길어질수록 값을 찾는데 걸리는 시간이 급격하게 길어지지만, 이진 탐색은 리스트의 길이가 길어져도 걸리는 시간이 아주 천천히 늘어남. 따라서 많은 데이터를 다루는 경우 이진 탐색 알고리즘을 사용

그러나 이진 탐색이 가능하기 위해서는 리스트가 정렬이 되어 있어야 함. 정렬이 안된 리스트에서는 선형 탐색을 사용해야 함

 

▼▼▼ 리스트 길이에 따른 탐색 알고리즘 처리 횟수 비교 ▼▼▼

리스트	선형 탐색	이진 탐색
16	16개	4개
32	32개	5개
64	64개	6개
128	128개	7개

 

📖 정렬 알고리즘 (sorting algorithm)

특정 순서로 리스트를 정렬하는 알고리즘

가장 흔하게 사용하는 정렬은 오름차순 혹은 내림차순이나 알파벳 순서 혹은 발생 빈도 수와 같은 특정 조건을 기초로 정렬할 수도 있음

 

파이썬에 sorted 내장 함수 혹은 sort() 메소드 사용해도 되는데 왜 정렬을 배워야 하는가?

정렬 알고리즘은 데이터 베이스 관리, 데이터 분석, 탐색 알고리즘과 같이 많은 용도로 사용되며, 컴퓨터 과학에 필수 내용

다양한 정렬 알고리즘이 개발되었고, 각각의 정렬 알고리즘은 각자의 장점과 단점을 가지고 있음. 그렇기 때문에 데이터셋의 크기나, 이용가능한 리소스와 같은 요소에 따라 알고리즘을 선택하여 사용

 

⚙ 선택 정렬(selection sort)

간단한 정렬 알고리즘으로 정렬되지 않은 리스트에서 가장 작은 값을 찾아 정렬되지 않은 부분의 시작 부분에 있는 값과 바꿈으로써 작동함. 그다음으로 작은 값을 찾을 때마다 정렬되지 않은 부분의 시작 부분에 있는 적정한 위치로 옮겨 전체 리스트가 정렬될 때까지 프로세스를 반복함

 

선택 정렬 steps
① 리스트의 0번 인덱스부터 끝 인덱스까지 중 가장 작은 값을 찾아 0번 인덱스의 값과 자리를 바꿈
    → 0번 인덱스까지 정렬 완료
② 0번 인덱스를 제외하고 나머지 리스트에서 가장 작은 값을 찾아 1번 인덱스의 값과 자리를 바꿈
    → 1번 인덱스까지 정렬 완료
...
③ 전체 리스트가 정렬될 때까지 반복

 

선택 정렬은 데이터의 양이 많아질수록 비효율적이지만 간단하고 쉽다는 장점이 있음

 

⚙ 삽입 정렬(insert sort)

리스트를 정렬된 부분과 정렬되지 않은 부분, 두 부분으로 나누어 작동하는 알고리즘

정렬되지 않은 부분에서 각 값들을 스캔하고 정렬된 부분의 적당한 위치에 값을 삽입함. 필요에 따라 다른 요소들을 이용하여 공간을 확보

 

삽입 정렬 steps
① 리스트의 첫번째 값을 포함해 정렬된 부분으로 세팅
② 첫 번째 값을 제외하고 리스트의 왼쪽부터 오른쪽까지 값을 스캔
③ 적정 위치를 찾을 때까지 정렬된 부분의 오른쪽에서 왼쪽으로 각 값들을 비교
④ 적정 위치를 찾으면 그 위치에 값을 삽입하고 나머지 값들은 이동시킴
⑤ 전체 리스트가 정렬될 때까지 반복

 

▼▼▼ 삽입 정렬 개념 상세 설명 링크 ▼▼▼

삽입 정렬 (개념 이해하기) | 알고리즘 | Khan Academy

 

▼▼▼ 다양한 상황에서의 여러 정렬 알고리즘의 퍼포먼스를 확인할 수 있는 사이트 ▼▼▼

Sorting Algorithms Animations

 

위의 사이트를 보면 이미 거의 정렬된 리스트를 정렬할 때는 삽입 정렬이 가장 빠른 반면, 무작위 순서의 리스트를 정렬할 때는 힙 정렬이 가장 먼저 끝남. 아예 정반대로 정렬된 리스트의 경우에는 삽입 정렬이 매우 오래 걸림. 선택 정렬과 합병 정렬은 상황에 영향을 받지 않고 일정한 시간이 소요됨

 

이렇게 정렬 문제의 경우 "절대적인 좋은 답"이란 없음. 상황에 따른 각 알고리즘의 장단점을 파악해야 올바른 알고리즘을 선택할 수 있음. 따라서 알고리즘을 평가하는 능력을 길러야 함

 

🔎 알고리즘 평가법

알고리즘을 설계할 때 신경 써야 할 것 2가지는 시간과 저장 공간임. 좋은 코드의 첫 번째 기준은 바로 빨리 처리되어야 하는 것(시간)이며 두 번째 기준은 저장 공간을 되도록 적게 차지하는 것임. 그러나 더 중요한 것은 시간 요소(용량은 돈 주고 늘릴 수 있음) ⇒ 시간 복잡도, 공간 복잡도

 

알고리즘의 실행 시간은 컴퓨터가 알고리즘 코드를 실행하는 속도에 의존함. 이 속도는 컴퓨터의 처리속도, 사용된 언어의 종류, 프로그래밍 언어를 컴퓨터가 실행할 수 있는 코드로 바꾸는 컴파일러의 속도 등에 달려있음. 즉, 수식 하나로 어떤 알고리즘의 소요시간을 완벽하게 표현하기 어려움. 컴퓨터의 사양 등 여러 조건에 따라 다르기 때문. 그러나 알고리즘의 실행 시간을 파악할 수 있는 또 다른 요소로 입력값의 크기(인풋 사이즈)도 있음. 우리는 이 입력값의 크기(인풋 사이즈)에 따른 알고리즘을 평가하는 방법을 사용할 예정 ⇒ Big-O 점근표기법

- 인풋 크기 ⇒ 리스트의 길이 n 

 

📖 시간 복잡도(Time Complexity)

인풋 크기의 함수에 따라 알고리즘을 수행하는데 필요로 하는 컴퓨터 리소스(시간)를 측정

데이터가 많아질수록 알고리즘을 처리하는 시간이 얼마나 급격히 증가하는가 

인풋 크기에 비례하는 알고리즘의 실행 시간

시간 복잡도가 클수록, 인풋 크기가 커질수록 알고리즘을 실행하는데 오래 걸림

 

시간 복잡도를 분석하기 위해서는 약간의 수학이 필요

①거듭제곱(exponentiation)

②로그(logarithms)

로그는 거듭제곱의 반대 개념으로 

b를 a로 몇 번 나누어야 1이 되는가

a가 2일 경우 lg라고 쓰기도 함

③ 1부터 n까지의 합

T = 1 + 2+ 3 + ... + (n-2) + (n-1) + n

T = n + (n-1) + (n-2) + ... + 3 + 2 + 1

2T = (1+n) * n

T = (1 + n) * n / 2

 

📖 Big-O 점근표기법

Big-O 점근표기법은

알고리즘의 시간복잡도를 나타내는 데 사용되는 표기법(공간복잡도에서도 사용될 수 있음)

Big-O 점근표기법의 핵심은 n이 엄청 크다고 가정하는 것. n이 별로 크지 않다면 안 좋은 알고리즘을 써도 크게 문제가 없기 때문. 절대적인 시간이 아니라 성장성을 보고 싶기 때문에 n의 영향을 가장 많이 받는 것만 사용. 따라서 점근 표기법은 수식에서 n의 영향력이 가장 큰 것만 표기

 

Big-O 점근표기법 규칙 : 수식에서 n의 영향력이 가장 큰 것만 표기한다

소요 시간	Big-O 점근표기법
20n + 40	O(n)
2n^2 + 8n	O(n^2)
5n^3 + 100n^2 +75	O(n^3)
20lgn + 50	O(lgn)

n이 무한하게 커질수록 나머지 수식은 크게 영향을 미치지 않기 때문

Big-O 점근 표기법의 의미
O(1) : 인풋 리스트의 길이가 증가해도 소요 시간은 똑같음
O(n) : 인풋 리스트의 길이가 x배 증가하면 x배만큼 소요 시간이 증가
O(n^2) : 인풋 리스트의 길이가 x배 증가하면 x^2배만큼 소요 시간이 증가
O(n^3) : 인풋 리스트의 길이가 x배 증가하면 x^3배만큼 소요 시간이 증가

 

⚙ 탐색 알고리즘 평가하기

선형 탐색 알고리즘 평가하기

리스트의 개수 : N개

① 만약, 찾고자 하는 값이 0번 인덱스에 있을 경우 

     → 인덱스 0번인 1개만 확인하면 됨 

     → 시간 복잡도는 O(1) 

② 만약, 찾고자 하는 값이 리스트에 없을 경우

    → 최대 N번 확인해야 함

    → 시간 복잡도는 O(N)

 

이진 탐색 알고리즘 평가하기

리스트의 개수 : N개

① 만약, 찾고자 하는 값이 중간 인덱스에 있을 경우

   - start_index → O(1)

   - last_index → O(1)

   - while문 → O(1) : 중간 인덱스만 확인하면 되기 때문

   - return None → O(1)

   ⇒ 총 시간 복잡도는 O(4)이지만 점근표기법 규칙에 의해 O(1)이 됨 

② 만약, 찾고자 하는 값이 리스트에 없을 경우

   - start_index → O(1)

   - last_index → O(1)

   - while문 → O(lg n) : 중간 인덱스만 확인하면 되기 때문

while 문 첫 시행 후 N의 개수 → N/2
두 번째 시행 후 N의 개수 → 1/2 * N/2
세 번째 시행 후 N의 개수 → 1/2 * 1/2 * N/2
...
K 번째 시행 후 N의 개수 → (1/2)^K * N 
...
찾는 데이터가 없는 경우 남는 데이터의 개수는 최종적으로 1이 됨
따라서 (1/2)^K * N는 1에 수렴하게 됨

   - return None → O(1)

   ⇒ 총 시간 복잡도는 O(lg n + 3)이지만 점근표기법 규칙에 의해 O(lg n)이 됨 

 

⚙ 점근 표기법으로 알고리즘을 평가할 때 주의해야 할 점

코드가 모든 줄은 O(1) 인가요?

NO. 인풋 크기와 상관없이 실행되는 코드만 O(1)

그렇지 않은 코드는 시간 복잡도를 따져봐야 함

만약 리스트에서 in 키워드를 통해 값의 존재 여부를 확인하면 내부적으로 O(n)의 선형 탐색이 이루어짐

 

▼ 다양한 함수, 메소드 등에서의 시간복잡도 평가

Operation	Code	Average Case
인덱싱	my_list[index]	O(1)
정렬	my_list.sort() sorted(my_list)	O(nlg n)
뒤집기	my_list.reverse()	O(n)
탐색	element in my_list	O(n)
끝에 요소 추가	my_list.append(element)	O(1)
중간에 요소 추가	my_list.insert(index, element)	O(n)
삭제	del my_list[index]	O(n)
최솟값, 최댓값 찾기	min(my_list) max(my_list)	O(n)
길이 구하기	len(my_list)	O(1)
슬라이싱	my_list[a:b]	O(b-a)
타입 함수	type(my_list)	O(1)
문자열로 변환	str(N) (N은 d자릿수)	O(log n) 혹은 O(d)

※ sort 메소드나 함수 sorted는 입력의 크기가 커질 경우 효율적으로 정렬하기 위해 퀵 정렬과 같은 진화된 정렬 방식을 사용하기 때문에 O(n lg n)의 시간 복잡도를 가질 수 있음

 

▼ 딕셔너리에서의 시간복잡도 평가

Operation	Code	Average Case
값 찾기	my_dict[key]	O(1)
값 넣어주기/덮어쓰기	my_dict[key] = value	O(1)
값 삭제	del my_dict[key]	O(1)

 

⚙ 주요 시간 복잡도 총 정리

O(1) * : 인풋의 크기가 소요 시간에 영향이 없다는 뜻 

O(lg n) * : 반복문이지만 n이 2배씩 증가할 때 혹은 1/2배씩 감소할 때 (예. 이진 탐색)

O(n) * : 반복문이 있고, 반복되는 횟수가 인풋의 크기와 비례하면 일반적으로 O(n) (예. 선형 탐색)

O(n lg n) * : O(n)과 O(lg n)이 겹쳐졌을 때

O(n^2) * : 2번 중첩 반복문

O(n^3) * : 3회 중첩 반복문

O(n^4) : 4회 중첩 반복문

 

📖 공간 복잡도

인풋 크기에 비례해서 알고리즘이 사용하는 메모리 공간

공간 복잡도 또한 점근 표기법 (Big-O)를 사용할 수 있음

 

⚙ O(1)

파라미터 a, b, c가 차지하는 공간을 제외하면 추가적으로 변수 result가 공간을 차지

리턴되는 result가 차지하는 공간은 인풋과는 무관하므로 함수 product의 공간 복잡도는 O(1)

 

⚙ O(n)

인풋 my_list의 길이를 n으로 가정. 파라미터 my_list가 차지하는 공간을 제외하면 추가적으로 변수 every_other가 공간을 차지. every_other에는 my_list의 짝수 인덱스의 값들이 복사되어 들어감. 약 n/2개의 값이 들어간다는 뜻. O(n/2)는 규칙에 의해 O(n)으로 나타내므로 get_every_other 함수의 공간 복잡도는 O(n)

 

⚙ O(n^2)

인풋 my_list의 길이를 n으로 가정. 파라미터 my_list가 차지하는 공간을 제외하면 추가적으로 변수 products, a, b가 공간을 차지. a와 b는 정수 값을 담으므로 O(1). products는 my_list에서 가능한 모든 조합의 곱이 들어감. 가능한 모든 조합은 n^2개로 O(n^2) ※ 공간 복잡도는 코드가 수행되는 동안 차지하는 메모리. 즉, a * b의 결과가 6개가 나온다고 해서 n^2번을 수행했으므로 공간 복잡도는 O(n^2)