자료구조
자료 구조는 자료(data)와 구조(structure)의 합성어로 자료를 정리하여 보관하기 위한 여러 가지 구조들을 뜻합니다.
일상생활에서 물건들을 정리하여 보관하는 방식과 매우 비슷한데 이를 책에서 제시한 예시들을 통해 설명해보겠습니다.
우리는 그릇을 정리할 때, 아래서 부터 하나씩 차곡차곡 쌓아가며 정리합니다. 그릇을 사용해야 될 때에는 반대로 맨 위 그릇부터 하나씩 차례차례 사용하죠. 이는 자료 구조로 스택에 해당합니다. 제일 나중에 저장된 것이 제일 먼저 꺼내어지는 구조이죠. 후입 선출이라고도 얘기합니다. (LIFO: Last In First Out)
그렇다면 우리가 컴퓨터를 사용하면서 스택은 어떤 때에 사용될까요?
다들 문서 작업하다가 잘못 입력된 내용을 바로잡기 위해 되돌리기 키를 사용한 적 있으신가요? 저는 매우 유용하게 사용하고 있는데, 이때 되돌릴 시점의 저장도 스택을 이용해 저장합니다. 제일 마지막 내용을 맨 윗부분에 저장함에 따라 우리는 최근에 했던 작업 내용으로 되돌아갈 수 있게 됩니다.
컴퓨터 내부적으로도 스택을 이용하고 있습니다. 우리가 프로그래밍을 할 때 함수에서 다른 함수를 호출하는 경우가 빈번하게 발생하는데, 호출된 함수가 다 작동을 하면 원래의 함수로 되돌아와야 합니다. 이때의 복귀 주소는 시스템 스택에 쌓이게 됩니다. 마지막에 저장되었던 복귀 주소부터 차례차례 실행되면서 결국 원래의 main 함수에서 프로그램이 종료가 됩니다.
현재는 스택의 간단한 예시와 응용들을 얘기했지만, 책의 후반부에 가면 더 자세하게 설명할 테니 조금만 기다려주세요!
🖥 컴퓨터에 활용되는 다양한 자료구조들
- 되돌리기(undo) 기능을 사용할 때 되돌려지는 시점을 저장하는 스택
- 컴퓨터 파일의 디렉터리 구조
- 함수의 복귀 주소를 기억하는 시스템 스택
- CPU와 주변 기기들의 속도 차이를 해결하기 위한 큐
자료구조와 알고리즘
자료구조가 존재한다면 알고리즘 또한 존재해야 합니다. 자료들이 정렬되어 있어도 그 자료들을 어떻게 사용할 것인지 순서를 정해두지 않으면 아무 쓸모가 없기 때문입니다. 교재에서는 프로그램을 자료구조 + 알고리즘으로 정의하고 있습니다.
간단한 예시를 들어 설명해보겠습니다.
반에 열 명의 아이들이 있습니다. 각 아이들의 성적은 배열로 정렬되어 있습니다. 만약 이 아이들 중 가장 높은 성적을 알아보고 싶다면 어떻게 해야 할까요?
첫 번째로 예시에서는 성적을 저장하기 위해서 배열이라는 자료구조를 사용하였습니다. 그렇다면 이제는 높은 성적을 얻기 위한 알고리즘만 존재한다면 질문의 니즈를 충족할 수 있게 됩니다.
높은 성적을 구하는 방법에는 다양한 알고리즘이 존재하지만, 저는 간단하게 반복문을 통해서 구해보겠습니다.
#include <iostream>
using namespace std;
int main(void){
int n = 10;
int scores[10] = {10, 50, 60, 30, 90 ,55, 67, 43, 12 ,98}; // 학생들의 점수를 임의로 설정
int i, largest;
largest = scores[0]; //초기 값을 집어 넣는다
for(int i = 0; i<n; i++){
if(scores[i] > largest){
largest = scores[i]; // largest 보다 큰 값이 나오면 그 값을 largest에 대입
}
}
cout<<largest<<endl;
}변수 largest 변수와 배열을 계속 비교하여 큰 값이 나오면 그 값이 변수 largest 안에 대입되는 연산을 반복 진행하였습니다. 이러한 방법들을 우리는 알고리즘이라고 합니다.
추상화
우리는 자료형들을 추상적으로 표현하는 것에 익숙해져야 합니다. 추상적으로 표현한 자료형을 추상 자료형이라고 말합니다.
추상 자료형 (Abstract Data Type)은 자료형을 추상적, 수학적으로 정의한 것입니다. 앞에서 간략하게 언급했던 스택, 곧 만나게 될 큐, 연결 리스트, 트리 등의 자료 구조를 추상 자료형으로 나타낼 수 있습니다.
추상 자료형의 간단한 예시를 소개하겠습니다.
Nat_Number
객체 (Object):
0에서부터 시작하여 컴퓨터가 표현할 수 있는 범위 (2의 31승)까지 순서화된 정수의 부분 범위
함수 (Function):
Nat_Number zero() := 0
Nat_Number is_zero(x) := x가 0이 라면 true, 0이 아니라면 false 리턴
Nat_Number eqaul(x, y) := x, y가 같다면 true, 다르다면 false 리턴
Nat_Number add(x, y) := x+y가 표현 가능 범위를 넘지 않는다면 x+y, 넘는다면 최대 가능 범위 (INT_MAX) 리턴
Nat_Number sub(x, y) := y가 x보다 크다면 0, 그렇지 않다면 x-y의 결괏값을 리턴
이처럼 핵심적인 구조나 동작에만 집중한 것이 추상 자료형입니다.
성능 분석
알고리즘의 성능을 분석하는 방법은 몇 가지 방법이 존재합니다. 그중에서 저는 시간 복잡도를 사용해서 비교하는 방법을 서술하겠습니다. 시간 복잡도는 절대적인 수행 시간이 아닌 알고리즘들이 이루고 있는 연산들이 몇 번 수행되는지 숫자로 표시합니다. 수행된 연산의 숫자를 비교하여 알고리즘의 효율성을 따지는 것입니다. 자세한 내용은 제 블로그에 포스팅해두었으니 참고하면 좋을 것 같습니다 :)
2022.04.02 - [Algorithm/Base] - 시간 복잡도
📌 연습 문제
01
의사 코드는 정해져 있는 문법이 없습니다. 일반적인 언어를 프로그래밍 언어의 형태로 작성하면 그것이 곧 의사 코드입니다.
Swap(A,B):
temp <- A;
A <- B;
B <- temp;물론 의사 코드가 아닌 C/C++로 작성하면 추가되는 개념이 존재합니다. 함수는 매개변수로 받은 변수들을 지역변수로서 할당하며 함수의 호출이 끝나면 사라집니다. 작성한 Swap 함수에서 아무리 A와 B의 값을 바꿔도 그 값은 함수 내에서만 유효하지 복귀 함수로 되돌아가면 존재하지 않습니다. 따라서 외부에서 변수에 직접 접근할 권한을 주는 포인터 선언이 필요합니다.
void swap(int * A, int * B){
int temp;
temp = *A;
*A = *B;
*B = temp;
}02
CompareTwoNum(A,B):
largest;
if(A>B)
then largest <- A
else
then largest <- B
return largest03
GetSum(n):
sum <- 0;
for i<-1 to n do
sum <- sum +i;
return sum;2,3 번 문제 역시 의사코드로 알고리즘을 작성하는 간단한 문제였습니다. 앞서 언급했듯이 의사 코드는 정해진 기준이 없다는 걸 다시 한번 강조 드립니다.
04
Set
객체 (Object):
원소라 불리우는 데이터 요소들의 모임
함수 (Function):
Create(): 집합 생성
Insert(S, x): 집합 S에 원소 x를 삽입
Remove(S, x): 집합 S에서 원소 x를 제거
Is_In(S, x): 집합 S에 원소 x가 존재하면 true, 존재하지 않는다면 false
Union(S1, S2): 집합 S1과 S2의 합집합
Intersection(S1, S2): 집합 S1과 S2의 교집합
Difference(S1, S2): 집합 S1과 S2의 차집합
05
Boolean
객체 (Object):
데이터들의 비교 연산
함수 (Function):
And(A, B): A와 B 둘다 참이라면 true, 하나라도 참이 아니라면 false 리턴
Or(A, B): A와 B 둘 중 하나라도 참이라면 true, 하나도 참이 아니라면 false 리턴
Not(A): A가 참이라면 false, 거짓이라면 true 리턴
Xor(A, B): A와 B의 값이 다르다면 true, 같다면 false
06
for(i = 1; i < n; i *= 2)
cout<<"hello"<<endl;$n$을 $2^{t}$ 라고 생각해보면, $i$에 2를 $t$번 곱하면 조건문을 만족합니다. 따라서 반복문은 $t$번 실행된다는 것을 알 수 있습니다. $t$는 아까 $2^{t}$로 치환했기에 풀어보면 $t=log_{2}n$ 을 만족합니다.따라서 시간 복잡도는 $O(log n)$ 입니다.
07
for(i = 0; i < n; i++)
for(j = 1; j < n; j *= 2)
cout<<"hello"<<endl;중첩 반복문 입니다. 안쪽 반복문은 6번 문제와 마찬가지로 $n$을 $2^{t}$ 라고 생각하고 $t$번 실행된다는 것을 풀어보면 $t=log_{2}n$ 을 만족합니다.따라서 시간 복잡도는 $O(log n)$ 입니다. 바깥 반복문은 n번 실행하므로 시간 복잡도는 $O(n \cdot log n)$ 입니다.
08
$n^{2}+10n+8$을 빅오 표기법으로 나타내면 $O(n^{2})$입니다. 시간 복잡도는 최고 차항이 영향이 제일 크기 때문에 최고 차항을 제외한 나머지 차수는 버리고 사용합니다.
09
시간 복잡도 홤수는 연산의 횟수를 의미합니다.
10
$O(n^{2})$ 의 시간 복잡도를 가지는 알고리즘의 입력의 개수가 2배가 늘었다면 4배가 됩니다. 간단한 산술식으로 표현해보면 입력의 개수 $n$이 2였다면 연산의 횟수는 4, 두배 더 늘은 $n$이 4였다면 연산의 횟수는 16이 됩니다. 4배 차이가 나는 것을 볼 수 있습니다.
11
$f(n)$에 대해 엄격한 상한을 제공하는 표기법은 빅 오, 엄격한 하한을 제공하는 표기법은 빅 오메가이며 이 둘을 합하여 비교하는 표기법이 빅 세타입니다.
12
수행 시간이 적게 걸리는 것 부터 나열해보면:
$O(1) < O(log n) < O(n) < O(n\cdot log n) < O(n^{2}) < O(2^{n}) < O(n!)$
13
$n$이 31이 될 때 $30n^{2}+4$가 $n^{2}$보다 작은 값을 가진다
14
| 입력의 개수 n | 수행시간 (초) |
| 2 | 2 |
| 4 | 8 |
| 8 | 25 |
| 16 | 63 |
| 32 | 162 |
표를 보면 수행 시간 표의 근사치는 $O(n\cdot log n)$ 인것을 알 수 있습니다.
입력의 개수가 4일 때, $4 \cdot log_{2}4 = 8$
입력의 개수가 8일 때, $8 \cdot log_{2}8 = 24$ (25의 근사치)
'C언어로 쉽게 풀어쓴 자료구조' 카테고리의 다른 글
| 3장 배열, 구조체, 포인터 (0) | 2022.04.17 |
|---|---|
| 2장 순환 (0) | 2022.04.17 |
댓글