1.1 자료구조와 알고리즘
자료구조란?
프로그램에서 자료들을 정리하여 보관하는 여러 가지 구조. 일상생활에서도 사용한다.
스택: 그릇을 쌓아서 보관하는 것
큐: 마트 계산대의 줄
리스트: 버킷 리스트
사전: 영어사전
그래프: 지도
트리: 컴퓨터 디렉토리 구조
프로그램 = 자료구조 + 알고리즘
알고리즘이란?
컴퓨터로 문제를 풀기 위한 단계적인 절차
문제와 컴퓨터가 주어진 상태에서 문제를 해결하는 방법을 정밀하게 장치가 이해할 수 있는 언어로 기술한 것
정의 1.1 알고리즘
- 입력: 0개 이상의 입력이 존재하여야 한다.
- 출력: 1개 이상의 출력이 존재하여야 한다.
- 명백성: 각 명령어의 의미는 모호하지 않고 명확해야 한다.
- 유한성: 한정된 수의 단계 후에는 반드시 종료되어야 한다.
- 유효성: 각 명령어들은 종이와 연필, 또는 컴퓨터로 실행 가능한 연산이어야 한다.
알고리즘을 기술하는 4가지 방법
- 한글이나 영어와 같은 자연어
- 흐름도(flowchart)
- 의사 코드(pseudo-code)
알고리즘 1.1 배열에서 최대값을 찾는 알고리즘을 의사 코드로 표현한 예
ArrayMax(list, N):
largest<-list[0]
for i <-1 to N-1 do
if list[i]>largest
then largest<-list[i]
return largest
- 프로그래밍 언어
1.2 추상 자료형
자료형: 데이터의 종류
C 언어에서 제공하는 자료형
- 정수(0,1,2,...)
- 실수(3.14)
- 문자('a', 'b', ...)
- 배열(동일한 자료형이 여러 개 모인 것)
- 구조체(다른 자료형이 여러 개 모인 것)
자료형이 결정되면 관련 연산도 달라진다.
ex) 나머지 계산 연산자(%)는 정수 데이터에서는 의미있지만 실수 데이터에서는 의미 없음(컴파일 오류)
따라서 자료형이라하면 데이터 뿐만 아니라 데이터 간에 가능한 연산도 고려해야 한다.
복잡한 자료형(ex. 스택)은 연산할때 함수를 쓰기도 한다.
스택에서 새로운 값을 추가하는 연산은 add()라는 함수.
추상 자료형(ADT: abstract data type): 추상적, 수학적으로 자료형을 정의한 것. 자료구조는 이러한 추상 자료형을 프로그래밍 언어를 구현한 것이라고 볼 수도 있다. 객체와 연산들의 명세(what)가 구현(how)으로부터 분리된 자료형.
책에서는 추상 자료형 먼저 소개할 것임!
추상 자료형은 왜 등장하게 되었을까?
SW 업계의 가장 중요한 이슈 "어떻게 소프트웨어 시스템의 복잡성을 관리할 것인가"
이를 해결하기 위해 추상화(abstraction) 도구들이 개발되었다.
추상화: 어떤 시스템의 간략화된 기술 또는 명세로서 시스템의 정말 핵심적인 구조나 동작에만 집중하는 것.
좋은 추상화를 위해서는 사용자에게 중요한 정보는 강조되고, 중요하지 않은 세부 사항은 제거되는 정보은닉기법이 필요했고,
이 정보은닉기법이 추상 자료형으로 발전되었다.
ADT에서는 데이터나 연산이 무엇(what)인지는 정의되지만, 데이터나 연산을 어떻게(how) 컴퓨터 상에서 구현할 것인지는 정의되지 않는다.
ADT는 객체와 함수로 정의된다.
ADT 1.1 추상 자료형: Nat_Number
객체: 0에서 시작하여 INT_MAX까지의 순서화된 정수의 부분범위
함수:
Nat_Number zero() ::= 0
Nat_Number successor(x) ::= if( x==INT_MAX ) return x
else return x+1
Boolean is_zero(x) ::= if(x) return FALSE
else return TRUE
Boolean equal(x,y) ::= if(x==y) return TRUE
else return FALSE
Nat_Number add(x,y) ::= if( (x+y) <= INT_MAX ) return x+y
else return INT_MAX
Nat_Number sub(x,y) ::= if(x<y) return 0
else return x-y;
1.3 알고리즘의 성능 분석
프로그램의 효율성이 중요한 이유
- 상용 프로그램의 규모가 이전에 비해서 매우 커지고 있기 때문(처리해야 할 자료의 양이 많다)
- 사용자들은 여전히 빠른 프로그램을 선호함
수행시간 측정방법
가장 확실한 방법: 알고리즘을 프로그래밍 언어로 작성하여 실제 컴퓨터상에서 실행시킨 다음, 수행시간을 측정
조건: 똑같은 하드웨어, 소프트웨어 환경 -> 실험이 어려움
알고리즘의 복잡도 분석방법
그래서 알고리즘 복잡도 분석 등장
실행 하드웨어 소프트웨어 환경과 상관없이 알고리즘 효율성 평가 가능
시간 복잡도 함수
알고리즘의 수행시간 분석
- 시간 복잡도
- 공간 복잡도
시간 복잡도에 더 관심이 많아서 보통 알고리즘의 복잡도라고 하면 시간 복잡도를 얘기한다.
시간 복잡도는 알고리즘의 절대적인 수행 시간을 나타내는 것이 아니라 알고리즘을 이루고 있는 연산들이 몇 번 수행되는지를 숫자로 표시한 것
빅오 표기법
T(n) = n^2 + n + 1
차수가 가장 큰 항이 전체의 값을 주도한다.
따라서 시간복잡도 함수에서 차수가 가장 큰 항만을 고려하면 된다.
빅오 표기법을 사용하면 시간 복잡도 함수의 증가에 별로 기여하지 못하는 항을 생략함으로써 시간복잡도를 간단하게 표시할 수 있다.
다항식의 최고차항만을 남기고 다른 항들과 상수항을 버리는 것이다. 최고차항의 계수도 버리고 차수만 사용한다.
가장 많이 쓰이는 빅오 표기법
- O(1): 상수형
- O(logn): 로그형
- O(n): 선형
- O(nlogn): 선형로그형
- O(n^2): 2차형
- O(n^3): 3차형
- O(2^n): 지수형
- O(n!): 팩토리얼형
아래로 갈수록 커짐
빅오표기법 이외의 표기법
빅오 표기법은 최소 차수 함수로 표기되었을 경우만 의미가 있다.
이를 보완하기 위해 빅오메가, 빅세타 표기법이 등장.
가장 정밀한 것은 빅세타 표기법이지만 통상적으로 빅오 표기법을 많이 사용한다.
최선, 평균, 최악의 경우
똑같은 알고리즘도 주어지는 입력에 따라 다른 수행 시간을 보인다.
알고리즘의 효율성은 주어지는 자료집합에 따라 3가지 경우로 나누어서 평가할 수 있음
- 최악(worst case): 입력 자료 집합을 알고리즘에 최대한 불리하도록 만들어서 얼마만큼의 시간이 소모되는지 분석
- 최선(best case)
- 평균(average case)
최악의 경우의 수행시간이 알고리즘의 시간 복잡도 척도로 많이 쓰인다.
연습 문제
01. 2개의 정수를 서로 교환하는 알고리즘을 의사 코드로 작성해보자.
Swap(A, B):
temp <- A
A <- B
B <- temp
return (A, B)
02. 사용자로부터 받은 2개의 정수 중에서 더 큰 수를 찾는 알고리즘을 의사코드로 작성해보자.
FindMax(A, B):
if A > B then
max <- A
else
max <- B
return max
03. 1부터 n까지의 합을 계산하는 알고리즘을 의사 코드로 작성해보자.
SumToN(n):
sum <- 0
for i <- 1 to n do
sum <- sum + i
return sum
04. Set(집합) 추상 자료형을 정의하라. 다음과 같은 연산자들을 포함시켜라.
Create, Insert, Remove, Is_In, Union, intersection, Difference
객체: 중복되지 않는 원소들로 이루어진 집합
함수:
Set Create() ::= return empty_set
Set Insert(Set S, Element x) ::= if( x ∉ S ) return S ∪ {x}
else return S
Set Remove(Set S, Element x) ::= if( x ∈ S ) return S - {x}
else return S
Boolean Is_In(Set S, Element x) ::= if( x ∈ S ) return TRUE
else return FALSE
Set Union(Set S1, Set S2) ::= return S1 ∪ S2
Set Intersection(Set S1, Set S2) ::= return S1 ∩ S2
Set Difference(Set S1, Set S2) ::= return S1 - S2
05. Boolean 추상 자료형을 정의하고 다음과 같은 연산자들을 포함시켜라.
And, Or, Not, Xor
객체: TRUE 또는 FALSE의 두 값 중 하나를 가질 수 있는 논리형 변수.
함수:
Boolean And(Boolean A, Boolean B) ::= if (A == TRUE and B == TRUE) return TRUE
else return FALSE
Boolean Or(Boolean A, Boolean B) ::= if (A == TRUE or B == TRUE) return TRUE
else return FALSE
Boolean Not(Boolean A) ::= if (A == TRUE) return FALSE
else return TRUE
Boolean Xor(Boolean A, Boolean B) ::= if (A ≠ B) return TRUE
else return FALSE
06. 다음과 같은 코드의 시간 복잡도는? 여기서 n이 프로그램의 입력이라고 가정하자.
for(i = 1; i < n; i *= 2)
printf("Hello");
• 첫 번째 반복: i = 1
• 두 번째 반복: i = 2
• 세 번째 반복: i = 4
• 네 번째 반복: i = 8
• …
이렇게 i는 매 반복마다 2배가 되므로, i는 2의 거듭제곱 형태로 증가합니다. 루프가 끝날 조건은 i >= n일 때입니다.
루프가 종료되기 직전의 i 값은 n보다 작은 가장 큰 2의 거듭제곱입니다. 이 값을 2^k라고 하면, 다음이 성립합니다:
2^k < n <= 2^{k+1}
양변의 로그를 취하면:
k < log_2(n) <= k+1
즉, 루프는 약 log_2(n)번 실행됩니다.
O(log n)
07. 다음과 같은 코드의 시간 복잡도는? 여기서 n이 프로그램의 입력이라고 가정하자.
for(i = 0; i < n; i++)
for(j = 1; j < n; j *= 2)
printf("Hello");
외부 루프 (i 루프)
외부 for 루프는 i가 0부터 시작하여 i < n일 동안 1씩 증가합니다. 따라서 이 루프는 총 n번 실행됩니다.
내부 루프 (j 루프)
내부 for 루프는 j가 1부터 시작하여 n보다 작을 때까지 반복됩니다. 반복할 때마다 j는 2배로 증가합니다. j가 2의 거듭제곱 형태로 증가하므로, 이 루프의 반복 횟수는 log_2(n)에 비례합니다.
전체 시간 복잡도
각 i에 대해 내부 루프가 log_2(n)번 실행되므로, 내부 루프의 시간 복잡도는 O(log n)입니다. 외부 루프는 n번 실행되므로 전체 시간 복잡도는 다음과 같이 계산됩니다:
• 외부 루프: O(n)
• 내부 루프: O(log n)
따라서 전체 시간 복잡도는 이 둘의 곱인 O(n log n)이 됩니다.
08. 시간 복잡도 함수 n^2 + 10n + 8 을 빅오 표기법으로 나타내면?
(1) O(n)
(2) O(n \log n)
(3) O(n^2)
(4) O(n^2 \log n)
09. 시간 복잡도 함수 7n + 10 이라면 이것이 나타내는 것은 무엇인가?
(1) 연산의 횟수
(2) 프로그램의 수행 시간
(3) 프로그램이 차지하는 메모리의 양
(4) 입력 데이터의 총개수
10. O(n^2) 의 시간복잡도를 가지는 알고리즘에서 입력의 개수가 2배로 되었다면 수행시간은 어떤 수준으로 증가하는가?
(1) 변함없다.
(2) 2배
(3) 4배
(4) 8배
• 원래 입력 크기를 n 이라 하면, 원래의 수행 시간은 T(n) 으로 표현할 수 있고, 이는 O(n^2) 입니다.
• 입력 크기를 2배로 늘리면 n 이 2n 이 됩니다. 이때 수행 시간은 T(2n) 이 되고, 이 또한 O((2n)^2) 로 계산할 수 있습니다.
T(2n) = O((2n)^2) = O(4n^2)
11. f(n) 에 대하여 엄격한 상한을 제공하는 표기법은 무엇인가?
(1) 빅오메가
(2) 빅오
(3) 빅세타
(4) 존재하지 않는다.
12. 다음의 빅오표기법들로 수행시간이 적게 걸리는 것부터 나열하라.
O(1), \( O(n) \), \( O(\log n) \), \( O(n^2) \), \( O(n \log n) \), \( O(2^n) \), \( O(\sqrt{n}) \)
• O(1)
• O(\log n)
• O(\sqrt{n})
• O(n)
• O(n \log n)
• O(n^2)
• O(2^n)
13. 두 함수 30n + 4 와 n^2 을 여러 가지 n 값으로 비교하라. 언제 30n + 4 가 n^2 보다 작은 값을 갖는지를 구하라. 그래프를 그려보라.
30n + 4 < n^2 인 모든 값..
14. 다음은 실제로 프로그램의 수행시간을 측정하여 도표로 나눈 것이다. 도표로부터 이 프로그램의 시간 복잡도를 예측하여 빅오 표기법으로 나타내라.
| 입력의 개수 | 수행시간 (초) |
|-----------------|------------|
| 2 | 2 |
| 4 | 8 |
| 8 | 16 |
| 16 | 63 |
| 32 | 162 |
답: O(n^3)
1단계: 시간이 어떻게 증가하는지 살펴보기
n이 두 배가 되면 시간이 어떻게 늘어나는지 살펴보세요:
- n이 2에서 4로 증가하면 시간은 2초에서 8초로 늘어납니다. 4배 더 길어집니다.
- n이 4에서 8로 증가하면 시간은 8초에서 16초로 두 배가 됩니다.
- n이 8에서 16으로 증가하면 시간은 거의 4배(16초에서 63초)로 늘어납니다.
- n이 16에서 32로 증가하면 시간이 두 배 이상 증가합니다(63초에서 162초).
2단계: 시간 증가 비교
패턴을 찾고 있습니다. 일반적으로 n이 두 배가 될 때마다 시간이 두 배로 늘어난다면 O(n) 또는 O(n \log n)의 복잡성을 나타냅니다. 하지만 여기서는 그보다 더 빠르게 시간이 증가하는 것 같습니다:
- n이 두 배가 될 때마다 시간이 네 배가 된다면(예: 2에서 4로, 16에서 32로), 이는 O(n^2) 와 같은 것을 의미합니다.
- 그러나 n이 커질수록 시간은 실제로 그보다 훨씬 더 빠르게 증가합니다.
3단계: 시간 복잡도 추측하기
경우에 따라 시간이 4배 이상 증가하는 것을 감안할 때, O(n^2) 보다 더 복잡한 것일 가능성이 높습니다.
결론
n이 증가함에 따라 시간이 매우 빠르게 증가하는 것을 볼 때, O(n^3) 이상의 고차 다항식 시간 복잡도일 가능성이 높습니다. 여기서 패턴은 시간 복잡도가 관찰된 데이터와 일치하는 O(n^3) 정도일 수 있음을 시사합니다.
15. 빅오표기법 정의를 사용하여 다음을 증명하라.
5n^2 + 3 = O(n^2)
16. 빅오 표기법의 정의를 이용하여 \( 6n^2 + 3n \)이 \( O(n) \)이 될 수 없음을 보여라.
6n^2 + 3n 이 O(n)이 될 수 없음을 보여주기 위해, n이 커짐에 따라 n^2 항이 지배적임을 알 수 있습니다. 따라서 어떤 상수 C도 큰 n에 대해 6n^2 + 3n <= Cn 을 만족할 수 없으므로 O(n) 이 될 수 없습니다.
17. 배열에 정수가 들어 있다고 가정하고 다음의 작업의 최악, 최선의 시간복잡도를 빅오 표기법으로 말하라.
(1) 배열의 n 번째 숫자를 화면에 출력한다. O(1)
(2) 배열 안의 숫자 중에서 최소값을 찾는다. O(n) <-최악
(3) 배열의 모든 숫자를 더한다. O(n)
'ML & DL > 책 & 강의' 카테고리의 다른 글
| [나는 리뷰어다] AI 딥 다이브 (0) | 2024.08.25 |
|---|---|
| [밑시딥2] Chapter 8. 어텐션 (0) | 2024.08.12 |
| [밑시딥2] CHAPTER 6 게이트가 추가된 RNN (0) | 2024.07.29 |
| [나는 리뷰어다] 실무로 통하는 타입스크립트 (1) | 2024.07.28 |
| [밑시딥2] CHAPTER 4 (4) | 2024.07.15 |
댓글