대엉코딩

0. 프로그램이란?

 - "실행할 수 있는 파일 ( 무언가 작업하기 위해 ) "

 - ex) 윈도우의 exe 파일 

1. 프로세스 란?

 - " 실행되고 있는 컴퓨터 프로그램 (독립적) "

 - 각 프로세스는 각각의 자원을 할당 받는다.

 - 프로세스 간의 통신 위해서는 파이프, 소켓등을 사용해 통신한다. (비용이 상대적으로 많이 든다.)

 - Register, Counter, Stack, Heap, Code 으로 구성된다

 - 시작, 종료, 컨텍스트 스위칭 시 비용(시간) 이 많이 소요된다.

 - 프로세스 간의 전환에는 운영체제 호출을 필요로한다.

1-1. 프로세스 제어 블록(PCB) 란?

- 운영체제의 자료구조

- 프로세스에 정보를 저장하고 있다.

- 운영체제는 프로세스 생성과 함께 PCB를 생성한다.

- 프로세스 스위치가 발생하면 진행중이던 작업들은 PCB에 저장하고 CPU를 반환한다.

- 다시 CPU를 할당받으면 PCB에서 복원해와 종료시점부터 다시 작업을 수행한다.

- 프로세스 ID, 프로세스 상태, 프로그램 카운트(다음 실행 명령어의 주소), CPU레지스터 등이 저장된다.

2. 쓰레드 란?

 - " 프로세스의 하나의 실행 단위 "

 - 프로세스 안에서 각각의 작업을 처리한다.

 - 프로세스 안에서 동시성(concurrency)을 가지고 진행한다.

 - 한 프로세스 안의 여러개의 프로세스들은 Code, Data, Heap은 공유하고, 각각의 Stack을 가진다. 

 - 시작, 종료, 컨텍스트 스위칭 시 비용(시간) 이 적게 소요된다.

 - 쓰레드 간의 전환에는 운영체제를 호출할 필요가 없다.

 - 자원을 공유하는 만큼, 공유자원에 접근하고, 변경을 할 때 주의가 필요하다.

2-2. 멀티스레딩 이란?

- 하나의 프로세스를 다수의 실행 단위로 구분하여 자원을 공유하고 자원의 생성과 관리의 중복성을 최소화하여 성능을 향상시키는 기법

- 각각의 스레드는 각각의 스택과 PC레지스터 값을 가진다.

- 독립적 실행흐름을 위해서 스택은 필요하다. (각각 가지는 이유)

- 스레드는 하나의 실행 단위 이므로 PC레지스터를 통해 실행위치를 CPU할당에 따라 저장,복구하여 그 위치에서 다시 실행한다.

www.acmicpc.net/problem/1406

1. 풀이방법

- 커서가 여러칸씩 뛰는 명령어는 없으므로 상대적으로 간단하였습니다.

- 저는 커서의 앞쪽은 VECTOR 커서의 뒤쪽은 STACK 을 이용하였습니다.

- 방법은 여러가지가 있을 것 같습니다 편하신대로...

- 커서를 왼쪽으로 옮길 때 커서의 뒤쪽이 되는 한 문자는 STACK에 푸쉬하고

- 커서를 오른쪽으로 옮길 때는 STACK에서 POP해 와서 다시 VECTOR에 넣는 식으로 하였습니다.

- 아마 시작할 떄의 커서의 위치가 맨 뒤쪽이라서 이러한 생각을 자연스럽게 하게된 것 같습니다.

2. 주의사항

3. 나의코드

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
#include<stack>
using namespace std;


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	string s;
	vector<char> tmpc;
	stack<char> tmps;
	int cursor;
	cin >> s;
	for (int i = 0; i < s.length(); i++) {
		tmpc.emplace_back(s[i]);
	}
	cursor = s.length();
	int n;
	cin >> n;
	while (n--) {
		char c;
		cin >> c;
		if (c == 'L') {
			if (cursor == 0) continue;
			else { //커서 뒤쪽은 스택으로 옮겨 놓음
				tmps.push(tmpc[cursor - 1]); tmpc.pop_back(); cursor--;
			}
		}
		else if (c == 'D') {
			if (tmps.empty()) continue;
			else {
				tmpc.emplace_back(tmps.top()); tmps.pop();
				cursor++;
			}
		}
		else if (c == 'B') {
			if (cursor == 0) continue;
			else {
				tmpc.pop_back();
				cursor--;
			}
		}
		else {
			char c;
			cin >> c;
			tmpc.emplace_back(c);
			cursor++;
		}
	}

	//출력부
	for (int i = 0; i < tmpc.size(); i++) {
		cout << tmpc[i];
	}
	while (!tmps.empty()) {
		cout << tmps.top();
		tmps.pop();
	}


	return 0;
}

www.acmicpc.net/problem/10799

1. 풀이방법

- 문제가 요구하는 사항을 구현하는 문제인데, 스택을 이용해서 현재 몇개의 막대가 쌓여있는지를 확인하였습니다.

- 사실 굳이 STACK.SIZE()를 그냥 임의의 변수 하나를 만들어 관리하면 그냥 반복문만으로도 구현 가능합니다.

2. 주의사항

- 조각의 개수가 증가하는 경우는 두가지 경우입니다. 

- (1) 레이저가 자르는 경우 (2) 막대가 끝나는 경우

3. 나의코드

<stack이용>

#include<iostream>
#include<stack>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
using namespace std;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	string s;
	cin >> s;
	stack<char> sarr;
	int resultnum = 0;
	for (int i = 0; i < s.length(); i++) {
		if (sarr.empty()) { //비어있을 경우
			sarr.push(s[i]); continue;
		}
		if (s[i] == ')'&&s[i-1]== '(') { //레이저
			sarr.pop();
			resultnum += sarr.size();
			continue;
		}
		if (s[i] == '(') { //막대의 시작
			sarr.push(s[i]);
		}
		else if (s[i] == ')') { //막대의 끝
			sarr.pop();
			resultnum++;
		}
	}
	cout << resultnum << "\n";
	return 0;
}

<변수로 관리>

#include<iostream>
#include<string>

	using namespace std;

	int main() {
		int cnt = 0, result = 0;
		string t;
		cin >> t;
		for (int i = 0; i < t.length(); i++) {
			if (t[i] == '(') {
				if (t[i + 1] == ')') {
					i++;
					result += cnt;
					continue;
				}
				cnt++;
			}
			else {
				cnt--;
				result++;
			}
		}
		cout << result;
		return 0;
	}

1. 힙 메모리를 사용하는 이유?

- 위의 그림에서 보듯이 heap의 공간과 stack 의 공간에 나누어져 있습니다.

- 그리고 stack메모리의 경우 사용되는 양은 런타임시 결정이 되지만 스택메모리의 최대 공간 (사용가능한) 은 컴파일 시

  이미 지정이 됩니다.

- 왜 스택공간이 있는데 굳이 힙 메모리를 사용해야 하는가 ? 에 대한 궁금증이 떠오르게 됩니다.

- 제가 경험해보고 아는 선에서 몇가지만 이야기해보겠습니다.

-- (1) dynamic (동적할당)

         알고리즘 문제를 풀 때 처럼 입력의 최대값이 정해져 있는경우 그 최대치로 메모리 공간을 할당해서 컴파일 시간

         에 결정을 해서 스택메모리를 사용할 수도 있지만 (큰 사이즈의 경우 다음에 언급), 만약 사용자에 입력에 의해서 

         공간의 변동이 정해지는 경우 개발자 입장에서 미리 그 크기를 예측할 수 없으므로 런타임 시간에 변동에 맞게 

         메모리를 할당해야하는 경우 입니다.

-- (2) size 문제 (엄청 큰)

         이전 게시글에서 언급했다싶이 stack memory의 경우 최대 사이즈가 미리 정해지는 만큼 엄청 큰 사이즈가 필요

         할 경우 stack overflow가 발생할 수 있습니다. 이 때 스택에는 주소를 가리키는 포인터만 설정해주고, heap 메모

         리 공간에 큰 사이즈를 선언해서 가리키게끔 할 수 있습니다.

-- (3) 스택메모리의 life cycle

         스택 메모리의 경우 stack frame단위로 쌓이게 되는데 그 함수가 끝날경우 (life cycle)이 끝날 경우, 스택 메모리에

         서 해제됩니다. 이 경우에도 어떤 데이터를 유지하고 싶을 때는 힙 메모리 공간을 사용합니다. (직접 해제 해주기 

         전 까지 힙 영역에 저장하고 있는 데이터는 사라지지 않으므로)

2. 힙 메모리 사용 in C++

- stack 메모리 대신 heap 메모리를 사용하는 경우는 필요한 용량이 매우 크다던지, dynamic(동적)으로 런타임 시간에

   결정이 되는 변수를 사용한다던지 할 때인데요

- C++에서는 new를 통해서 힙에 공간을 할당 받고 스택 메모리에서의 포인터 변수가 이를 가리키도록 합니다.

- new를 통해서 할당을 받을경우 반드시 까먹지말고 delete을 해주어야만 메모리 leak을 막을 수 있습니다.

- new이외에도 unique_ptr 을 사용한다던지, 배열의 경우 vector를 사용하여 힙에 선언을 해준다면

- 메모리 해제 과정을 신경쓰지 않아도 되게끔 좀 더 안전하게 사용하실 수도 있습니다. 하지만 new를 사용하신다면

- 까먹지말고 반드시 delete으로 해제를 해주어야 한다는 점.!

3. stack 메모리 사용할 때와 heap 메모리 사용할 때의 차이점(장단점?)

- 우선 stack에 선언할 경우 속도가 더 빠릅니다.

- heap의 경우 원하는 만큼의 공간의 힙메모리상에서 찾고 할당하고 나중에는 이를 해제해야 하므로 상대적으로 시간이

- 많이 소요됩니다.

- 그럼에도 heap에는 큰 용량을 필요로 하는 변수라던지, 동적으로 결정이 되는 변수일 때 사용이 가능합니다.

- 그러므로 큰 사이즈가 아닌 경우 (100kb 미만? 정도?) 정도는 속도가 빠른 스택메모리를 사용하는 것이 좋습니다.

- 또 다른 차이점은 스택메모리의 경우 여러번수를 선언하고 주소를 찍어보시면 아시겠지만,

- 빽빽하게?? a가 4바이트를 차지하고, b가 4바이트를 차지한다면 메모리 주소도 4바이트(32bits) 차이가 납니다.

                   (물론 연속되게 위치하고 있을 경우를 가정)

- 중간에 빈 공간없이 빽빽하게 차지하지만, 힙의 경우 구멍이 송송뚤린 것 처럼 사이에 공간이 있습니다.

- 스택처럼 빡빡하게 메모리를 채우지는 않습니다.

0. 메모리 구조를 알아야 하는 이유.

- c++는 개발자가 메모리를 관리를 할 줄 알아야하고, memory 누출이 발생할 경우 (만약 지속적으로)

프로그램이 오류가 날 수도, 다운이 될 수도 있습니다.

- 컴퓨터 구조론인가.....배울 때 많이 학습했던 부분인 것 같은데 시간이 꽤 경과되어서... 다시 중요한 부분 위주로 다시 정리해보겠습

   니다.

1.  메모리 구성

2. Stack

- 이번 글에서는 c++의 스택구조에 대해서 상세히 정리를 해볼까 합니다.

- 변수의 코드를 짜서 포인터를 이용해서 주소를 출력해보시면 아시겠지만, 변수의 주소가 스택으로써 아래에서 위 저장

- 컴퓨터는 변수의 이름을 저장해서 바로 접근하는 것이 아닌, stack의 top의 위치에서 얼마나 떨어져있는지를 기억하여 

  접근합니다.

3. 스택프레임

- 사실 Stack 메모리에 쌓이는 단위는 변수 단위가 아닌 스택프레임 단위인데 이는 function단위 입니다.

- 변수가 하나씩 쌓이는게 아니라 function에서 차지하는 메모리 만큼이 한번에 stack에 쌓이는 것입니다.

- 또한, stack에는 function이나 main 함수의 변수들 뿐만 아니라 스택에 쌓인 function이 종료되면 다시 그 이전의

- 함수 (메인이 될수도, 또다른 function이 될수도)로 돌아 가야 하기 때문에 function call을 한 function 의 return     

   address , 그리고 그 function의 arguments 등이 같이 스택메모리 공간에 쌓입니다.

- 그 function이 끝나면 스택메모리에서 해당부분이 사라집니다.

- 프로그램 실행시 어느정도의 메모리 공간을 확보하는데 간단한 예로 너무 깊이 재귀함수를 실행할 경우, 이 스택메모

  리 공간에 계속 쌓이게 되고, 이는 스택오버플로우를 발생시키는 경우를 종종 확인하실 수 있습니다.

- c++에서는 this라는 키워드를 제공하는데 , 이를 통해서 함수를 실행하면서 객체의 멤버 변수에 쉽게 접근할 수 있습니

  다. this 역시 스택프레임에 객체의 주소를 가지고 올라감으로써 쉽게 객체의 멤버변수에 접근할 수 있도록 해주고 있

  습니다.

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

- 조건1. 같은 문자끼리 연결한 선이 교차 하지 않아야 한다.

- 조건2. 각 글자를 정확히 한개의 다른위치에 있는 다른글자와 짝지을 수 있다.

- 문제를 읽고 조건을 생각해보다가 스택을 이용하면 편하게 풀수 있다고 생각한 것이

- 스택에 넣어놓고 같은 단어가 들어와서 그 단어와 함께 pop이 되면 그것이 선이 교차하지 않는다는 것으로 생각

- 1. 스택이 비어있으면 삽입

- 2. 스택의 top()과 현재 문자가 같으면 스택을 pop()

- 3. 스택의 top()과 현재 문자가 다르면 그대로 스택에 push()

- 단어 전체를 순회 하는동안 위 과정을 거쳐는데 만약 1번 조건이 만족하지 않는다면 스택에서 빠져나가지

- 못한채로 남아있는 문자들이 있을 것이고 1번은 만족해도 2번이 만족되지 않는다면 홀수개의 문자가 스택에 남아있을

- 것입니다.

- 즉 반복문을 모두 돌았을 떄 스택이 비어있어야 그 단어는 좋은 단어 인것입니다.

<필기>

<코드>

* 스택이란 ?

- LIFO(Last In First Out)

- 떠올리기 쉬운것은 주방에 쌓여있는 식기를 놓으면 좋다. 

- 설거지를 해서 위에 쌓으면 사용을 할 때는 위에서 부터 하나씩 가지고 간다.

* 스택의 연산

- 삽입, 삭제, 비어있는지 확인, 상단 확인, 크기 등의 연산이 있다.

- 객체 : 후입선출(LIFO)의 접근 방법을 유지하는 요소들의 모임

   연산 : push(x)

               pop()

               size()              

               peek() -> 스택 상단에 위치한 요소를 반환(봄) (스택이 비어있지 않으면)

    시간복잡도 : size()를 제외하고는 모드 O(1)이라고 할수 있습니다.

                            size()는 어떻게 구현하느냐에 따라 다를 수 있습니다.( 배열이나 연결리스트)

- 말이 나와서 하는 것이지만 추상자료형 (Abstract Data Type)은 사실 어떻게 구현하느냐는 사용자는 알 수 없습니다.

   제가 배웠던 것을 항상 떠올릴 때는 문 밖에서 어떠한 입력을 넣고 요구를 하면 안에서는 어떤식이던지 구현을 하여

   정확한 결과만을 문 밖으로 다시 보내주는 것 입니다. 사용자는 결과를 받지만 내부에 어떤식으로 이를 처리 하였는지는

   알 수 없지요

* 스택 활용의 예

- 문서나 그림, 수식 등의 편집기에서 되돌리기 기능

   (최근 사용했던것 부터 다시 되돌리기를 합니다. -스택을 사용하면 편하겠죠????)

- 함수 호출에서 복귀주소 를 기억 할 때

   (예를 들면, main 함수에서 작업을 수행하다가 다른 함수를 호출해서 그 함수로 이동한다고 하면

     그 함수가 끝나고 났을 때 다시 main 함수로 돌아와서 그 다음 작업을 진행 하여야 합니다.

     그럼 그때 복귀주소를 스택에 넣어 놓습니다.)

- main에서 function A를 호출하고 function A에서 function B 를 호출 한다고 가정을 한다면????

    (스택에 우선 main으로 돌아오기 위한 복귀 주소가 먼저  push될 것입니다. 그다음 function A로 가고

      function B가 수행될 때 function A로 돌아오기 위한 복귀 주소가 그 위에 삽입 될 것 입니다.

      function B가 끝나면 스택에서 맨위 (TOP)을 pop해서 function A 나머지를 수행하고 다시 POP 을

      하면 main함수로 돌아올 수 있습니다.)

* 스택의 구현

 - 1. 배열을 이용

 - 2. 연결리스트를 이용

   직접 구현은 하지 않았지만 연결리스트를 사용하면 처음에 스택 사이즈를 지정 해 줄 필요도 없을 것입니다.

     배열을 이용해서 연결리스트 처럼 구현을 하려면 사이즈를 넘어 갈경우 max사이즈를 두배로 증가시켜서

     다시 배열을 만들고 모든 요소들을 새로운 배열로 이동시키고 원래 배열을  delete 시키고 하는 그런 복잡한

     작업을 해야할 것 입니다.