[이취코] ch05. 자료구조 기초 (스택/큐/재귀함수)
탐색: 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
탐색 알고리즘을 이해하기 위해선 기본 자료구조인 스택, 큐에 대한 이해가 있어야한다.
자료구조 : 데이터를 표현하고 관리하고 처리하기 위한 구조
<자료구조 기초 개념 - 함수>
- 삽입(Push) : 데이터를 삽입한다
- 삭제(Pop) : 데이터를 삭제한다.
<자료구조 기초 개념 - 언더플로/오버플로>
- 오버플로(Overflow) : 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 때 (저장공간을 벗어나 데이터가 넘쳐흐를 때)
- 언더플로(Underflow) : 특정한 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행하면 데이터가 전혀 없는 상태이므로 발생
[스택]
스택은 박스 쌓기로 생각하면 된다.
아래부터 위로 쌓는 방식 / 위에서부터 아래로 내리는 방식 : 선입후출(First In Last Out) or 후입선출(Last In First Out)
* 선입후출 : 먼저 넣은 것을 나중에 꺼낸다
* 후입선출 : 나중에 넣은 것을 먼저 꺼낸다
5, 2, 3, 7을 순서대로 스택에 삽입
<삭제> 7이 제일 나중에 들어왔으므로 7 삭제 (후입선출)
1, 4 삽입
<삭제> 4가 제일 늦게 들어왔으므로 4 삭제 (후입선출)
c++코드
#include <iostream>
#include <stack>
using namespace std;
stack<int> s;
int main(void) {
// 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
s.push(5);
s.push(2);
s.push(3);
s.push(7);
s.pop();
s.push(1);
s.push(4);
s.pop();
// 스택의 최상단 원소부터 출력
while (!s.empty()) {
cout << s.top() << ' ';
s.pop();
}
}5 2 3 7 순으로 삽입 → 삭제 → 제일 늦게 들어온 7 삭제 → 5 2 3 → 1 4 삽입 → 5 2 3 1 4 → 삭제 → 제일 늦게 들어온 4 삭제 → 5 2 3 1
(1) 정수형 스택 s 선언
(2) s.push - 스택 s에 삽입
(3) s.pop - 스택 s에 있는 가장 마지막 숫자(최근에 넣은 숫자 삭제)
(4) 스택 s가 빌때까지 출력하고 삭제
(5) 출력값 : 1 3 2 5
[큐]
큐는 대기줄에 비유할 수 있다.
먼저 온 사람이 먼저 들어가고 나중에 온 사람이 나중에 들어간다 → 선입선출(First In First Out) 구조
5, 2, 3, 7 순서대로 숫자 삽입
<삭제> 5가 제일 먼저 들어왔으므로 5가 먼저 삭제된다. (선입선출)
1, 4 삽입 : 들어온 순서대로 왼쪽으로 쌓임
<삭제> 남은 수 중에 2가 제일 먼저 들어왔으므로 2가 삭제된다 (선입선출)
cpp 코드
#include <iostream>
#include <queue>
using namespace std;
queue<int> q;
int main(void) {
// 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
q.push(5);
q.push(2);
q.push(3);
q.push(7);
q.pop();
q.push(1);
q.push(4);
q.pop();
// 스택의 최상단 원소부터 출력
while (!q.empty()) {
cout << q.front() << ' ';
q.pop();
}
}5 2 3 7 순으로 삽입 → 삭제 → 제일 먼저 들어온 5 삭제 → 7 3 2 → 1 4 삽입 → 4 1 7 3 2 → 삭제 → 제일 먼저 들어온 2 삭제 → 4 1 7 3
(왼쪽으로 들어오는 거라고 생각하면 됨 / 오른쪽이 먼저 순서)
따라서 출력값 : 3 7 1 4
[재귀함수]
자기 자신을 다시 호출하는 함수
간단한 재귀함수 예
#include <iostream>
using namespace std;
void recursive_function() {
cout << "재귀함수를 호출합니다"<<endl;
recursive_function();
}
int main(void) {
recursive_function();
}이 코드를 실행하면 "재귀함수를 호출합니다" 라는 문자열이 무한히 출력될 것이다.
위 코드처럼 재귀함수는 종료조건을 제시하지 않으면 함수가 무한호출되어 오류메시지가 나기 때문에 종료조건을 제시해야한다.
종료조건 예시
100번째 재귀함수가 호출되었을때 종료하도록 한다.
#include <iostream>
using namespace std;
void recursive_function(int i) {
if (i == 100) return;
cout << i << "번째 재귀함수에서 " << i + 1 << "번째 재귀함수를 호출합니다"<<endl;
recursive_function(i + 1);
cout << i << "번째 재귀함수를 종료합니다"<<endl;
}
int main(void) {
recursive_function(1);
}
재귀함수를 이용하는 대표적인 예제로 팩토리얼을 볼 수 있다.
팩토리얼을 반복적으로 구현한 방식과 재귀적으로 구현한 두 방식을 비교해보자
반복적으로 구현한 방식
int factorialIterative(int n) {
int result = 1;
// 1부터 n까지의 수를 차례대로 곱하기
for (int i = 1; i <= n; i++) {
result *= i;
}
return result;
}
재귀함수를 통해 구현한 방식
int factorialRecursive(int n) {
// n이 1 이하인 경우 1을 반환
if (n <= 1) return 1;
// n! = n * (n - 1)!를 그대로 코드로 작성하기
return n * factorialRecursive(n - 1);
}코드를 통해 알 수 있듯이 재귀함수가 더 간결하다.
그 이유는 재귀함수가 수학의 점화식(재귀식)을 그대로 소스코드로 옮겼기 때문이다
수학에서 점화식은 특정한 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것을 의미한다.
일반적으로 종료조건을 찾을 때 팩토리얼은 n이 양의 정수일때만 유효하기 때문에 n이 1 이하인 경우 1을 반환할 수 있도록 재귀함수를 작성해야한다.
재귀함수 내에서 특정 조건일 때 더 이상 재귀적으로 함수를 호출하지 않고 종료하도록 if문으로 이용하여 종료조건을 구현해주자.
**참고
컴퓨터 내부에서 재귀함수의 수행은 스택 자료구조를 이용한다.
함수를 계속 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료되기 때문이다
컴퓨터구조에 관한 얘기지만, 재귀함수는 내부적으로 스택 자료구조와 동일하다는 것만 기억하자