1. 자료구조 및 알고리즘 소개
📌기본 전제 : 우리는 컴퓨터를 이용하여 문제를 해결한다고 가정!
1.1. 자료구조(Data structure)란?
기본 개념
1) 현실 세계의 데이터(자료)들을 논리적 구조로 표현하고,
2) 그 데이터를 컴퓨터가 효율적으로 처리할 수 있도록, 컴퓨터(메모리)에 저장하고 연산(조작)하는 방법
- `효율적` : 시간 효율 = 빠르다 / 공간 효율 = 메모리를 적게 쓴다
- 자료구조는 연산까지 포함한 개념
(ex. python의 ‘리스트’라는 자료구조에는 append, pop 등 다양한 연산이 있듯이)
3) 주어진 문제에 알맞은 자료구조를 선택(or 설계)해야, 효율적인 알고리즘을 선택(or 설계)할 수 있음!
- ex) 지하철 노선도 시각화 = 그래프 구조!
보편적으로 가장 많이 쓰이는 논리적 구조
1) 선형 구조 (=리스트)
- 데이터의 앞뒤 관계가 1:1(일대일)로 고정된 구조
- ex. 배열(array), 파이썬 리스트(list), 연결 리스트, 스택, 큐 등
- 배열, 파이썬 리스트와 달리, 연결리스트는 데이터의 논리적 구조와 메모리에 저장되는 물리적 구조가 일치 X ⭐
- 이러한 물리적 구현 방법에 따라, 알고리즘 성능도 달라짐 ex) 연결리스트로 구현한 경우, 이진 검색 써도 성능 좋지 않음(=쓸 필요 없음)
2) 비선형 구조
- 선형 구조가 아닌 구조 (데이터 간의 앞뒤 관계가 1:1로 고정되지 않은 구조)
- ex) 1호선 지하철 노선도는 선형 구조지만, 1~9호선 지하철 노선도는 비선형 구조임
1.2. 알고리즘(Algorithm)이란?
기본 개념
1) 문제에 대해 주어진 입력을 유한한 시간 내에 (정확한) 출력으로 전환시켜줄 수 있는 일련의 연산 절차
- 문제(problem) : 해답(solution)을 찾기 위해 물어보는 질문
- ex) “$N$개의 항목으로 구성된 리스트 $L$에서 $x$라는 수가 있는가?”
- 매개변수(parameter) : 문제에서 특정 값이 주어지지 않은 변수 ; $L, n, x$
- 입력(input) : 매개변수에 특정 값을 지정한 것 ; $L$=[10, 7, 11, 5, 3, 8], $n$=6, $x$=5
- 출력(output) : 입력에 대한 해답 ; “Yes”
2) 표기(기술) 방법
- 자연어 : 프로그램으로 전환하기 어려움. 모호한 경우가 많음.
- 프로그래밍 언어 : 직접 실행 가능. 가독성 낮음. (ex. C, C++, JAVA 등)
- 의사 코드 : 직접 실행 불가능. 가독성 좋음.
- Python : 직접 실행 가능. 가독성 좋음. ✅
알고리즘의 효율성
1) 시/공간 계산복잡도(computational complexity)로 분석하는 게 일반적임
- 구하는 방법은 뒤에서 배울 거임
- ex) `선형검색`과 `이진검색`의 계산복잡도 비교
- : 이진검색의 복잡도가 더 낮음 → 입력 크기가 커질수록 효율 차이가 더 심해짐!!
2) 알고리즘과 마찬가지로, 자료구조의 효율성도 연산의 수행 시간으로 측정함
- ex. 파이썬 리스트에서 `append` 수행하는 데 걸리는 시간
1.3. 학습 목표
[자료구조]
- 보편적으로 많이 쓰이는 논리적 구조를 배워서, (모든 경우에 효율적인 논리적 구조 같은 건 없음;;)
→ 특정 문제해결에 적합한 논리적 구조를 선택하는 능력을 키우자!
→ 다양한 구조의 데이터가, 선형 구조로 저장되는 메모리에 어떻게 저장될 수 있는지 이해하자!
[알고리즘]
- 알고리즘의 대표적인 전략을 배워서,
→ 새로운 문제가 주어졌을 때 가장 적합한 알고리즘 전략을 선택하는 능력을 키우자!
→ ‘적합한’ = 알고리즘이 정확성과 효율성을 보장할 수 있어야 한다는 뜻!
[문제에 알맞은 자료구조 & 알고리즘 선택이 중요한 이유?]
Ex) "정렬 안 한 리스트에서 선형 검색" vs "정렬된 리스트에서 이진 검색" 비교해보자
예시 문제 : 8개 짜리 리스트에 숫자 ‘13’이 존재하는가?
- 1) `정렬 안 한 리스트에서 선형 검색(linear search)`
- 8번 비교하고 나서야 Output 출력 가능
- 일반적으로 ‘선형 검색’은 약 $n/2$ 회 비교해야 결과값 얻을 수 있음
- 2) `정렬된 리스트에서 이진 검색(binary search)`
- 3번만에 Output 출력 가능 → 검색을 원할 땐 정렬리스트+이진탐색 사용하세요!
- 최악의 경우에도 $\log n+1$ 회 비교
2. 알고리즘의 효율성 분석
2.1. 시간효율성과 공간효율성
- 시간 효율성 : 문제를 해결하는 데 얼마나 많은 시간을 요하는가 → CPU 성능
- 공간 효율성 : 문제를 해결하는 데 얼마나 많은 공간을 요하는가 → 메모리 용량
- 보통 시간 효율성이 더 강조됨! (CPU가 더 비싸기 때문!)
- 효율성이 높을수록 복잡도(complexity)가 낮아짐
2.2. 알고리즘의 시간복잡도 분석
1) 계산 방법 : 입력 크기에 따라 단위 연산이 몇 번 수행되는가
- 입력 크기 : 리스트 크기, 트리의 노드 수 등
- 단위 연산 : 알고리즘 수행에 가장 핵심적인 연산 (ex. 비교연산, 수치연산 후 할당연산)
👨🏫시간효율성 = 그냥 연산(코드) 돌렸을 때 걸리는 시간으로 보면 안 될까?
▶ NO! Because…
▶하드웨어 성능의 영향을 받을 수 있음 (당연히 좋은 컴퓨터로 돌리면 시간 적게 걸림)
▶프로그래머의 숙련도의 영향을 받을 수 있음 (코드 고수가 잘 짠 코드는 초보가 복잡하게 짠 코드보다 금방 돌아감)
▶그 외에도 OS 등 알고리즘 외적인 요소의 영향이 많이 들어갈 수밖에 없음
2) 분석 방법 4가지
① 모든 경우 분석 : $T(n)$
- 입력 크기(n)에만 종속되고, 입력 값과는 무관함!
- 리스트 L에 들어있는 값에 상관없이, for 루프를 n번 실행하니까! (=입력값과 무관하게 단위연산 수가 동일!)
- ex) 크기가 n인 리스트 L의 모든 항목의 값을 더하라
- 단위 연산 : line 4 (수치연산 후 할당연산)
- 시간복잡도 : T(n) = n
② 최악의 경우 분석 : $W(n)$
- 입력크기(n)와 입력값 모두에 종속
- x가 리스트 L의 첫 번째 값이면 1번만 수행하면 되는데, 가장 재수 없을 경우(맨 끝에 있는 경우)에는 n번 다 확인해봐야 함! (= 입력값에 종속됨!)
- 단위 연산이 수행되는 횟수가 최대(최악)인 경우
- ex) 크기가 n인 리스트 L에 x라는 수가 존재하는가 확인
- 단위 연산 : line 3 (비교문의 비교연산)
- 시간복잡도 : W(n) = n
③ 최선의 경우 분석 : $B(n)$
- 입력크기(n)와 입력값 모두에 종속
- 단위 연산이 수행되는 횟수가 최소(최선)인 경우
사실상 별 의미가 없는 분석^^;; 최선의 경우가 좋다고 훌륭한 알고리즘 보장할 수 없으니.. - ex) 크기가 n인 리스트 L에 x라는 수가 존재하는가 확인 (②와 동일)
- 단위 연산 : line 3 (비교문의 비교연산)
- 시간복잡도 : B(n) = 1
④ 평균의 경우 분석 : $A(n)$
- 입력크기(n)와 입력값 모두에 종속
- 모든 입력에 대해, 단위 연산이 수행되는 횟수의 기댓값(평균) → 확률적 계산이 필요
- 그래서 보통은 균등분포(uniform dist.)를 가정함
- ex) 크기가 n인 리스트 L에 x라는 수가 존재하는가 확인 (②와 동일)
- 단위 연산 : line 3 (비교문의 비교연산)
- 시간복잡도 :
- x가 L 내에 존재하는 경우만 고려하면…
- A(n) = $\sum_{i=1}^n(i)*{1 \over n} = {(n+1) \over 2}$
- x가 L 내에 존재하지 않는 경우도 고려하면…
- A(n) = $\sum_{i=1}^n(i*{p \over n})+n(1-p) = {(n+1) \over 2}p+n(1-p)$
➡️ 일반적으로 W(n) 혹은 A(n) 방법을 사용함!