나눗셈

정수 두 개를 나누었을 때, 몫과 나머지를 구할 수 있다.

//( A/B = Q\space remainder \space R //)

이때 A는 피제수(dividend)라고 부른다.

B는 제수(divisor) 라고 부른다.

Q는 몫(quotient)라고 부른다.

R는 나머지(remainder)라고 부른다.

모듈러(Modulo) 연산

나머지 연산은 modulo라고 하며 mod라고 나타낸다.

//( 7\space mod\space 2 = 1 //) 이다. 왜냐면 7을 2로 나누면 몫이 3이고 나머지가 1이므로, 이 나머지 값이 모듈러 연산의 결과값이 된다.

그렇다면 //( -5\space mod\space 3 //) 과 같은 경우는 어떻게 될까?

이러한 경우는 모듈러 연산의 특징을 이용해서 값을 구할 수 있다.

모듈러 연산은 피연산자의 값을 주기로 같은 결과값을 갖는 주기성을 띤다. 따라서 다음과 같은 관계가 성립한다.

//( -5\space mod\space 3 = -2\space mod\space 3 = 1\space mod\space 3 = 4\space mod\space3 ...//)

즉 첫번째 피연산자에 두번째 피연산자의 정수배의 값을 더해도 같은 값이 나오는 것을 이용하여 문제를 해결할 수 있다.

다시말해 -5에 3이나 6이나 9 등의 //(3*K//)의 값을 더해도(단 //(K//)는 정수) 결과값은 같다는 것이다.

모듈러 합동(Congruence Modulo)

이제 모듈러 합동(Congruence Modulo)에 대해 알아보자.

다음과 같은 수식이 있다.

//(A \equiv B(modC)//)

이를 A는 모듈러 C에 대해서 B와 합동이다 라고 읽는다. (A is congruent to B modulo C)

이는 다르게 말하면, //( A\space mod\space C = B\space mod\space C //)라는 뜻이다.

위 수식이 성립한다면, 또한 //(A-B//)는 //(C//)의 정수배라고 볼 수 있다.

모듈러 역원(Modular inverse)

역원(inverse)

역원에 대해 한번 다시 알아보자. 어떤 수와 그 수의 역원을 곱하면 1이 된다.

숫자 //(A//)의 역원은 //(1/A//)이다, 왜냐면 //(A * 1/A = 1//)이기 때문이다.

0보다 큰 실수는 역원을 갖는다.

그리고 //(A//)의 역원과 곱셈을 하는 것은 //(A//)로 나누는 것과 같다.

모듈러 역원(Modular inverse)

모듈러 역원의 활용

프로그래밍을 할 때, //(A//)를 구하는 과정에서 //(A//)가 int나 long long 범위를 벗어나서, 온전한 //(A//)값을 구할 수 없고, //( A \mod C //) 값만 구할 수 있는 경우

위의 성질을 활용하면 간편하다.

//(A//)값과 //(B^{-1}//)를 각각 구해서 모듈러를 취한 뒤, 곱한 뒤 다시 모듈러를 취하면 되기 때문이다.

그러면 //(B^{-1}//)를 어떻게 구하느냐면, 페르마의 소정리를 이용하면 된다.

-------------------------

[참고]

https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/e/congruence-relation

https://www.acmicpc.net/blog/view/29

블로그에 수학 수식을 입력하는 방법은 다양합니다. 간단하게는 다른 수학 수식을 그려주는 곳에서 (e.g 한컴오피스) 수식을 그린 뒤, 해당 수식을 캡쳐해서 이미지 형태로 올릴 수도 있고, 아니면 직접 수식 모양대로 svg등으로 한땀 한땀 그릴 수도 있습니다. 아니면 흔히 다른 사람들이 많이 쓰는 라이브러리인 MathJax 등을 사용할 수도 있습니다. 저는 이번에 KaTeX라고 하는 라이브러리를 이용해서 블로그에 수식을 입력해보도록 하겠습니다.

https://khan.github.io/KaTeX/

KaTeX의 공식 홈페이지입니다. MathJax 보다 랜더링 속도가 빠르다는 것을 강점으로 홍보하고 있습니다.

참고로 LaTeX는 TeX라고 하는 조판 프로그램을 쉽게 사용하기 위해 만든 매크로입니다. LaTeX라는 것을 이용해서 특정한 의미를 갖는 메타캐릭터들과 텍스트들을 조합해서 PDF나 다른 문서들을 만들어낼 수 있습니다. 그 LaTeX에서 사용하는 매크로 중에서 수식을 그리는 매크로도 있는데, 이 KaTeX는 LaTeX의 이름을 바꾸어서 네이밍을 한 것 같습니다.

LaTeX는 자바스크립트 API를 지원하며, 다양한 방식으로 수식을 입력할 수 있는데, 여기서는 자바스크립트 API를 최대한 호출하지 않도록 간단하게 입력할 수 있는 Auto-Render Extension을 이용하겠습니다.

티스토리 관리자 페이지에서 '스킨 편집' - 'html 편집'을 누릅니다. 그리고 </head> 바로 윗 부분에 아래와 같이 코드 스니펫을 입력해줍니다.

아래 사진에는 Auto-Render Extension을 위한 값을 입력하지 않고 기본 katex라이브러리만 불러오는 방식으로 되어있지만, Auto-Render Exntension을 위해서는 아래 코드스니펫을 복사 밑 붙여넣기 해 줍니다.

CDN을 사용하지 않고, js파일과 css파일을 직접 본인의 서버에 올려서 사용하려고 한다면, prism.js 적용하는 것과 유사하게 파일업로드 후 상대경로를 지정해주면 됩니다.

 

	<!-- KaTex Start -->
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.9.0/katex.min.css" integrity="sha384-TEMocfGvRuD1rIAacqrknm5BQZ7W7uWitoih+jMNFXQIbNl16bO8OZmylH/Vi/Ei" crossorigin="anonymous">
<script src="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.9.0/katex.min.js" integrity="sha384-jmxIlussZWB7qCuB+PgKG1uLjjxbVVIayPJwi6cG6Zb4YKq0JIw+OMnkkEC7kYCq" crossorigin="anonymous"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.9.0/contrib/auto-render.min.js" integrity="sha384-IiI65aU9ZYub2MY9zhtKd1H2ps7xxf+eb2YFG9lX6uRqpXCvBTOidPRCXCrQ++Uc" crossorigin="anonymous"></script>
<script>
	document.addEventListener("DOMContentLoaded", function() {
    renderMathInElement(document.body, {
			delimiters: [
				{left: "$$", right: "$$", display: true},
				{left: "//[", right: "//]", display: true},
				{left: "//(", right: "//)", display: false}
			]
		});
	});
</script>
	<!-- KaTex End -->

스니펫은 다음 링크에서도 확인할 수 있습니다.

https://github.com/Khan/KaTeX/blob/master/contrib/auto-render/README.md

그리고 테스트용 글을 한번 써 봅니다. 해당 API 문서를 참조해보면, 기본값으로 수식을 나타내는 구분자(delimiter)는 기본 설정 값으로 3개가 주어진다고 합니다.

$$ 수식 $$

\\[ 수식 \\]

\\( 수식 \\)

이러한 구분자의 값은 renderMathInElement 함수의 두번째 인자의 옵션에 설정하여 원하는 값으로 바꿀 수 있다고 합니다.

그리고 처음 첫번재 두번재 구분자는 display가 true값으로, 해당 구분자로 입력을 하면 해당 수식이 줄의 가운대 정렬이 되어서 displayMode로 크게 보여집니다. 하지만 마지막 구분자를 이용하면 displayMode가 false이므로 inline 모드로 입력이 되어 수식이 본문과 어우러지게 입력됩니다.

그리고 한글 자판을 사용하는 시스템에서 백슬래시 값을 입력하면 Won 기호로 인식되어서 두번째 세번째 구분자가 제대로 인식되지 않는 경우가 많습니다. 따라서 저 같은 경우에는 이 기본값의 구분자를 \ 대신 /으로 치환해서 사용합니다.

아래 그림은 $$ 구분자로 수식을 입력한 모습입니다.

원하는 수식으로 잘 랜더링 되었습니다.

$$A \equiv B(modC)$$

그리고 KaTeX에서 지원하는 구문들에 대한 레퍼런스 문서의 링크는 다음과 같습니다.

https://khan.github.io/KaTeX/function-support.html

KaTeX를 이용해서 구문을 작성할 시 참조하면 좋습니다.

백준저지 1013번 문제 Contact과 2671번 문제 잠수함 식별은 문제가 똑같다.

특정한 문자열 패턴에 일치하는지 확인하는 문제이다. 문자열 패턴이 정규표현식(Regular Expression) 형태이므로 DFA(Deterministic Finite Automata)를 그려서 O(n)에 문제를 해결할 수 있다.

주어진 패턴이 (100+1+|01)+인데, DFA를 바로 그리기에는 어려우므로 NFA(Non-deterministic Finite Automata)를 먼저 그린다. 이후 DFA로 변환해보도록 한다.

아래 그림은 NFA를 그린 것이다. Initial State는 a이고, Final State는 e, g이다.

이후 DFA로 변환하면 다음과 같다. 똑같이 Initial state는 a이고 Final State는 g, e, {b,e} 이다.

state를 빨간샛 숫자에 맞추어 번호를 부여한 뒤 구현하면 다음과 같은 코드가 나타난다.

1013번 Contact 문제 풀이 코드이다.

 

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

#define FAIL 9
const int tr[10][2] = {
    {5, 1}, //0
    {2, FAIL}, //1
    {3, FAIL}, //2
    {3, 4}, //3
    {5, 7}, //4
    {FAIL, 6},//5
    {5, 1},//6
    {8, 7},//7
    {3, 6},//8
    {FAIL, FAIL}//9
};

bool chk(string &seq) {
    int state = 0;
    for (size_t i=0; i < seq.size(); i++) {
        char ch = seq[i] - '0';
        state = tr[state][ch];
    }
    return state == 4 or state == 6 or state == 7;
}
int main() {
    int t;
    cin >> t;
    while(t--) {
        string seq;
        cin >> seq;
        bool ans = chk(seq);
        cout << (ans ? "YES" : "NO") << '\n';
        
    }
	return 0;
}

잠수함 식별 문제도 거의 동일한 코드로 풀이가 가능하다. 하지만 2671번 잠수함 문제는 C++에서 제공하는 정규표현식 라이브러리를 이용해서 풀이해보겠다.

 

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

int main() {
    regex re("(100+1+|01)+");    
    cmatch m;
    string seq;
    cin >> seq;
    bool ans = regex_match(seq.c_str(), m, re);
    cout << (ans ? "SUBMARINE" : "NOISE") << '\n';

	return 0;
}

위와 같은 간단한 코드로 쉽게 정규표현식에 일치하는지 확인할 수 있다.

정규표현식이 정확한지는 다음 사이트에서 쉽게 태스트 해 볼 수 있다.

https://regexr.com/

한국정보올림피아드(정올) 1996년도 초등부 문제 풀이 포스팅이다.

문제들은 백준저지에서 참고하고 풀이했다.

https://www.acmicpc.net/category/detail/403

1번 단지번호 붙이기 문제이다.

https://www.acmicpc.net/problem/2667 (백준 2667번)

dfs로 풀면 간단하게 풀 수 있는 문제이다.

 

#include <stdio.h>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

vector<vector<char> > matrix;
int N; //length of matrix edge
int num_of_danji;
int num_of_1;
int x,y;
vector<int> num_of_houses;
void dump_matrix();
bool find_danji();
bool spread(int xpos, int ypos);
bool comp(int a, int b) {
    return (a > b);
};
int main() {
	char temp;
	scanf("%d\n", &N);
	
	matrix.assign(N, vector<char>(N, '0'));
	for (int i=0; i<N; i++) {
		for (int j=0; j<N; j++) {
			scanf("%c", &temp);
			if (temp == '1') {
				num_of_1++;
			}
			matrix[i][j] = temp;
		}
		scanf("\n");
	}

	while (num_of_1 > 0) {
		// dump_matrix();
		find_danji();
		int temp = num_of_1;
		// cout << "x:" << x << endl << "y:" << y << endl;
		spread(x, y);
		num_of_danji++;
		num_of_houses.push_back(temp - num_of_1);
		// dump_matrix();
	}
	
	cout << num_of_danji << endl;
	sort(num_of_houses.begin(), num_of_houses.end());
	for (int i=0; i< num_of_houses.size(); i++) {
		cout << num_of_houses[i] << endl;;
	}
	
}

bool find_danji() {
	for (int i=0; i<N; i++) {
		for (int j=0;j<N; j++) {
			if (matrix[i][j] == '1') {
				x = i;
				y = j;
				return true;
			}
		}
	}
	x = -1;
	y = -1;
	return false;
}
bool spread(int xpos, int ypos) {
	// cout << "spread(" << xpos << "," << ypos << ")" << endl;
	if (xpos >= 0 && xpos < N && ypos >= 0 && ypos < N) {
		// cout << "flag 1"<< endl;
		if (matrix[xpos][ypos] == '1') {
			// cout << "flag 2"<< endl;
			matrix[xpos][ypos] = '0';
			num_of_1--;
			
			return spread(xpos-1, ypos) || spread(xpos, ypos-1) || spread(xpos+1, ypos) || spread(xpos, ypos+1);
		} else {
			return false;
		}
	} else {
		return false;
	}
}
void dump_matrix() {
	for(int i=0; i<N; i++) {
		for(int j=0; j<N; j++) {
			printf("%c", matrix[i][j]);
		}
		putchar('\n');
	}
}

2번 숫자고르기 문제이다.

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

다음 특징들에 착안해서 알고리즘을 고안했다.

위쪽의 그룹의 숫자는 중복이 없고 인덱스값과 같다.

아래쪽 그룹의 숫자는 중복이 있다. 따라서 없는 숫자도 있다.

위쪽 그룹 숫자를 U집합 이라고 하고 아래쪽 집합 숫자를 D집합이라고 하자.

아래쪽 그룹에 없는 숫자가 위쪽 그룹에서 지정될 수 없다는 점을 이용해서 다음 알고리즘을 고안했다.

1. 두번째 줄의 숫자 집합을 구한다. 이를 A라고 한다.

2. A의 원소를 인덱스(첫번째 줄의 숫자기준)로 하는 숫자 집합 B를 구한다.

3. A집합과 B집합이 일치하면 이(A집합 혹은 B집합)를 리턴한다. 그렇지 않으면 다음 단계로 간다.

4. B집합을 A집합으로 두고, B집합은 초기화한다. A집합을 기준으로 스텝 2를 다시 시도한 뒤 3번으로 간다.

백준에 나타난 예시에서 해당 알고리즘을 진행하면 다음과 같이 나타난다.

첫번째 스탭에서 집합 A는 다음과 같이 나타난다.

A = { 1, 3, 4, 5, 6 }

아래쪽 집합의 숫자들을 중복을 제거한 집합의 결과이다.

이때 이 A집합은 U집합에서 고른녀석들이라고 볼 수 있다.

알고리즘 두번째 스탭에서 집합 B를 구한다.

집합 B는 다음 항목들의 집합이다.

D[1], D[3], D[4], D[5], D[6]

B = { 3, 1, 5, 5, 6 } = { 1, 3, 5, 6 }

이때 이 B집합은 D집합에서 A집합에 대응되는 녀석이라고 볼 수 있다.

세번재 스탭에서 A와 B집합을 비교했을 때,  B집합이 크기가 더 작으므로 B집합을 A집합에 대입하고 다시 이어나간다.

A집합은 다시 다음값이 된다.(U집합에서 고른녀석들)

A = { 1, 3, 5, 6 }

B = { 3, 1, 5, 4 } = { 1, 3, 4, 5 }

다시 비교했을 때 맞지 않으므로 A집합에 다시 B 집합을 대응한다.

A = { 1, 3, 4, 5 }

B = { 3, 1, 5, 5 } = { 1, 3, 5 }

일치하지 않으므로 다시 대응한다.

A = { 1, 3, 5 }

B = { 1, 3, 5 }

일치하므로 정답을 리턴한다.

 

#include <stdio.h>
#include <vector>
#include <iostream>
#include <set>

using namespace std;

vector<int> arr; //기본애들
vector<int> elite; //뽑힌애들
set<int> set1, set2;
int N;

void arr_dump();
void set_dump(set<int> a);
bool is_equal(set<int>, set<int>);
int main() {
	
	int temp;
	scanf("%d\n", &N);
	arr.reserve(N+1);
	arr.push_back(0000);
	for (int i=0; i<N; i++) {
		scanf("%d\n", &temp);
		arr.push_back(temp);
	}
	
	// arr_dump();
	for(int i=1; i< arr.size(); i++) {
		set1.insert(arr[i]);
	}
	// cout << "set1 : ";
	// set_dump(set1);
	for (set<int>::iterator pos = set1.begin(); pos != set1.end(); pos++) {
		set2.insert(arr[*pos]);
	}
	// cout << "set2 : ";
	// set_dump(set2);
	// cout << "is_equal " << is_equal(set1, set2) << endl;
	

	do {
		set1 = set2;
		set2.clear();
		for (set<int>::iterator pos = set1.begin(); pos != set1.end(); pos++) {
			set2.insert(arr[*pos]);
		}
		
	} while(!is_equal(set1, set2));
	// cout << "fin";
	// set_dump(set1);
	printf("%lu", set1.size());
	set_dump(set1);
}

void arr_dump() {
	for (int i=1; i<arr.size(); i++) {
		printf("%d ", arr[i]);
	}
}
void set_dump(set<int> a) {
	cout << endl;
	for (set<int>::iterator IterPos = a.begin(); IterPos != a.end(); IterPos++) {
		cout << *IterPos << endl;
	}
}
bool is_equal(set<int> a, set<int> b) {
	if (a.size() != b.size()) {
		return false;
	}
	set<int>::iterator ai, bi;
	ai = a.begin();
	bi = b.begin();
	while (ai != a.end()) {
		if (*ai != *bi) {
			return false;
		}
		ai++;
		bi++;
	}
	return true;
}

3번 직사각형 네개의 합집합의 면적 구하기 문제이다.

https://www.acmicpc.net/problem/2669 (백준 2669번)

N값이 크지 않으므로 좌표평면을 만들어서 죄다 더해버리면 된다.

 

#include <vector>
#include <iostream>
#include <stdio.h>

using namespace std;

int map[100][100] = {0,};
int rect[4][4];

void dump();
int answer();
int main() {
	for (int i=0; i<4;i++) {
		scanf("%d %d %d %d\n", &rect[i][0], &rect[i][1], &rect[i][2], &rect[i][3]);
	}
	for (int i=0; i<4;i++) {
		for (int x=rect[i][0]; x < rect[i][2]; x++) {
			for(int y=rect[i][1]; y < rect[i][3]; y++) {
				map[x][y]++;
			}
		}
	}
	// dump();
	cout << answer() << endl;
}
int answer() {
	int count = 0;
	for(int i=0;i<100;i++) {
		for (int j=0;j<100;j++) {
			if (map[i][j]) {
				count++;
			}
		}
	}
	return count;
}
void dump() {
	//rect
	// for(int i=0;i<4;i++) {
	// 	for(int j=0;j<4;j++) {
	// 		printf("%d\t", rect[i][j]);
	// 	}
	// }
	
	for(int i=99;i>=0;i--) {
		for(int j=99;j>=0;j--) {
			printf("%d ", map[j][i]);
		}
		putchar('\n');
	}
}

한국정보올림피아드(정올) 2013년도 초등부 문제 풀이 포스팅입니다.

문제들은 백준저지에서 참고하고 풀이했습니다.

https://www.acmicpc.net/category/detail/1075

총 4문제가 있습니다.

1번 올림픽 문제입니다. (백준 8979번)

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

단순 계산으로 풀 수 있다. 비교 연산자를 재정의해서 정렬한 뒤, 중복 순위의 경우에만 체크를 해주면 된다.

 

#include <bits/stdc++.h>
using namespace std;
struct data {
    int num, gold, silver, bronze;
    
    bool operator < (const data& rhs) const {
        return gold != rhs.gold ? gold > rhs.gold : (silver != rhs.silver ? silver > rhs.silver : bronze > rhs.bronze);
    }
    bool operator == (const data& rhs) const {
        return gold == rhs.gold && silver == rhs.silver && bronze == rhs.bronze;
    }
};
vector<data> arr;
int main() {
    int n, k;
    cin >> n >> k;
    arr.reserve(n);
    for (int i=0; i < n; i++) {
        data tmp;
        scanf("%d %d %d %d\n", &tmp.num, &tmp.gold, &tmp.silver, &tmp.bronze);
        arr.push_back(tmp);
    }
    sort(arr.begin(), arr.end());
    
    int rank = 0;
    int accu = 1;
    data prev;
    prev.gold = prev.silver = prev.bronze = -1;
    //dump
    for (int i=0; i < n; i++) {
        auto& a = arr[i];
        if ( (prev == a) == false) {
            rank += accu;
            accu = 1;
        } else {
            accu++;
        }
        // printf("rank %d - ", rank);
        if (a.num == k) {
            cout << rank << '\n';
            return 0;
        }
        
        prev = a;
        // printf("(%d) %d, %d, %d\n", a.num, a.gold, a.silver, a.bronze);
    }
    //dump
}

2번 택배 문제입니다.

https://www.acmicpc.net/problem/8980 (백준 8980번)

그리디로 풀 수 있다. 그리디도 그리딘데, 어떤식으로 그리디를 적용시킬지가 중요하다. 일단 배달 구간이 가장 짧은놈들 순서대로 sorting한다. 배달 구간이 짧을수록 트럭에서 공간을 점유하는 시간이 작아지므로 그렇게 하는 것이다.    

그리고 배달구간이 짧은놈 순서대로 트럭에 최대한 집어넣으면 정답이 된다. 이것을 어떻게 구현하느냐에서 많이 해맸는데, 궂이 시간순대로 트럭이 이동하는 방식으로 시뮬레이션을 하지 않더라도 짧은 구간부터, 구간별 트럭에 적제된 화물양을 저장해놓았다가 최대한 적재시키는 식으로 정답을 구하면 쉽게 풀이가 된다.

 

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

typedef pair<int, int> pii; //src, dst
struct Order {
    int src, dst, size;
};

Order orders[10001];

bool cmp(const struct Order& lhs, const struct Order& rhs) {
    if (lhs.dst != rhs.dst) return lhs.dst < rhs.dst;
    return lhs.src < rhs.src;
}
int loaded[2001]; //해당 위치에 있을 때, 트럭에 차있는 양
int main() {
    int ans = 0;
    int n, c, m;
    cin >> n >> c >> m;
    for (int i=0; i < m; i++) {
        scanf("%d %d %d", &orders[i].src, &orders[i].dst, &orders[i].size);
        
    }
    
    sort(orders, orders + m, cmp);
    for (int i=0; i< m; i++) {
        auto& order = orders[i];
        int already_loaded_amount = 0;
        for (int pos = order.src; pos < order.dst; pos++) { //구간을 돌면서 가장 많이 적제된 양을 찾는다.
            if (loaded[pos] > already_loaded_amount) {
                already_loaded_amount = loaded[pos];   
            }
        }
        int can_be_more_load_amt = min(order.size, c - already_loaded_amount); //더 적재할 양을 고른다.
        for (int pos = order.src; pos < order.dst; pos++) { //구간에 적재 시킨다.
            loaded[pos] += can_be_more_load_amt;
        }
        ans += can_be_more_load_amt;
    }    
    cout << ans <<'\n';
    return 0;
}

3번 입력숫자 문제입니다.

https://www.acmicpc.net/problem/8981 (백준 8981번)

비슷한 로직으로 하면 역연산이 된다. 이전 값 만큼 offset을 앞으로 전진시키고, 해당 위치에 다음 받은 값을 쓴다. 만약 거기 이미 값이 있다면 값이 없을 때 까지 앞으로 전진하면 된다.

 

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

int arr[30];
int input[30];
int ptr;
int val;
int n;
void search() {
    while(arr[ptr]) {
        ptr++;
        ptr %= n;
    }
}
int main() {
    cin >> n;
    cin >> val;
    arr[ptr] = val;
    for (int i=1; i < n; i++) {
        ptr += val;
        ptr %= n;
        search();
        cin >> input[i];
        arr[ptr] = val = input[i];
    }
    
    cout << n << endl;
    for (int i=0; i < n; i++) {
        cout << arr[i] << ' ';
    }
    cout << '\n';
	return 0;
}

----------------------------------------------------------------------------------------

- 이 글은 2020-01-08에 마지막으로 수정되었습니다.

- 글 상에 오류나 틀린 내용이 있을 수 있습니다.

- 잘못된 내용에 대한 신고나, 피드백을 주시고자 한다면 댓글을 달아주시면 반영하도록 하겠습니다.

----------------------------------------------------------------------------------------

개발을 시작하면서 접하기 쉬운 단어 중 햇갈리기 쉬운 API, ABI, 라이브러리, 프레임워크의 뜻을 알기쉽게 한번 설명해보는 포스팅이다.

계속 개발을 진행하다 보면 이런 용어들에 대한 대략적인 의미는 감이 잡히지만 정확한 뜻을 알거나 남에게 개념을 설명하기에는 햇갈릴 수 있다. 이번 포스팅을 계기로 한번 정리해보자.

라이브러리

일단 첫번째로 라이브러리이다.

컴퓨팅에서 라이브러리(Library)의 위키백과에서의 정의는 다음과 같다.

https://ko.wikipedia.org/wiki/라이브러리_(컴퓨팅)

소프트웨어를 개발할 때, 컴퓨터 프로그램이 사용하는 비휘발성 자원의 모임이다. 구성 데이터, 문서, 도움말 자료, 메시지 틀, 미리 작성된 코드, 서브루틴(함수), 클래스, 값, 자료형 사양 등을 포함할 수 있다.

예를 들어서, 누군가가 이전 C++포스팅에서 언급한 big_integer 클래스를 만들었다고 가정해보자. 아주 잘 만들어서 버그도 거의 없고, 정의된 함수만 잘 호출하면 잘 동작한다고 하자. 이 big_integer 클래스를 만든 사람이, 이 클래스를 혼자서 쓰기 아까워서 남들도 쉽게 사용할 수 있도록 공개를 해서 남들도 사용할 수 있도록 하되, 소스코드는 공개를 하고 싶지 않다면 어떻게 할까?

일반적으로 다음과 같은 절차를 밟는다. 클래스의 멤버변수와 멤버 함수들을 선언한 헤더파일과, 함수 정의부분을 컴파일한 목적 파일(Object File)을 만들고 사용 방법에 대한, 즉 클래스의 생성자 인자라던지 함수 사용 별 동작되는 방식이라던지 이런 부분에 대한 설명이 들어간 문서를 같이 공유하면 된다.

그러면 이 big_integer 클래스 사용하고 싶은 다른 개발자는, big_integer의 소스코드는 볼 수 없지만, 제공받은 헤더파일과 컴파일된 목적 파일, 그리고 사용법을 확인해서 자신의 프로젝트에서 그 개발자가 작성한 big_integer 클래스를 자유로이 쓸 수 있게 된다. 이 때, big_integer 클래스의 헤더파일과 컴파일된 목적 파일, 그리고 사용 방법에 대한 문서는 "C++ big_integer 라이브러리"가 된다.

그리고 여기서 big_integer 클래스의 생성자의 인자와, add 함수의 인자 및 리턴 타입 등 big_integer 클래스를 사용하기 위한 메소드 프로토타입들은 이 C++ big_integer 라이브러리의 "API"가 된다.

API

API의 정의에 대해 다시 자세히 설명해보겠다.

API는 일단 Application Programming Interface의 약자이다. 여기서 Application이란 Application Program이란 뜻으로, 한글로는 응용 프로그램이다.

컴퓨터 프로그램은 크게 응용 프로그램과 시스템 프로그램으로 나뉘는데, 시스템 프로그램이 아니면 모두 응용 프로그램이라고 보면 된다. 시스템 프로그램은 쉽게 말하면 운영체제이다. 따라서 간단하게 생각하면 'Application -> 운영체제가 아닌 모든 프로그램' 이다.

Programming은 프로그램을 만드는 것을 뜻한다. 따라서 API는 응용 프로그램을 만들 때 사용하는 인터페이스라는 뜻이 되는데, 그러면 인터페이스는 무엇을 뜻하는가?

예를 한번 들어보겠다. 노트북에 USB 메모리를 연결해서 데이터를 전송하려고 한다. 이 때, 노트북과 USB 메모리의 인터페이스는 무엇일까?

USB포트가 이 서로 다른 두 물체의 인터페이스다. 인터페이스는 간단하게 서로 다른 두 개 이상의 것들을 이어주는 '매개체'라고 생각하면 된다.

API는 따라서 응용 프로그램을 작성할 때 필요한 매개체라는 해석이 가능하다. 그러면 매개체가 왜 필요한 것일까?

실무 개발에서는 프로그램의 크기가 커지면 혼자서 밑단 부터 윗단 까지 모두 다 개발할 수 없다. 따라서 서로간의 협업이나 이미 만들어진 소프트웨어 컴포넌트를 결합해서 만드는데, 이 때 라이브러리도 그 중 하나이다. 그러한 컴포넌트들을 결합하기 위한 매개체들을 API라고 하는 것이다.

C++ 어플리케이션을 작성할 때 다른 C++ 클래스 라이브러리를 사용하는 경우 해당 클래스에 정의된 메소드들을 실행함으로써 해당 라이브러리를 활용한다. 따라서 해당 메소드들의 필요한 인자나 리턴 타입 등이 C++ 클래스 라이브러리의 API가 되는 것이다.

그런데 보통 외부 컴포넌트의 경우 라이브러리 형태로 제공받는 경우가 많아서 라이브러리와 API의 뜻을 햇갈려하는 경우가 많다. 하지만 라이브러리는 이러한 컴포넌트 자체를 뜻하고, API는 이 컴포넌트를 활용하는 규약이라고 보면 된다. 다음 예에서 라이브러리가 아니지만 API를 제공하는 경우를 확인해보자.

구글 클라우드에서 제공하는 Speech API가 있다.(이름 부터 대놓고 API이다)

음성 데이터를 넣으면 그 데이터를 원하는 언어의 텍스트로 인식해서 돌려주는 방식이다. 그리고 기계학습을 이용한 인공지능 기술로 해당 기능을 구현하였다고 하고, 내부적인 동작은 공개하지 않고 있다. 그리고 여기서 제공하는 RESTful API의 경우는 특정한 포맷에 맞추어서 HTTP 음성 데이터를 포함한 요청을 보내면 HTTP 응답으로 해석해낸 텍스트가 돌아오는 방식이다. 이 때 HTTP 요청/응답 포맷 역시 API이며, 이는 개발자의 로컬 컴퓨터에 설치된 라이브러리를 통해 제공받는 방식이 아니다. 외부 원격에 있는 서버에서 부터 이러한 음성 인식 서비스를 제공받는 것이다.

이 경우는 라이브러리가 아니지만 API를 제공한다.

ABI

이제 API와 차이점을 잘 알기 어려워 할 수 있는 ABI에 대해 알아보자.

API라는 단어는 흔히 접하게 되어서 대략적으로도 뜻을 알기 쉬운데 ABI는 자주 접하는 단어는 아니다. ABI는 Application Binary Interface의 약어로 직역해보면 응용프로그램 이진 인터페이스이다. 응용프로그램과 다른 컴포넌트간에 이진 인터페이스인데, 이때 이진은 Binary로 0과 1을 뜻하는데 컴퓨터에서 가장 로우레벨, 가장 기계와 가까운 수준으로 내려가게 되면 0과 1로 이루어진 이진값들로 가게 된다. 기계 수준, 이진값 수준에서 인터페이스를 뜻한다. API는 소스코드 레벨에서 호환이 된다면, ABI는 바이너리 수준에서 호환이 된다고 한다.

바이너리 수준에서 호환이 된다고 하면 바이너리로 이루어진 기계어들과 관련이 있다고도 볼 수 있겠다.

이 기계어들은 결국 물리적인 프로세서, 즉 CPU에서 실행을 하고, CPU들이 실행하는 기계어 명령어 셋들을 ISA(Instruction Set Architecture)라고도 부른다. 이 ABI는 실질적으로 ISA와 밀접한 관련이 있다고 볼 수 있다.

아까 라이브러리와 API를 햇갈려 하듯이, ABI와 ISA는 햇갈릴 수 있는 관계라고 볼 수 있다. 

하지만 의미상으로는 ISA는 해당 하드웨어 프로세서가 실행할 수 있는 기계어 명령어 세트를 의미하고, ABI는 바이너리 코드 레벨에서 호환되는 인터페이스를 의미한다. 

아래는 안드로이드 스튜디오에서 에뮬레이터를 생성하려고 할 때 고르는 화면이다. 우측에 보면 CPU/ABI라고 되어 있는 항목이 있다. x86이라고 쓰여 있는데 이는 흔히 쓰이는 Intel에서 개발한 유명한 32bit CPU 아키텍쳐 중 하나이다. CPU라고도 같이 쓰여있는 것으로 보아 ABI와 CPU 아키텍쳐는 여기서는 사실상 같은 의미로 쓰이고 있다고 볼 수 있다.

API라고 쓰여있는 부분도 있는데, 여기서 API는 안드로이드 API 버전을 의미하며, API level 28는 안드로이드 PIE 버전을 의미한다. API Level 27 안드로이드 환경에서 앱을 만들때와, API Level 28에서 안드로이드 환경에서 앱을 만들 때, 소스코드의 형태가 다를 수 있다는 것을 시사하는 것이다.

이렇게 이야기를 하면 이해가 어려우므로 예를 들어서 설명해보도록 하겠다.

Windows 운영체제에서 다음과 같은 Hello World 코드를 작성해서 컴파일 후 실행해 보았다.

 

#include <stdio.h>
int main() {
	printf("Hello World!\n");
	return 0;
}

이 코드를 그대로 복사해서 Ubuntu Linux 환경에서 컴파일 후 실행하면 같은 결과가 나올까?

정답은 당연히 Yes이다. 왜냐하면 윈도우 환경과 리눅스 환경에서 표준 입출력 라이브러리에 구현된 printf 함수의 스펙이 같기 때문이다. 받는 인자와 결과가 같기 때문이다. 

이것은 윈도우와 리눅스의 printf 함수의 API가 호환이 되기 때문이라고 볼 수 있다. 호환이 된다는 것은 같은 입력값을 넣었을 때 같은 결과값이 나타난 다는 것이다.

그러면 만약 x86 CPU를 사용하는 윈도우 시스템에서 대충 다음과 같은 어셈블리 코드를 실행한다고 생각해보자.

 

[BITS 32]
mov	ax, 0x01

ax레지스터에 1이라는 값을 넣는 결과가 나타날 것이다.

그러면 이 똑같은 코드를 기반으로 x86 CPU를 사용하는 리눅스 시스템에서 같은 코드를 실행한다면 같은 결과가 나올까?

이 질문의 답도 Yes이다. 어셈블리 언어는 바이너리 값과 1대 1 매칭이 되므로, 어셈블리 수준에서 호환이 된다는 것은 바이너리 수준에서 호환이 된다고 볼 수 있다. 같은 바이너리 값을 실행했을 때 같은 결과가 나타난다면 바이너리 수준에서 호환이 된다고 볼 수 있다.

이 경우 ABI가 호환된다고 볼 수 있다.

두 시스템 다 x86 계열 CPU를 사용을 하기 때문에 나타나는 것으로, 같은 기계어 Instruction에 대하여 똑같이 동작하기 때문에 ABI가 호환이 되는 것이다.

"""

여기서 살짝 궁금증이 있을 수 있는 부분은 ABI가 호환된다면, 윈도우에서 컴파일한 Hello World 실행파일이 리눅스에서는 왜 똑같은 결과를 내면서 실행이 되지 않느냐라는 것인데, 이는 윈도우와 리눅스의 운영체제별 실행파일의 포멧이 다르기 때문이다. 그리고 공유 라이브러리의 존재 유무와 공유 라이브러리의 포맷 등 다른 여러가지 요인들이 섞여있기 때문이다. 따라서 ABI에 대한 예제로 해당 Hello World 실행파일을 주지 않았다.

"""

이러한 개념이다. 따라서 API는 소스코드 레벨의 호환성을 보장하고, ABI는 바이너리 레벨의 호환성을 보장하는 의미이다.

그러면 다음의 사례는 어떠할까?

A 라는 라이브러리를 사용하는 소프트웨어가 있다. A라이브러리의 버전이 업그레이드 되어서 API가 바뀌었다. 이 때 해당 소프트웨어는 A라이브러리와의 호환성을 유지하기위해 어떠한 조치를 취해야 하는가?

=> API가 바뀌었으므로 소스코드를 수정해야 한다.

B라는 소프트웨어는 x86 시스템에서 사용하도록 컴파일되었다. 하지만 이 소프트웨어를 ARM 시스템에서도 사용할 수 있는 버전을 만들려면 어떻게 해야하는가?

=> ABI가 다른 시스템으로 이식해야 한다. 소스코드->바이너리로의 변환은 컴파일러가 해줄 수 있으므로, ARM용 컴파일러나 크로스 컴파일러를 이용해서 새로 컴파일하면 된다.

프레임워크

소프트웨어 프레임워크(software framework)는 복잡한 문제를 해결하거나 서술하는 데 사용되는 기본 개념 구조이다. 간단히 뼈대, 골조(骨組), 프레임워크(framework)라고도 한다. 이렇게 매우 폭넓은 정의는 이 용어를 버즈워드(buzzword)로서, 특히 소프트웨어 환경에서 사용할 수 있게 만들어 준다.

SW분야에서 프레임워크와 일반적인 프레임워크에서 공통되는 부분은 "틀"이라는 부분이다.

무언가를 하기 위한 '틀'에 해당된다.

흔히 이야기하는 "틀에 박힌 사고방식"라는 관용어구에 있는 그 "틀"과 같다고 볼 수 있다.

이 틀이 있음으로써 가지는 장점은 무언가를 해결해야 하거나 할 것이 있을 때, 그 틀에 맞추어서 행동을 하면 누구나 쉽게 따라하면서 해결 해 나갈 수 있다.

반면 단점으로는 그 틀에 맞지 않는 무언가는 해결할 수 없다는 점이 있다.

소프트웨어 프레임워크도 마찬가지이다. SW 프레임워크는 어떠한 문제를 해결하기 위한 소프트웨어적 틀에 해당한다.

예시로 매우 유명한 프레임워크 중 하나인 안드로이드 프레임워크를 들어보겠다.

(사실 안드로이드 시스템은 안드로이드 커널 위에 안드로이드 프레임워크가 올라가는 형식으로 이루어져 있다.)

안드로이드 프레임워크는 안드로이드 시스템에서 구동가능한 안드로이드 앱을 만들 수 있는 API들을 제공을 한다.

OnClickListener라는 java나 코틀린 메소드를 오버라이딩 하면 어떤 View를 눌렀을 때 어떤 동작을 할 것인지를 지정할 수 있고, 실제로 그 뷰를 클릭했을 때 해당 동작이 일어나게 해준다.

이러한 기타 등등의 작업들만 하고 앱을 빌드하면 원하는 대로 동작하는 안드로이드 앱이 생성이 된다. 

API대로만 구현을 하면 앱 내부적으로는 어떠한 최적화나 연산을 하는지는 알 수 없지만, 원하는 대로 동작한다는 것 만 알 수 있다.

이 안드로이드 프레임워크는, 안드로이드 앱을 만들기 위한 정해진 틀이라고 볼 수 있는 것이다.

하지만 안드로이드 프레임워크로는 웹 서버를 만들 수 없다. 왜냐하면, 안드로이드 프레임워크는 안드로이드 앱을 만들기 위한 "틀"이므로, 틀의 원래 목적과 다른 웹 서버를 만들 수는 없다.

그렇다면 라이브러리와 프레임워크는 어떻게 다른 것일까?

일반적으로 프레임워크 안에 라이브러리가 포함되는 경우가 많다. SW 프레임워크는 보통 어떤 거대한 응용프로그램 등을 만들기 위한 "틀"인 경우가 많은데, 이를 위해서 미리 코딩된 코드조각들은 거의 당연히 들어가있다고 볼 수 있다.

이 "미리 코딩된 코드조각"들은 라이브러리에 해당된다고 볼 수 있다.

다만 라이브러리만 가져다 쓰는 경우는, 프로그램의 메인은 개발자가 직접 쓰고, 중간중간 필요한 부분만 라이브러리로 가져와서 쓰는 형태인 반면, 프레임워크를 가져다 쓰는 경우, 그 프레임워크의 본디 목적과 다른 프로그램은 만들 수가 없다.

프레임워크가 라이브러리에 비해 해 주는 일이 더 많고, 규모가 거대한 만큼 원래 목적과 다른 일은 할 수 없다는 점이 다르다고 볼 수 있다.

아래 KLDP에서 프레임워크와 라이브러리 차이에 대한 쓰레드가 열린 적이 있는데, main문을 바꿀 수 있으면 라이브러리고 아니면 프레임워크다 하는 식의 이야기도 나오곤 한다.

https://kldp.org/node/124237

사실 프레임워크의 정의 자체가 매우 엄밀한 정의는 아니므로 몹시 까다롭게 따질 필요는 없으나, 소프트웨어 분야에 종사하는 사람으로써 매우 자주 쓰이는 용어 중 하나이므로, 한번 짚고 넘어갈 필요는 있다고 생각한다.

 
struct big_integer {
	char *digit;
	int length;
	char sign;
	struct big_integer* add(struct big_integer lhs, struct big_integer rhs);
	struct big_integer* subtract(struct big_integer lhs, struct big_integer rhs);
	struct big_integer* multiply(struct big_integer lhs, struct big_integer rhs);
	struct big_integer* divide(struct big_integer lhs, struct big_integer rhs);
};

지난 시간에 이어 포스팅을 하겠다. 지난 시간에는 C 구조체를 이용해서 위와 같은 big_integer 구조체에 필요한 맴버변수들과 관련 함수들을 묶어서 캡슐화를 할 수 있다는 것 까지 진행했다. 이렇게 확장된 구조체를 C++에서는 클래스라고 부른다. 따라서 다음과 같이 나타내어질 수 있다.

 
class big_integer {
	char *digit;
	int length;
	char sign;
	struct big_integer* add(struct big_integer lhs, struct big_integer rhs);
	struct big_integer* subtract(struct big_integer lhs, struct big_integer rhs);
	struct big_integer* multiply(struct big_integer lhs, struct big_integer rhs);
	struct big_integer* divide(struct big_integer lhs, struct big_integer rhs);
};

위 구조체와 달라진 점은, struct가 class로 바뀌었다는 것 뿐이다. 실제로 C++에서 구조체와 클래스의 문법적인 차이는 매우 미미하다. 하지만 단지 구조체에 함수를 포함시켰다는 것의 작은 의미가 아니라, 절차지향 프로그래밍에서 객체지향 프로그래밍이라는 패러다임의 변화가 함축되어 있는 그러한 부분이다. 따라서 이러한 상징성을 위해서 class라는 새로운 이름을 부여한 것이다.

게다가 실제로 객체지향 프로그래밍을 할 때, 다른 객체지향 개념이 내재된 언어에서 구조체라는 단어는 쓰지 않고 모두 클래스와 객체라고 부른다. 그러면 문법적인 부분에서 C++의 구조체와 클래스의 차이는 어떠한 것이 있을까?

이를 알기 위해선 우선 접근지정자(Access Modifier)와 정보 은닉(Data Hiding)에 대하여 알아야 한다.

객체지향 패러다임에서는 절차지향 패러다임 보다 코드의 모듈화와 재사용성에 많이 관심을 가지면서도, 사람에 의한 실수들을 줄이는 방향으로 발전했다.

객체지향 패러다임에서는 남이 작성한 클래스와 모듈들을 쉽게 재사용하도록 하면서 생산성을 늘렸다. 남이 미리 작성한 클래스들의 내부적인 복잡한 로직은 알 필요가 없도록 추상화되어 숨겨져있고, 어떠한 상황에서 어떠한 함수를 호출해야 하는지 정도만 알면 된다.

하지만 또 다른 관점으로 보면 다른 누군가가 작성한 그 클래스를 사용하는 개발자는 그 클래스의 내부 로직에 대해 잘 모를 것이고, 내부의 중요한 값들을 잘못 건드렸다가 내부적 로직이 꼬이거나 버그를 유발할 수도 있을 것이다.

예를 들어서 big_integer 클래스를 사용하는 누군가가 big_integer.length += 5; 와 같은 코드를 추가하게 된다면 어떠한 일이 발생할까? 실제 자릿수의 값들은 digit이라는 char 포인터 변수가 가리키는 곳에 문자열 형태로 있을 것이고, 이 때 문자열의 길이는 length라는 변수로 계산이 될 것이다. 따라서 허용되지 않은 메모리에 접근하게 될 수도 있다. 그러므로 big_integer 클래스를 사용하는 개발자는 length라는 변수의 값을 읽는 것은 가능하게 하되, length의 변수의 값을 마음대로 바꾸도록 하면 안된다. length의 값은 대입, 덧셈, 뺄샘, 곱셈, 나눗셈 등의 연산으로 인하여 자연스럽게 변화되는 경우에만 변해야 한다. 이럴 때 적용할 수 있는 것이 접근지정자이다.

class big_integer {
private:
	char *digit;
	int length;
	char sign;
	struct big_integer* add(struct big_integer lhs, struct big_integer rhs);
	struct big_integer* subtract(struct big_integer lhs, struct big_integer rhs);
	struct big_integer* multiply(struct big_integer lhs, struct big_integer rhs);
	struct big_integer* divide(struct big_integer lhs, struct big_integer rhs);
};

private라는 이름의 접근 지정자를 설정함으로써, private 접근지정자 밑의 맴버변수와 메소드들은 모두 외부에서 접근이 불가능하도록 변경되었다. 하지만 이렇게 되는 경우는 메소드들도 접근할 수 없게 되므로 좀 곤란해진다. 따라서 메소드들은 외부에서 접근이 가능하도록 변경해 보았다.

class big_integer {
private:
	char *digit;
	int length;
	char sign;
public:
	struct big_integer* add(struct big_integer lhs, struct big_integer rhs);
	struct big_integer* subtract(struct big_integer lhs, struct big_integer rhs);
	struct big_integer* multiply(struct big_integer lhs, struct big_integer rhs);
	struct big_integer* divide(struct big_integer lhs, struct big_integer rhs);
};

이렇게 해서 메소드들은 외부에서 접근이 가능하지만, 멤버변수들은 그렇지 않도록 설정되었다. 그러면 big_integer의 자릿수를 length 변수를 통해서 알아내고 싶다면 어떻게 해야할까?

length 변수에 대한 getter 함수를 지정해주면 된다. 다음과 같은 형태가 될 것이다.

class big_integer {
private:
	char *digit;
	int length;
	char sign;
public:
	struct big_integer* add(struct big_integer lhs, struct big_integer rhs);
	struct big_integer* subtract(struct big_integer lhs, struct big_integer rhs);
	struct big_integer* multiply(struct big_integer lhs, struct big_integer rhs);
	struct big_integer* divide(struct big_integer lhs, struct big_integer rhs);
	int get_length() {
		return length;
	}
};

위와 같이 get_length 함수를 정의해주면, 외부에서 length 멤버변수의 값을 알아야 할 때, get_length 함수를 호출하면서 간단하게 값을 알아낼 수 있다.

일반적으로 클래스의 메소드들을 디자인할 때, 이러한 점에 입각해서 멤버변수들은 모두 private 접근지정자를 설정하고, 메소드들은 public 접근지정자를 설정하는 것이 일반적이다. 그리고 접근해야 할 필요가 있는 멤버변수들에 대해서는 각각 getter 함수와 setter 함수를 지정한다. 만약 setter 함수를 지정하게 된다면 다음과 같은 모습이 될 것이다.

class big_integer {
private:
	char *digit;
	int length;
	char sign;
public:
	struct big_integer* add(struct big_integer lhs, struct big_integer rhs);
	struct big_integer* subtract(struct big_integer lhs, struct big_integer rhs);
	struct big_integer* multiply(struct big_integer lhs, struct big_integer rhs);
	struct big_integer* divide(struct big_integer lhs, struct big_integer rhs);
	int get_length() {
		return length;
	}
	void set_length(int length) {
		this->length = length;
	}
};

하지만 이 big_integer 클래스에서는 length의 값을 임의로 바꾸면 안되므로, set_length 함수가 없는 것이 낫다. 그리고 만약 set_length 함수를 사용한다고 하더라도 저렇게 간단하게 값만 대입하는 방식이 아닌, 입력받은 값이 정당한 값인지 확인하는 과정이 필요할 것이다. 예를 들면 length의 인자에 음수가 들어올 경우 0값을 대입한다는 식으로 말이다.

이렇게 맴버변수와 같이 잘못 건드릴 수 있는 값들을 접근지정자 등을 통해서 외부에서 잘못 바꾸지 않도록 안전장치를 만드는 것을 정보 은닉(Data Hiding)이라고 한다.

이 정보 은닉을 객체지향 프로그래밍의 특징의 한 카테고리고 분류해서 넣는 경우도 있지만, 일반적으로는 저번 포스팅에서 언급했던 "캡슐화"의 특징 중 하나로 보는 경우가 많다. 따라서 "캡슐화"의 특징은 두개로 나뉜다고 볼 수 있다.

1) 관련된 데이터(멤버변수)와 동작(메소드)를 한 곳에 묶어음

2) 외부에서 몰라도 되거나, 몰라야 하는 정보들을 자유롭게 접근하지 못하도록 제한하고 은닉함 (정보 은닉)

이제 C++ 언어에서 구조체와 클래스의 문법적 차이점을 알아보자. 이 두 개의 문법상 차이는 기본 접근 지정자(Default access modifier)가 구조체의 경우 public이고, 클래스의 경우 private라는 것이다. 다시 말하면, 접근 지정자를 설정하지 않을 경우 구조체는 모두 public이고, 클래스는 모두 private이다.

------------------------------------

다음 포스팅에서 이어진다.

이번에는 객체지향 프로그래밍의 개념에 대해서 간단간단하게 설명해보는 포스팅을 올려볼까 한다. 

> 일단 객체지향 프로그래밍이라는 프로그래밍 패러다임이 새로 생겨나게 된 배경에 대해서 설명해보겠다. 

객체지향 프로그래밍 패러다임이 있기 전에는 절차지향 프로그래밍이라는 패러다임이 있었는데, 이는 문제를 해결하는 절차들, Step by Step에 포커스를 맞춘 방식의 프로그래밍 패러다임이었다. 그런데 하드웨어는 급속도로 발달하지만, 소프트웨어는 개발 속도도 늦고 버그도 많고 해서 하드웨어의 발전 속도를 못 따라가는 일이 생겼는데, 이를 간단히 이야기 해서 '소프트웨어 위기'라고 불렀다.

이를 해결하기 위해서 소프트웨어도 하드웨어 부품들을 조립하는 것 처럼, 소프트웨어도 객체라는 부품으로 나누어서 개발을 하고, 이런 객체들을 조립하는 식으로 해보자 라는 아이디어가 객체지향 프로그래밍이다.

이제 객체지향 프로그래밍이 어떤 것인지 예제를 통해서 알아보자. 이 포스팅의 독자는 C언어에 대해서는 기본적은 다 알고 객체지향 개념은 잘 모르는 사람이라고 가정한다.

C언어에서의 문자열(String)은 char형 배열로 표현된다. 하지만 이 방식은 여러모로 불편한 점이 많다. 예를 들어서 scanf("%s");와 같은 코드로 문자열을 입력받을 때, 문자열의 크기가 얼마나 될 지 모르기 때문에 배열의 크기를 너무 작게 지정하면 버퍼 터짐(Buffer overflow) 현상이 나타날 것이고, 너무 크게 지정하면 메모리의 낭비가 될 것이다.

다음은 C언어로 문자열을 입력받는 코드이다.

 
#include <stdio.h>

int main() {
	char str[100]; // 입력받을 문자열의 길이가 99보다 크다면 Buffer overflow 발생
	scanf("%s", str);
}

하지만 C에서 객체지향의 개념이 추가된 C++언어로 같은 동작을 하는 코드를 작성하면 다음과 같이 나타난다.

 
#include <iostream>
#include <string>
using namespace std;
int main() {
	string str;
	cin >> str;
}

위에 있는 C로 작성된 코드의 경우는 입력 받을 문자열의 길이가 99이하 라고 가정하고 100만큼의 메모리만 할당된 char 배열을 선언해서 입력을 받았다. 따라서 99보다 길이가 작은 문자열을 받으면 안쓰는 메모리가 필연적으로 생기고, 99보다 길이가 크다면 버퍼 오버플로가 발생한다.

하지만 C++로 작성한 코드의 경우 string이라는 객체를 사용하면 입력 받을 문자열의 길이에 대하여 상관할 필요가 없다. string 객체 내부적으로 알아서 입력크기에 맞게 메모리 할당을 유동적으로 해주도록 하는 코드가 이미 작성이 되어 있고 그 코드는 흔히 나타날 수 있는 버그들은 알아서 잘 수정이 되어있는 상태이다. 따라서 우리는 이전에 어떤 누군가가 작성한 string이라는 객체 클래스를 사용함으로써 문자열을 이렇게 쉽게 다룰 수 있게 된 것이다.

그리고 이 string 객체를 사용하는 개발자는 string 객체 내에 멤버변수나 메소드가 어떻게 정의되어있는지는 알 필요가 없다. 단지 해당 객체에 어떤 함수가 있고, 그 함수는 어떤 인자를 받고, 어떤 리턴값을 주는지만 알면 된다. 예를 들면 해당 문자열의 길이를 알고 싶다면 개발자는 다음 length함수를 호출하기만 하면 된다.

 
#include <iostream>
#include <string>
using namespace std;
int main() {
	string str("Lorem ipsum");
	size_t len = str.length();
	cout << len << '\n';
	return 0;
}

단지 개발자는 string 클래스에 length라는 함수가 있고 이 함수의 원형은 size_t length(void); 이며 리턴값이, 해당 문자열의 길이라는 것만 알면 되고, 내부적으로 해당 함수가 어떻게 구현되어있는지 알 필요가 없다. 따라서 string 클래스 내부 구조에 신경을 쓸 필요도 없다.

이러한 특징을 "추상화"라고 하며 이는 객체지향 프로그래밍의 4대 특징 중 하나이다. 해당 클래스 사용자는 클래스에 대해서 '추상적'으로만 알면 된다는 것이다. length함수 -> 문자열 길이 리턴 이라고 '추상적'으로만 알면 되고 length 함수 호출 시 어떠한 내부 기작이 일어나고 메모리에서 어떤 일이 일어나는지 '구체적'으로 알 필요가 없다는 뜻이다.

여기까지가 객체지향 프로그래밍에 있는 객체를 '사용하는 입장'에서 알아본 것이다.

이제 객체라는 개념이 C언어 문법에서 C++문법으로 확장될 때 프로그래밍 언어의 문법적인 관점에서는 어떻게 해석되는지 알아보자.

C언어에는 구조체라는 문법이 있다. Composite Data Type의 대표격이며, Primitive Data Type들과 Composite Data Type들을 묶어서 한 덩어리로 만들 수 있다. 한 예를 들어서 C언어에서 64bit 정수형으로 나타낼 수 있는 값 보다 훨씬 큰 정수 값을 다루기 위한 big_integer라는 구조체를 만든다고 생각해보자. 아마 다음과 같이 구성할 수 있을 것이다.

 
struct big_integer {
	char *digits;
	int length;
	char sign; // 0이면 양수, 1이면 음수를 나타낸다.
};

 
struct big_integer* add(struct big_integer lhs, struct big_integer rhs);
struct big_integer* subtract(struct big_integer lhs, struct big_integer rhs);
struct big_integer* multiply(struct big_integer lhs, struct big_integer rhs);
struct big_integer* divide(struct big_integer lhs, struct big_integer rhs);

함수에서 각 좌항 우항을 넣어서 호출 시, 함수 내부에서 big_integer 구조체를 malloc으로 동적할당한 뒤 필요한 값들을 넣고 리턴을 해준다고 생각해보면 위와 같은 프로토타입이 나타날 수 있다.

함수 명들은 직관적으로 add, subtract, multiply, divide등으로 명명하였다. 하지만 만약에 big_integer 구조체 외에 큰 수의 부동소수점을 나타내기 위한 big_float라는 구조체가 더 있다면 어떠할까?

비슷한 방식으로 big_float라는 구조체가 선언될 것이다. 그리고 해당 구조체에서 사용할 함수들도 생겨나야 하는데 그 함수들도 모두 big_float 구조체의 사칙연산을 처리해야할 것이다. 이렇게 해당 구조체에서만 사용될만한 함수 이름이 겹치기 쉬워진다. 따라서 해당 함수들의 이름 앞에 사용될 구조체의 이름을 붙이거나, 아니면 함수 오버로딩과 같은 방식을 통해서 이러한 문제를 해결해야 한다.

그리고 만약 big_integer라는 구조채를 다른 사람들도 사용할 수 있도록 배포한다고 하면, 구조체 뿐만 아니라 해당 구조체용 함수들도 같이 배표해야 한다.

물론 그렇게 해도 된다. 그래서 C언어에서도 객체지향 프로그래밍 패러다임을 따르는 것 처럼 프로그래밍이 가능하다. 하지만 큰 소프트웨어 프로젝트를 진행할 때는 이러한 부분들을 프로그래밍 언어차원에서 지원을 해 주면 개발자들이 좀 더 직관적이고 편하게 개발을 할 수 있다. 사람이 할 수 있는 실수들과 햇갈릴 수 있는 것들을 도구 차원에서 덜 햇갈리게 하고 실수를 방지하는 장치들을 추가해주는 것이다.

그렇게 객체지향 프로그래밍 언어인 C++에서는 객체지향 프로그래밍을 위하여 C에서 사용되는 구조체들을 다음과 같이 확장해 나갔다.

 
struct big_integer {
	char *digit;
	int length;
	char sign;
	struct big_integer* add(struct big_integer lhs, struct big_integer rhs);
	struct big_integer* subtract(struct big_integer lhs, struct big_integer rhs);
	struct big_integer* multiply(struct big_integer lhs, struct big_integer rhs);
	struct big_integer* divide(struct big_integer lhs, struct big_integer rhs);
};

big_integer라는 구조체에 해당 구조체를 위해 필요한 함수들을 구조체에 포함시켜버렸다. 언어차원에서 C절차지향 -> C++객체지향으로 발전한 것은 간단하게 생각하면 구조체에 함수도 같이 포함시킬 수 있다는 점인 것이다.

이렇게 관련있는 데이터(구조체 맴버변수)에 함수들도 묶어버린 것을 "캡슐화"라고 한다. 이 특징 역시 추상화와 같이 객체지향 프로그래밍 4대 특징 중 하나이다. 데이터와 동작을 묶어서 하나의 캡슐로 묶어버린 것이라고 생각하면 이해하기 쉽다.

이렇게 해서 이 하나의 big_integer라는 구조체에 함수를 포함시키는 확장을 함으로써, 이 구조체가 소프트웨어의 부품으로서 동작할 수 있게 된 것이다.

-----------------------------------------

다음 포스팅에서 이어진다.

한국정보올림피아드(정올) 2014년도 초등부 문제 풀이 포스팅입니다.

문제들은 백준저지에서 참고하고 풀이했습니다.

https://www.acmicpc.net/category/detail/1274

총 4문제가 있습니다.

1번 전자레인지 문제입니다. (백준 10162)

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

나눗셈 연산과 모듈러 연산을 이용하면 간단하게 해결할 수 있습니다.

 

#include <iostream>

using namespace std;

int main() {
	int t;
	cin >> t;
	if (t % 10 != 0) {
		cout << -1 << endl;
		return 0;
	}
	int m300, m60, m10;
	m300 = m60 = m10 = 0;
	
	m300 = t/300;
	t %= 300;
	m60 = t/60;
	t %= 60;
	m10 = t/10;
	cout << m300 << ' ' << m60 << ' ' << m10 << endl;
	return 0;
}

2번 색종이 문제입니다. (백준 10163)

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

N값이 작으므로, 2차원 배열로 종이 그리드를 모두 나타내고 시뮬레이션 한 뒤 개수를 세면 됩니다.

 

#include <iostream>

using namespace std;

int map[102][102];
int sz[101];
int n;
int main() {
	cin >> n;
	int sx, sy, dx, dy;
	for (int i=1; i <= n; i++) {
		cin >> sx >> sy >> dx >> dy;
		dx += sx;
		dy += sy;
		for (int x=sx; x < dx; x++) {
			for (int y=sy; y <dy; y++) {
				map[x][y] = i;
			}
		}
	}
	
	for (int i=0; i < 101; i++) {
		for (int j=0; j < 101; j++) {
			if (map[i][j]) {
				sz[ map[i][j] ]++;
			}
		}
	}
	for (int i=1; i <= n; i++) {
		cout << sz[i] << endl;
	}
}

3번 격자상의 경로 문제입니다. (백준 10164)

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

다이나믹 프로그래밍으로 문제를 해결할 수 있습니다. K값이 하나 뿐이므로, (시작점 -> K까지 경로)와 (K지점 -> 도착점까지 경로)를 나누어서 구해주면 된다. 숫자를 1부터 세므로 이에 따른 오류를 조심해야 한다.

get함수를 쓸 때 dp[x][y]는 시작 지점에서 (x, y)까지 도달 할 수 있는 경로의 개수를 뜻한다.

get2 함수를 쓸 때에는, (limitx, limity)에서 (x, y)로 도달할 수 있는 경로의 개수를 뜻한다.

get함수가 호출되었을 때에는 K지점을 기점으로 왼쪽과 위쪽부분의 부분 사각형에만 값이 들어가 있으며 또한 get2함수에서 (limitx, limity)보다 위쪽이나 왼쪽은 0으로 예외처리가 되어있게 처리되어있다.

 

#include <iostream>

using namespace std;
int dp[16][16];

int n, m, k;

int get(int x, int y) {
	if (x < 0 || y < 0) return 0;
	if (x == 0 && y == 0) return 1;
	if (dp[x][y]) return dp[x][y];
	
	return dp[x][y] = get(x-1, y) + get(x, y-1);
}

int get2(int x, int y, int limitx, int limity) {
	if (x < limitx || y < limity) return 0;
	if (dp[x][y]) return dp[x][y];
	
	return dp[x][y] = get2(x-1, y, limitx, limity) + get2(x, y-1, limitx, limity);
}
int main() {
	cin >> n >> m >> k;
	
	if (!k) {
		cout << get(n-1, m-1) << endl;
	} else {
		int xpos = (k-1) / m;
		int ypos = (k-1) % m;
		get(xpos, ypos);
		cout << get2(n-1, m-1, xpos, ypos) << endl;
	}
}

4번 버스 노선 문제입니다. (백준 10165)

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

케이스를 잘 나누어야 한다. 일단 노선이 직선일 경우에 대하여 생각을 해 보자. 비교 연산자를 재정의해서 소팅해서, 시작위치는 오름차순으로, 끝 위치는 내림차순으로 정렬한다.    

그러면 소팅을 하고 나서 선형탐색을 앞에서 뒤로 할 때, 뒤에 나타난 녀석이 앞에 있는 녀석을 포함하는 경우는 없다. 

시작위치는 뒤로 갈 수록 앞으로 가기 때문에 시작 범위는 줄어들기 마련이다.    

그리고 시작 위치가 고정인 상태에서는 끝나는 위치는 계속해서 작아지게 되어있으므로, 시작 위치가 다음 값이 되었을 때 끝 위치가 가장 큰놈 일 것이다. 이러한 점을 이용해서 끝놈 위치만 저장해 놓고, 끝놈보다 작으면 포함시켜버리고, 끝놈보다 크면, 그 끝놈 위치를 새 끝놈 위치로 저장해서 끝만 비교하면서 선형 탐색을 하면 된다.    

그러면 또 노선이 원형일 경우를 체크를 해야 하는데, 시작점<끝점 의 경우 A그룹으로 정의하고 시작점>끝점 의 경우를 B그룹으로 정의를 하자. B그룹의 경우는 0번위치를 무조건 통과하고 A그룹은 0번 위치를 지나갈 수는 없다. 따라서 A그룹이 B그룹을 포함할 수는 없다. 

B그룹에서 시작 부분의 최대값을 구하고, 끝 부분의 최소값을 구해서 A그룹의 (?~시작부분 최대값) 의 경우와 (끝부분 최소값~?)을 모두    

포함할 수 있다. 이러한 경우를 체크해 주고(B가 A를 포함하는 경우) A그룹이 A를 포함하는 경우와 B그룹이 B를 포함하는 경우는 직선에서 비교하는 것과 똑같은 방법으로 체크하면 된다.

 

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

int n, m;

struct Route {
    int src, dst, num;    
};

bool cmp(const struct Route& lhs, const struct Route& rhs) {
    if (lhs.src != rhs.src) return lhs.src < rhs.src;
    return lhs.dst > rhs.dst;
}

vector<Route> small, large; //인덱스 숫자가 작을수록 범위가 큰놈이다.
vector<bool> ans;
int main() {
    cin >> n >> m;
    ans.reserve(m+1);
    int large_over = -1;
    int large_below = n+1;
    int over = 0;
    for (int i=1; i<=m; i++) {
        Route tmp;
        scanf("%d %d", &tmp.src, &tmp.dst);
        tmp.num = i;
        if (tmp.src < tmp.dst) {
            small.push_back(tmp);
        } else {
            large_over = max(large_over, tmp.dst);
            large_below = min(large_below, tmp.src);
            large.push_back(tmp);
        }
    }
    sort(small.begin(), small.end(), cmp);
    sort(large.begin(), large.end(), cmp);
    
    //초기 large_over값은 large가 small 덮어쓰는 경우(0~over 범위로 덮는 경우임)
    //초기 large_below값은 large가 small 덮어쓰는 경우(below~N) 범위로 덮는 경우
    //진행하다보면 small이 small 덮어쓰는 경우도 있음
    for (size_t i=0; i < small.size(); i++) {
        if (small[i].dst <= large_over) ans[small[i].num] = true;
        else if (small[i].src >= large_below) ans[small[i].num] = true;
        if (small[i].dst <= over) {
            ans[small[i].num] = true;
        } else {
            over = small[i].dst;
        }
    }
    over = -1; //large가 large 덮어쓰는 경우
    for (size_t i=0; i < large.size(); i++) {
        if (large[i].dst <= over) ans[large[i].num] = true;
        else over = large[i].dst;
    }
    
    for (int i=1; i <= m; i++) {
        if (!ans[i]) {
            cout << i << '\n';
        }
    }
    
	return 0;
}

백준저지에서는 다양한 언어를 지원합니다. 그 중에서도 32bit Assembly 언어도 지원을 합니다. 32bit Assembly로 백준저지에서 간단한 문제를 풀어보도록 하겠습니다.

일단 로컬에서 Assebmly 코딩을 하기 위해서 어셈블 환경을 만들어 볼 것인데요, 일단 Ubuntu 16.04기준으로 하겠습니다.

nasm과 gcc를 설치해줍니다. 만약 호스트가 64bit 운영체제라면 32bit 컴파일을 위해서 gcc-multilib을 설치해줘야 합니다.

다음 명령어로 어셈블리를 ELF파일로 빌드할 수 있습니다.

 
nasm -f elf32 assembly.asm -o assembly.o
gcc -m32 assembly.o -o assembly.out

어셈블러로 어셈블리 소스코드를 오브젝트 파일로 바꾼 뒤, 실행가능한 ELF 바이너리로 빌드하는 과정입니다.

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

백준 2557번 Hello World를 어셈블리 코드로 작성해보도록 하겠습니다.

printf 라이브러리 콜을 이용해서 작성한 코드입니다.

extern을 이용해서 사용할 함수 명을 가지고 오며, 함수의 인자를 스택에다가 push해서 호출하는 것을 확인할 수 있습니다. Calling convention에 따라서 Caller function에서 스택을 정리하는 모습(add esp, 4)도 보입니다.

 
extern printf
section .data
    msg : db "Hello World!", 0xa, 0
        
section .text
    global main
main:
    push msg
    call printf
    add esp, 4
ret

write 시스템 콜을 이용해서 작성한 코드입니다.

int명령어로 인터럽트를 발생해서 시스템 콜을 호출하며, 시스템 콜 인자를 지정된 레지스터에 넣어서 호출하는 것을 확인할 수 있습니다.

EAX에는 시스템 콜 번호(write의 시스템 콜 번호는 4입니다), EBX는 첫번째 인자(stdout=1), ECX는 write할 Address로 두번째 인자, EDX는 세번째 인자로 문자열의 길이가 들어가게 되었습니다.

 
M: db "Hello World!"
section .text
global main
main:
    mov edx, 12
    mov ecx, M
    mov ebx, 1
    mov eax, 4
    int 0x80
    ret

어셈블리로 ps 문제 등을 풀면 어셈블리 언어에 대한 이해도가 늘고 리버싱이 쉬워질 것 같습니다.