딩코딩 : Computer Science 블로그

build.gradle의

plugins에

id 'kotlin-android-extensions'

를 추가하면 추가적인 자동완성기능을 이용할 수 있다.

https://www.acmicpc.net/problem/5670

1. 문제설명

휴대폰 자판을 입력할 때 자동완성기능이 존재하면,

특정 단어를 입력하기 위해서 자판을 몇번 눌러야 하는지 계산하는 문제이다.

단어 리스트가 주어지고, 각 단어마다 몇번 눌러야하는지 구하는 과정에서

트라이 알고리즘을 이용해야 문제를 시간내에 해결할 수 있다.

주어진 단어로 위와 같이 트리를 미리 구현하고

분기점과 단어가 끝나는 지점마다 카운트해주어야

하나의 단어를 입력하기 위해 자판을 몇번 입력해야하는지 알아낼 수 있다.

2. 문제풀이코드 C++

#include <bits/stdc++.h>
#define ALPHABETS 26
using namespace std;


const int ROOT = 1;
int unused = 2;
const int MX = 1000'003;
int nxt[MX][26];
bool chk[MX];
int childs[MX];

int ctoi(char c){
    return c-'a';
}

void insert(string &s){
    int cur = ROOT;
    for(auto c : s){
        if(nxt[cur][ctoi(c)] == -1){
            childs[cur]++;
            nxt[cur][ctoi(c)] = unused++;
        }
        cur = nxt[cur][ctoi(c)];
    }
    chk[cur] = true;
}


int count(string &s){
    int res = 1;

    int cur = ROOT;
    for(int i=0; i<s.length();i++){
        cur = nxt[cur][ctoi(s[i])];

        if(i!=s.length()-1 && (childs[cur] > 1||chk[cur])){
            res++;
        }
    }
    return res;
}


vector<string> words;



int n;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    while(cin >> n){
        words.clear();
        unused = 2;

        fill(childs, childs+MX , 0);
        fill(chk, chk+MX, 0);
        for(int i=0; i<MX; i++){
            fill(nxt[i], nxt[i]+26, -1);
        }

        for(int i=0; i<n; i++){
            string s;
            cin >> s;
            insert(s);
            words.push_back(s);
        }


        double sum = 0;
        for(auto s : words){
//            cout << s << '\n';
//            cout << count(s) << '\n';
            sum += count(s);
        }


        cout << fixed;
        cout.precision(2);
        cout << sum / n << '\n';



    }

    return 0;
}

#include <stdio.h>
#include <stdlib.h>

struct node {
    int data;
    struct node *left;
    struct node *right;
} Node;

// 데이터 삽입(recursion)
void insert(struct node **root, int data) {
    struct node* ptr;
    struct node* newNode = (struct node*)malloc(sizeof(struct node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;

    if(*root == NULL){
        *root = newNode;
        return;
    }

    ptr = *root;

    while(ptr){
        if(data < ptr->data){
            if(ptr->left == NULL){
                ptr->left = newNode;
                return;
            }
            else{
                ptr = ptr->left;
            }
        }
        else{
            if(ptr->right == NULL){
                ptr->right = newNode;
                return;
            }
            else{
                ptr = ptr->right;
            }
        }
    }
}

// 전위(preorder)탐색(recursion)
void preOrder(struct node *root) {
    if(root == NULL) return;
    printf("%d ", root->data);
    preOrder(root->left);
    preOrder(root->right);
}

// 중위(inorder)탐색(recursion)
void inOrder(struct node *root) {
    if(root == NULL) return;
    inOrder(root->left);
    printf("%d ", root->data);
    inOrder(root->right);
}

// 후위(postorder)탐색(recursion)
void postOrder(struct node *root) {
    if(root == NULL) return;
    postOrder(root->left);
    postOrder(root->right);
    printf("%d ", root->data);
}

// 노드의 개수(recursion)
int size(struct node *root) {
    if(root == NULL) return 0;
    return 1 + size(root->left) + size(root->right);
}

// 높이(recursion)
int height(struct node *root) {
    if(root == NULL) return 0;
    if(root->left == NULL && root->right == NULL) return 0;

    int leftHeight = height(root->left);
    int rightHeight = height(root->right);
    return 1 + (leftHeight>= rightHeight ? leftHeight : rightHeight);
}

// 미러 이미지로 변환하기(recursion)
void mirror(struct node **root) {
    if(*root == NULL) return;
    mirror(&(*root)->left);
    mirror(&(*root)->right);
    struct node *tmp = (*root)->left;
    (*root)->left = (*root)->right;
    (*root)->right = tmp;
}

// 노드에 저장된 데이터의 값의 합 구하기(recursion)
int sumOfWeight(struct node *root) {
    if(root == NULL) return 0;
    return sumOfWeight(root->left) + sumOfWeight(root->right) + root->data;
}

// 루트노드부터 단말노드까지의 경로 상의 데이터의 최대합(recusrion)
int maxPathWeight(struct node *root) {
    if(root == NULL) return 0;
    int leftWeight, rightWeight;
    leftWeight = maxPathWeight(root->left);
    rightWeight = maxPathWeight(root->right);
    return root->data + (leftWeight>=rightWeight ? leftWeight : rightWeight);
}

// 트리노드의 동적 메모리 해제하기(recursion)
void destruct(struct node **root) {
    if(*root == NULL) return;
    destruct(&((*root)->left));
    destruct(&((*root)->right));
    free(*root);
    *root = NULL;
}

버튼을 눌렀을 때 새로운 Activity를 호출하는 예시이다.

package com.example.harudemo.fragments

import android.content.Context
import android.content.Intent
import android.os.Bundle
import android.util.Log
import android.view.LayoutInflater
import android.view.View
import android.view.ViewGroup
import android.widget.Button
import androidx.fragment.app.Fragment
import com.example.harudemo.R
import com.example.harudemo.sns.SnsTestActivity

class SnsFragment: Fragment() {
    companion object{
        const val TAG : String = "로그"

        fun newInstance() : SnsFragment {
            return SnsFragment()
        }
    }

    override fun onCreate(savedInstanceState: Bundle?) {
        super.onCreate(savedInstanceState)
        Log.d(TAG, "HomeFragment - on Create() called" )
    }


    override fun onAttach(context: Context) {
        super.onAttach(context)
        Log.d(TAG, "HomeFragment - onAttach() called")
    }

    //뷰가 생성되었을 때
    //프래그먼트와 레이아웃을 연결시켜주는 부분이다.
    override fun onCreateView(
        inflater: LayoutInflater,
        container: ViewGroup?,
        savedInstanceState: Bundle?
    ): View? {
        Log.d(TAG, "HomeFragment - onCreateView() called")

        val view = inflater.inflate(R.layout.fragment_sns, container, false)

        return view
    }

    override fun onViewCreated(view: View, savedInstanceState: Bundle?) {
        super.onViewCreated(view, savedInstanceState)

        //버튼이 클릭되면 액비티비 호출
        val btnActivity: Button = view.findViewById(R.id.btn_newActivity)
        btnActivity.setOnClickListener{
            activity?.let{
                val intent = Intent(it, SnsTestActivity::class.java)
                it.startActivity(intent)
            }
        }
    }
}

docker 명령어

이미지, 컨테이너 전체 삭제

docker rm -f $(docker ps -aq)

gcc 이미지, 입력가능한 터미널을 이용해 실행

-it 조건은 interactive를 의미하고 이는 현재 터미널에서 실행됨을 뜻한다.

docker run -it --name ex3ct gcc:9 /bin/bash

볼륨 마운트해서 호스트와 컨테이너 데이터 공유하기

docker run -it --name ex3ct -v "호스트전체경로:/source" gcc:9 /bin/bash

이때 호스트 전체경로는 bash 명령어로 pwd를 사용하면 쉽게 구할수 있다.

다음과 같이 명령어를 치면 된다.

docker run -it --name ex3ct -v "/Users/lmj/Desktop/os/2차과제:/source" gcc:9 /bin/bash

exec를 이용해 -it, /bin/bash를 명령어에 넣어주면 터미널을 추가하여 실행할 수 있다.

docker exec -it ex3ct /bin/bash

activity_main.xml

<?xml version="1.0" encoding="utf-8"?>
<LinearLayout xmlns:android="http://schemas.android.com/apk/res/android"
    xmlns:app="http://schemas.android.com/apk/res-auto"
    xmlns:tools="http://schemas.android.com/tools"
    android:layout_width="match_parent"
    android:layout_height="match_parent"
    android:orientation="vertical"
    tools:context=".MainActivity">

    <TextView
        android:id="@+id/tvInput"
        android:layout_width="match_parent"
        android:layout_height="250dp"
        android:background="@color/light_gray"
        android:padding="10dp"
        android:textSize="40dp"
        android:text=""
        android:gravity="right|bottom"
        />
    <LinearLayout
        android:layout_width="match_parent"
        android:layout_height="match_parent"
        android:orientation="vertical"
        android:layout_margin="0dp">

        <LinearLayout
            android:layout_width="match_parent"
            android:layout_height="wrap_content"
            android:layout_weight="1"
            android:orientation="horizontal">

            <Button
                android:id="@+id/btnOne"
                android:layout_width="0dp"
                android:layout_height="match_parent"
                android:layout_margin="2dp"
                android:layout_weight="1"
                android:onClick="onDigit"
                android:text="@string/_1" />

            <Button
                android:id="@+id/btnTwo"
                android:layout_width="0dp"
                android:layout_height="match_parent"
                android:layout_margin="2dp"
                android:layout_weight="1"
                android:onClick="onDigit"
                android:text="@string/_2" />

            <Button
                android:id="@+id/btnThree"
                android:layout_width="0dp"
                android:layout_height="match_parent"
                android:layout_margin="2dp"
                android:layout_weight="1"
                android:onClick="onDigit"
                android:text="@string/_3" />

            <Button
                android:id="@+id/btnSubtract"
                android:layout_width="0dp"
                android:layout_height="match_parent"
                android:layout_margin="2dp"
                android:layout_weight="1"
                android:onClick="onOperator"
                android:text="@string/minus" />
        </LinearLayout>
        <LinearLayout
            android:layout_width="match_parent"
            android:layout_height="wrap_content"
            android:orientation="horizontal"
            android:layout_weight="1"
            >
            <Button
                android:id="@+id/btnFour"
                android:layout_width="0dp"
                android:layout_height="match_parent"
                android:layout_weight="1"
                android:layout_margin="2dp"
                android:onClick="onDigit"
                android:text="@string/_4"/>
            <Button
                android:id="@+id/btnFive"
                android:layout_width="0dp"
                android:layout_height="match_parent"
                android:layout_weight="1"
                android:layout_margin="2dp"
                android:onClick="onDigit"
                android:text="@string/_5"/>
            <Button
                android:id="@+id/btnSix"
                android:layout_width="0dp"
                android:layout_height="match_parent"
                android:layout_weight="1"
                android:layout_margin="2dp"
                android:onClick="onDigit"
                android:text="@string/_6"/>
            <Button
                android:id="@+id/btnMultiply"
                android:layout_width="0dp"
                android:layout_height="match_parent"
                android:layout_weight="1"
                android:layout_margin="2dp"
                android:onClick="onOperator"
                android:text="@string/multiply"/>
        </LinearLayout>
        <LinearLayout
            android:layout_width="match_parent"
            android:layout_height="wrap_content"
            android:orientation="horizontal"
            android:layout_weight="1"
            >
            <Button
                android:id="@+id/btnSeven"
                android:layout_width="0dp"
                android:layout_height="match_parent"
                android:layout_weight="1"
                android:layout_margin="2dp"
                android:onClick="onDigit"
                android:text="@string/_7"/>
            <Button
                android:id="@+id/btnEight"
                android:layout_width="0dp"
                android:layout_height="match_parent"
                android:layout_weight="1"
                android:layout_margin="2dp"
                android:onClick="onDigit"
                android:text="@string/_8"/>
            <Button
                android:id="@+id/btnNine"
                android:layout_width="0dp"
                android:layout_height="match_parent"
                android:layout_weight="1"
                android:layout_margin="2dp"
                android:onClick="onDigit"
                android:text="@string/_9"/>
            <Button
                android:id="@+id/btnDivide"
                android:layout_width="0dp"
                android:layout_height="match_parent"
                android:layout_weight="1"
                android:layout_margin="2dp"
                android:onClick="onOperator"
                android:text="@string/div"/>
        </LinearLayout>
        <LinearLayout
            android:layout_width="match_parent"
            android:layout_height="wrap_content"
            android:orientation="horizontal"
            android:layout_weight="1"
            >
            <Button
                android:id="@+id/btnDot"
                android:layout_width="0dp"
                android:layout_height="match_parent"
                android:layout_weight="1"
                android:layout_margin="2dp"
                android:onClick="onDecimalPoint"
                android:text="."/>
            <Button
                android:id="@+id/btnZero"
                android:layout_width="0dp"
                android:layout_height="match_parent"
                android:layout_weight="1"
                android:layout_margin="2dp"
                android:onClick="onDigit"
                android:text="0"/>
            <Button
                android:id="@+id/btnClr"
                android:layout_width="0dp"
                android:layout_height="match_parent"
                android:layout_weight="1"
                android:layout_margin="2dp"
                android:onClick="onClear"
                android:text="CLR"/>
            <Button
                android:id="@+id/btnAdd"
                android:layout_width="0dp"
                android:layout_height="match_parent"
                android:layout_weight="1"
                android:layout_margin="2dp"
                android:onClick="onOperator"
                android:text="+"/>
        </LinearLayout>
        <LinearLayout
            android:layout_width="match_parent"
            android:layout_height="wrap_content"
            android:orientation="horizontal"
            android:layout_weight="1"
            >
            <Button
                android:id="@+id/btnEqaul"
                android:layout_width="0dp"
                android:layout_height="match_parent"
                android:layout_weight="2"
                android:layout_margin="2dp"
                android:onClick="onEqaul"
                android:text="="/>
        </LinearLayout>

    </LinearLayout>


</LinearLayout>

MainActivity.kt

package com.example.mycalculator

import androidx.appcompat.app.AppCompatActivity
import android.os.Bundle
import android.view.View
import android.widget.Button
import android.widget.TextView
import android.widget.Toast
import java.lang.ArithmeticException

class MainActivity : AppCompatActivity() {

    private var tvInput: TextView? = null
    var lastNumeric : Boolean = false
    var lastDot : Boolean = false

    override fun onCreate(savedInstanceState: Bundle?) {
        super.onCreate(savedInstanceState)
        setContentView(R.layout.activity_main)

        tvInput = findViewById(R.id.tvInput)
    }

    fun onDigit(view:View){
        tvInput?.append((view as Button).text)
        lastNumeric = true
        Toast.makeText(this, "Button clicked", Toast.LENGTH_LONG).show()
    }

    fun onDecimalPoint(view:View){
        if(lastNumeric && !lastDot){
            tvInput?.append(".")
            lastNumeric = false
            lastDot = true
        }
    }

    fun onClear(view: View){
        tvInput?.text = ""
    }

    fun onOperator(view: View){
        tvInput?.text?.let {
            if (lastNumeric && !isOperatorAdded(it.toString())){
                tvInput?.append((view as Button).text)
                lastNumeric = false
                lastDot = false
            }
        }
    }

    fun onEqaul(view : View){
        if(lastNumeric){
            var tvValue = tvInput?.text.toString()
            var prefix = ""
            try{
                if(tvValue.startsWith("-")){
                    prefix = "-"
                    tvValue = tvValue.substring(1)
                }
                if(tvValue.contains("-")){
                    val splitValue = tvValue.split("-")
                    var one = splitValue[0]
                    var two = splitValue[1]

                    if(prefix.isNotEmpty()){
                        one = prefix + one
                    }

                    tvInput?.text = removeZeroAfterDot((one.toDouble() - two.toDouble()).toString())
                } else if(tvValue.contains("+")){
                    val splitValue = tvValue.split("+")
                    var one = splitValue[0]
                    var two = splitValue[1]

                    if(prefix.isNotEmpty()){
                        one = prefix + one
                    }

                    tvInput?.text = removeZeroAfterDot((one.toDouble() + two.toDouble()).toString())
                }else if(tvValue.contains("*")){
                    val splitValue = tvValue.split("*")
                    var one = splitValue[0]
                    var two = splitValue[1]

                    if(prefix.isNotEmpty()){
                        one = prefix + one
                    }

                    tvInput?.text = removeZeroAfterDot((one.toDouble() * two.toDouble()).toString())
                }else if(tvValue.contains("/")){
                    val splitValue = tvValue.split("/")
                    var one = splitValue[0]
                    var two = splitValue[1]

                    if(prefix.isNotEmpty()){
                        one = prefix + one
                    }

                    tvInput?.text = removeZeroAfterDot((one.toDouble() / two.toDouble()).toString())
                }
            }catch(e: ArithmeticException){
                e.printStackTrace()
            }
        }
    }

    private fun removeZeroAfterDot(result: String) : String{
        var value = result
        if(result.contains(".0"))
            value = result.substring(0, result.length-2)

        return value
    }


    private fun isOperatorAdded(value : String) : Boolean{
        return if(value.startsWith("-")){
            false
        }else{
            value.contains("/") || value.contains("*") || value.contains("+") || value.contains("-")
        }
    }

}

Sequential Access와 Random Access

메모리에서 특정 레코드를 찾기 위해 디스크에 접근할 때

레코드를 찾는 순서에 따라 디스크 접근 방식을 Sequential Access와 Random Access로 나눌 수 있다.

그림에서 알 수 있듯이 Sequential access는 데이터에 대해 저장된 순서대로 접근하는 방식을 의미하고

Random access는 데이터에 대해서 랜덤하게 접근하는 방식을 의미한다.

이러한 Access방식에 대해 실생활에서 은행을 예로 들어 생각해보자.

은행에는 많은 사람들이 방문한다.

방문하는 사람들은 계좌번호 순서대로 줄을 서서 입장하지 않는다.

무작위의 계좌번호를 가진 손님들이 Random Access 하는 방식이다.

이제 Sequential Access 방식을 생각해보자.

은행이 문을 닫고 은행원은 손님들의 계좌번호를 Sorting 한 상태에서 순서대로 볼 것이다. (아마도)

이 방식이 Sequential Access 방식이다.

즉 일상생활에서 데이터 레코드에 접근할 때 방식은

Sequential Access, Random Access 나뉘는 것이다.

이러한 Access 방식을 생가하며 화일의 구조를 만들어야 한다.

Sequential file과 Index file

화일은 크게 두가지 구조로 나뉜다.

sequential file과 Index file이다. 

순차화일과 색인 화일로 부르기도 하는데 이제

두 화일을 순차화일과 인덱스 화일로 칭한다.

화일 처리의 주된 목적은 메모리에서 디스크 Access를 줄여서 io시간을 줄이는 것이다.

https://dingcoding.tistory.com/318?category=1035429 

위에서 설명한 두가지 Access 방법에 따라 

Sequential file과 Index file의 장단점이 구분된다.

결론부터 말하면 Sequential file은 Sequential Access에 유리하고

Index file은 Random Access에 유리하다.

이제 그 이유를 살펴보자

순차화일

순차화일은 데이터가 순차적으로 저장되어 있기 때문에

Sequential Access를 많이 할 경우 유리하다.

Blocking Factor(메모리에서 디스크의 블록을 읽는 단위)에 따라 데이터를 읽는 양은 다르겠지만,

Sequential Access를 할 때

5번 21번 학생의 데이터가 필요한 상황이라 가정해보자.

그리고 쉽게 설명하기 위해서 한 번의 디스크 Access를 할때 학생 3명의 데이터를 읽을 수 있다 가정하자.

그렇다면 순차적으로 5번, 21번, 105번의 데이터가 필요한 경우에는

5번 학생의 데이터를 읽기 위해 디스크 Access를 한 이후에

5번, 21번, 105번 데이터를 읽어온다 (학생 3명의 데이터를 읽어올 수 있다고 가정했으므로)

메모리에는 5번 21번의 데이터가 존재하기 때문에 21번 학생의 데이터를 얻기 위해서

다시 디스크에 접근할 필요가 없다.

즉 데이터를 순차적으로 요청할 때 순차화일의 경우에는 Disk Access를 적게 할 수 있다는 장점이 있다.

하지만 Random Access를 할 경우 비효율적이 된다.

이번에는 5번, 700번, 105번 데이터를 읽는다 생각해보자. (이번에도 한번의 Disk Access에 3명의 데이터를 읽어온다고 가정하자)

Disk Access 1회:

5번 데이터를 읽을 때

메모리 버퍼에는 5, 21, 105번이 저장된다.

Disk Access 2회:

메모리 버퍼에 700번 데이터가 없기 때문에

다시 디스크에 접근하고 700번, x, y 데이터를 읽어오게 된다.

Disk Access 3회:

메모리 버퍼에 105번 데이터가 없기 때문에

다시 디스크에 접근하고 데이터를 읽어오게 된다.

이 때 데이터를 찾을 때마다 순차화일에서 이진탐색을 해야한다.

디스크 위에서 이진탐색을 시행하기 때문에 여러번 디스크에 접근해야 하는 것이다.

하지만 이런식으로 데이터를 처리하면 cpu의 관점에서 너무 느려진다.

한번 디스크에 접근하는데 10ms 정도 소요되기 때문이다.

그리고 더불어 다른 문제점으로 순차화일은 데이터를 갱신할 때 비용이 많이 든다.

(그 이유는 위의 다른 게시물 링크에서 설명한다)

Random Access 할 때도 디스크 Access 를 줄이는 방법이 필요하다.

인덱스 화일

인덱스 화일에서는 순차화일과 달리 데이터를 key값에 따라 순서대로 저장하지 않는다.

데이터가 입력되면 입력되는 그 순서대로 기록할 뿐이다.

하지만 해당 학번이 디스크 어느 위치에 존재하는지 나타내주는

인덱스 테이블을 메인 메모리에 두고 사용한다.

이럴 경우 메인 메모리에서 원하는 key(학번)을 찾아서 바로 디스크에 접근할 수 있다.

인덱스를 메인메모리에 저장할 수 있는 이유는

단순 인덱스 테이블을 메인 메모리에 저장하는 데에는 많은 용량이 필요하지 않기 때문에 가능하다.

그리고 추후 설명하겠지만 실제로 인덱스 테이블은 배열구조가 아닌

트리 구조로 이루어진다.

트리 자료구조로 인덱스 구조를 만들어 메모리에 저장하고 디스크에 접근해야 하는 일이 생기면

메모리 내의 인덱스에서 key값을 찾아 접근해야 하는 디스크의 주소를 알아내고 디스크에는 한 번 Access 하게 되는 것이다.

순차화일 처럼 키값을 찾기 위해 이진탐색을 하는 것은 동일하지만

순차화일은 디스크 상에서 이진탐색을 해야하는데

인덱스 화일은 메모리 상에서 이진탐색을 진행하기 때문에 

인덱스 화일이 Random Access를 할 때 유리하다.

하지만 인덱스화일은 Sequential Access를 할 때 불리하다.

순차화일은 데이터가 순차적으로 저장되어 있는 걸 읽어오기 때문에

순차적으로 데이터를 요청할 때 Disk Access를 적게 할 수 있는데 비해

인덱스화일은 실제 데이터가 무작위로 섞여 있기 때문에

순차적인 데이터 요청이 오더라도 계속 Disk Access를 하여 데이터를 읽어와야 할 것이다.

이처럼 순차 화일과 인덱스 화일은

Disk Access 방식에 따라 장단점이 존재한다.

하지만 이러한 두 화일의 장점을 살려 만든 B+ 트리 구조의 화일도 존재한다.

재귀란

int factorial(int n){
	if (n==1) return 1
    return n * factorial(n-1);
}

재귀란 특정 함수나 개체를 설명할 때

그 함수나 개체를 바탕으로 설명하는 것을 의미한다.

특정 문제에 대해서 재귀를 이용하면 단순 반복문으로 해결하기 어려운 문제를 쉽고 간결하게 해결할 수 있다.

단 재귀를 이용해서 문제를 해결할 때는

stack Overflow가 발생하는 것을 조심해야 한다.

프로그램이 실행될 때 프로그램은

메모리에 정보를 저장하고 이용하는데 이 때 메모리의 구조는

크게 코드 영역, 데이터 영역, 힙 영역, 스택 영역으로 나뉜다.

재귀를 이용할 때 스택영역이 중요하다.

Activation Record

함수가 실행될 때 스택 영역에 activation record가 쌓인다.

activation record는 특정 함수를 실행하기 위해서 기록해두어야 하는 데이터를 의미한다.

함수 내에서 또 다른 함수를 실행하는 경우가 많다.

이러한 경우 A 함수를 실행하는 중에 B 함수가 실행 되면 다음과 같은 과정이 진행된다.

A 함수를 실행했던 데이터를 메모리의 call stack에  activation record를 기록해둔다.

B 함수의 실행이 끝나면 A 함수가 실행되던 정보를 불러오기 위해 call stack에 저장된 activation record를 불러와서

다시 A 함수를 실행할 수 있다.

즉 특정 함수를 실행할 때 그 정보를 call stack의 activation record에 기록하는 것이다.

그런데 프로그램이 사용하는 메모리는 무한한 자원이 아니다.

즉 스택 영역도 한정된 자원이다.

이 말은 함수를 재귀적으로 무한히 호출하다보면 activation record가 무한히 생성되고

이는 프로그램이 사용할 수 있는 call stack의 범위를 넘어서게 된다.

이러면 Stack Overflow 현상이 발생하는 것이다!

다만 헷갈리지 말아야할 점은 함수가 재귀적으로 무한히 실행되는 것은

activation record가 계속 쌓여서 문제가 발생하지만,

재귀적으로 실행되지 않고 일반적인 함수가 계속해서 실행되는 것은 Stack Overflow가 발생하지 않는다.

왜냐하면 함수의 실행이 끝나면 call stack에 저장된 activation record도 메모리에서 지워져서

계속 쌓이지 않기 때문이다.

그래서 base condition, 기저사례를 잘 설정해서

재귀함수를 실행하면 함수가 stack Overflow가 발생하지 않도록

잘 설계하는 것이 중요하다.

stack Overflow 발생 가능

int sum(int n){
	if (n==1) return 1
    return sum(n-1) + n;
}

위 경우 n이 엄청 커진다면 activation record가 계속 기록하여 stack overflow가 발생할 수 있다.

stack Overflow 발생 안함

while(1){
	int sum(int n, int m){
		return n + m;
	}
}

하지만 이 경우에는 함수를 실행하고 activation record를 기록하고 함수가 끝나면 바로 지우고

기록하고 지우고를 반복하여 함수는 무한히 실행하지만 실제 stack에 activation record가 무한히 쌓이는 상황은 아니다.

activation record는 몇개까지 쌓을 수 있을까?

간단한 더하기 함수를 재귀적으로 구현했을 때

함수를 4000번 정도 실행하면 Stack Overflow가 발생하는 것을 확인할 수 있었다.

이 말은 만약 재귀적으로 구현할 때 함수를 4000번 이상 실행해야 한다면 

해당 문제를 재귀적으로 해결할 수 없다는 것을 의미한다.

이때는 반복문을 이용해서 해결해야 할 것이다.

Heap Overflow?

본문과는 크게 관련없지만, 

메모리 구조에서 코드와 데이터 영역은 프로그램을 실행할 때 한번 메모리에 할당되고 크기가 변하지 않기 때문에 정적이다.

하지만 힙 영역과 스택 영역은 프로그램이 동작하는 과정에서 동적으로 이용된다.

이때 메모리가 동적으로 이용된다는 말은 프로그램이 진행하면서 계속 메모리를 일정하게 이용하는 것이 아닌,

프로그램의 진행 상황에 따라 메모리의 사용량이 변화하는 것을 의미한다.

스택을 보면 함수를 실행할 때마다 Activation Record를 기록하기 위해 메모리를 추가적으로 사용한다.

힙 영역은 프로그램 코드에서 메모리를 동적으로 할당할 때 사용된다.

주로 C, C++계열 언어에서 포인터와 new 키워드를 활용하여 힙 메모리를 할당받아 사용하는 것이 예시이다.

그렇다면 Heap Overflow도 존재하지 않을까 하는 의문이 들었다.

이에 대해 찾아보니 프로그래머가 메모리를 계속 동적으로 하고 반환해주지 않는다면

stack과 마찬가지로 heap도 overflow가 발생한다고 한다.