이중 for 문 / 자료구조 + a

1. 이중 for 문

2. 자료구조 (스택, 큐)

3. 재귀함수

4. 콜 스택

5. 스택 오버플로우

6. 동적 계획법

---

1. 이중 for 문

for 문 안에 for 문이 들어가 있는 구조를 이중 for 문이라고 한다. 흔한 예시로는 구구단이 있다.

 

// 구구단 n단 출력
function gugudan(num) {
    for (let i = 1; i < 10; i++) {
        console.log(num+" * "+i+" = "+num*i);
    }
}
gugudan(6);

// 구구단 모두 출력
for (let i = 1; i < 10; i++) {
    for (let j = 1; j < 10; j++) {
        console.log(i+" * "+j+" = "+(i*j));
    }
}

 

첫 번째 예시의 경우 gugudan(n)의 n에 원하는 값을 넣으면 거기에 맞는 단이 출력되고, 두 번째 예시의 경우 구구단이 1 * 1 = 1부터 9 * 9 = 81까지 모두 출력된다. 이중 for 문의 특징은 안쪽의 for 문이 모두 실행될 때까지 바깥쪽 for문이 기다렸다가 실행된다는 것이다. 즉, for 문이 실행되는 순서는 안쪽에 있는 for 문부터 바깥쪽으로 이어진다.

 

 

2. 자료구조 (스택, 큐)

[그림 1] 스택의 구조

스택(stack)은 제한적으로 접근할 수 있는 나열 구조이다. 접근 방법은 언제나 목록의 끝에서만 일어난다. 끝먼저내기 목록(Pushdown list)이라고도 한다.

 

스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO, Last In First Out)으로 되어 있다. 자료를 넣는 것을 '밀어넣는다' 하여 푸쉬(push)라고 하고 반대로 넣어둔 자료를 꺼내는 것을 팝(pop)이라고 하는데, 이때 꺼내지는 자료는 가장 최근에 푸쉬한 자료부터 나오게 된다. 이처럼 나중에 넣은 값이 먼저 나오는 것을 LIFO 구조라고 한다.

 

[그림 2] 큐의 구조

큐(queue)는 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 말한다. 영어 단어 queue는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다. 나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다.

 

프린터의 출력 처리나 윈도 시스템의 메시지 처리기, 프로세스 관리 등 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용된다.

 

 

3. 재귀함수

[그림 3] 재귀함수의 구조

재귀함수는 정의 단계에서 자신을 재참조하는 함수를 뜻한다. 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적(recursive)이라고 한다. 재귀함수의 흔한 예시로 피보나치(Fibonacci) 함수가 있다.

 

// 피보나치 함수 예시1
function fibo(n) {
    if (n == 1 || n == 2) {
        return 1;
    }
    return fibo(n-1) + fibo(n-2);
}
console.log(fibo(5));

// 피보나치 함수 예시2
let num = [1, 1];
function fibo2(n) {
    if (num[n-1] > 0) {
        return 1;
    } else if (num[n-1] > 0) {
        return num[n-1];
    } else {
        return fibo2(n-1) + fibo2(n-2);
    }
}
console.log(fibo2(10));

// 피보나치 함수 예시3
let numbers = [];
function fibo3(n) {
    if (numbers[n] > 0) {
        return numbers[n];
    } else if (n === 1 || n === 2) {
        return numbers[n] = 1;
    } else {
        return numbers[n] = fibo3(n-2) + fibo3(n-1);
    }
}
console.log(fibo3(30));

 

피보나치 수열은 1번째, 2번째 값이 1이고, n번째 값이 n-1번째 값과 n-2번째 값의 합이라는 특징이 있다. 이 원리를 이용해 위와 같은 코드를 구현할 수 있다.

 

 

4. 콜 스택

[그림 4] 콜 스택의 구조

콜 스택(call stack)이란 컴퓨터 프로그램에서 현재 실행 중인 서브루틴에 관한 정보를 저장하는 스택 자료구조이다. 또한 실행 스택(execution stack), 제어 스택(control stack), 런 타임 스택(run-time stack) 혹은 기계 스택(machine stack)이라고도 하며, 그냥 줄여서 스택(the stack)이라고도 한다.

 

콜 스택을 사용하는 목적은 여러 가지이지만, 주된 이유는 현재 실행 중인 서브루틴의 실행이 끝났을 때, 제어를 반환할 지점을 보관하기 위해서이다. 실행 중인 서브루틴은, 호출되어서 그 실행이 아직 완료되지는 않았지만, 완료 후에는 호출된 지점으로 제어를 넘겨야 한다. 

 

 

5. 스택 오버플로우

소프트웨어에서 스택 오버플로우(stack overflow)는 스택 포인터가 스택의 경계를 넘어설 때 일어난다. 콜 스택은 제한된 양의 주소 공간을 이루며 대개 프로그램 시작 시 결정된다.

 

프로그램이 콜 스택에서 이용 가능한 공간 이상을 사용하려고 시도할 때, 스택이 오버플로우(overflow)된다고 하며 이 경우 일반적으로 프로그램 충돌이 발생하게 된다.

 

스택 오버플로우의 가장 흔한 원인은 상당히 깊거나 무한으로 이어지는 루프이다. C언어에서 무한 루프의 예는 다음과 같다.

 

int foo() {
    return foo();
}

 

 

6. 동적 계획법

수학과 컴퓨터 과학, 그리고 경제학에서 동적 계획법(dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.

 

조금 더 설명하자면, 주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것이다. 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다. 이러한 방법으로 동적 계획법은 계산 횟수를 줄일 수 있다. 특히 이 방법은 하위 문제의 수가 기하급수적으로 증가할 때 유용하다.

 

피보나치 수열을 구하는 함수를 위의 코드블럭에 나와있는 1번째 예시인 fibo()로 실행할 경우 fibo(5)를 구한다고 하면 계산은 다음과 같이 이루어진다.

 

(1) fibo(5)

(2) fibo(4) + fibo(3)

(3) (fibo(3) + fibo(2)) + (fibo(2) + fibo(1))

(4) ((fibo(2) + fibo(1)) + (fibo(1) + fibo(0))) + (((fibo(1) + fibo(0)) + fibo(1))

(5) (((fibo(1) + fibo(0)) + fibo(1)) + (fibo(1) + fibo(0)) + (fibo(1) + fibo(0)) + fibo(1))

 

여기에서 세 번째 줄의 fibo(2)가 중복되어 계산되고, 이것은 전반적인 계산 속도를 떨어뜨린다. 이 알고리즘의 시간 복잡도는 지수 함수가 된다.

 

이때 각 함수의 계산값을 저장하는 객체를 추가해주면(fibo2()와 fibo3()처럼) 계산 속도가 더욱 빨라진다. 이와 같은 방법을 메모이제이션이라고 한다.

 

※ 메모이제이션  (memoization)

컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다.