대엉코딩

1. 멀티 프로세스

- 각각의 프로세스들은 독립적이므로, 하나의 프로세스가 죽더라도 다른 프로세스에는 영향을 끼치지 않는다.

- 하지만 멀티 스레드에 비해 더 많은 메모리공간과 컨텍스트 스위치로 인한 시간을 많이 차지한다.

- 여러개의 프로세스가 필요한 작업을 하나의 프로세스내의 여러개의 스레드로 나눠 수행하면 메모리 공간과 시스템 자 원소모, 실행시간을 줄일 수 있다.

2. 멀티스레드

- 멀티프로세스에 비해 적은 메모리공간 차지, 컨텍스트 스위치가 빠름

- 하나의 스레드에 문제가 발생하면, 다른 스레드들도 영향을 받을 수 있다.

- 스레드간의 통신은 별도의 자원을 이용하지 않고, 전역변수나 힙 영역을 이용해서 데이터를 주고 받을 수 있다

   ( 스택은 각각 가지지만, 힙 공간은 공유함)

- 이 점은 문제가 되기도 한다.... 멀티 프로세스는 프로세스간 공유하는 자원이 없으므로 동일한 자원에 동시에 접근하지 않지만, 멀티 스레드는 서로 다른 스레드가 데이터와 힙 영역을 공유하기 때문에 잘못 수정하거나, 예상치 못한 값으로 수정되는 경우가 발생할 수 있어서 동기화 작업이 필요하다.

- 작업 순서와 공유자원 처리에 대해 신경써야 한다. 이 과정에서 병목현상으로 인한 성능 저하가 나타날 수 있다. 

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 역시 스택프레임에 객체의 주소를 가지고 올라감으로써 쉽게 객체의 멤버변수에 접근할 수 있도록 해주고 있

  습니다.

www.acmicpc.net/problem/1463

1. 풀이방법

- 맨 처음에는 3으로 나누어떨어지면 -> 2로 나누어떨어지면 -> 이것마저 안되면 -1 이라고 생각했었는데

- 이럴경우 10->5->4->2->1  (답은 10->9->3->1)

- 그리고 나서 숫자를 쭉 써놓고 한번생각을 해보았는데

- 결국 비교해야 할 경우는 3가지 이다 N-1 과 N/3 과 N/2 이다.

- 중요한 것은 경우에 따라 N-1을 한 경우가 최소연산 일 수 있다는 것.

2. 주의사항

- 처음에는 항상 익숙한대로 탑다운 방식(재귀함수)를 이용했다.

-결과는 "메모리 초과"

- 문제 조건을 보았는데 메모리는 128MB까지 허용이 가능하고

- 내가 사용한 용량을 얼추 계산해봐도 1,000,000 * 4바이트(INT) 기껏해서 4MB 정도이다. (짜잘한 것은 생략.)

- 추측한 것은 재귀로 너무 깊이 들어가서 스택메모리가 초과되었나? 라는 생각

- 그래서 재귀를 사용하지 않고 바텀업 방식(반복문이용) 으로 짰더니 통과가 되었습니다.

3. 나의코드

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

int X;
int dp[1000001];

//메모리 초과
/*int getdp(int num) {
	if (dp[num] == 0) {
		if (num % 3 == 0) { dp[num] = min((getdp(num - 1) + 1), (getdp(num / 3) + 1)); return dp[num]; }
		else if (num % 2 == 0) { dp[num] = min((getdp(num - 1) + 1),(getdp(num / 2) + 1)); return dp[num]; }
		else { dp[num] = getdp(num - 1) + 1; return dp[num]; }
	}
	else { return dp[num]; }
}*/
void bottomup() {
	for (int i = 6; i < 1000001; i++) {
		if (i % 3 == 0) {dp[i] = min(dp[i - 1] + 1, dp[i / 3] + 1);}
		else if(i%2==0){ dp[i] = min(dp[i - 1] + 1, dp[i / 2] + 1); }
		else { dp[i] = dp[i - 1] + 1; }
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> X;   //  X>1
	dp[1] = 0;
	dp[2] = 1;
	dp[3] = 1;
	dp[4] = 2;
	dp[5] = 3;
	bottomup();
	cout<<dp[X]<<"\n";
	return 0;
}

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

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

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

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

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

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

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

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

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

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

- 것입니다.

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

<필기>

<코드>

* 큐(queue) 란 ?

- FIFO(First In Fisrt Out)

- 편하게 생각해보면 맛집에 줄 서있는 사람들을 떠올리면 될것이다.

  (먼저 줄을 선 사람 순서대로 식당에 들어간다.)

- 그외에 번호표, 버퍼(buffer) 도 같은 개념이라고 보시면 되겠네요 !

* 큐의 연산

- 삽입, 삭제, 비어있는지 확인, 맨 앞 (front) 확인,끝(rear) 확인 크기 등의 연산이 있다.

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

   연산 : enqueue(x)

           dequeue()

           front()              

           rear()

           peek() -> front에 위치한 데이터 확인

           empty()

- 시간 복잡도: (배열을 통한 구현으로 생각해보겠습니다.)

                   enqueue의 경우 배열 맨 끝에 추가하면 됩니다. O(1)

                   dequeue의 경우 배열의 앞에서 빼고 다른 요소들을 모두 하나씩 당기는 방식으로 구현할 경우 O(n)

                                         (이경우 front는 무조건 index가 0일 것이므로 따로 index변수를 관리 할 필요가 없겠죠)

                                         배열의 앞에서 빼고 front index를 따로 관리하여 +1만 해주는 경우 O(1) - 효율적

                   그 외 front(), rear(), peek() 등의 연산들은 index를 관리해줄 경우 모두 O(1) 타임 이겠죠?

* 큐 구현상의 문제점

                   만약 index를( 따로 front와 rear 를 가리키는) 관리해주는 방식으로  (효율적)

                   그럴 경우 배열의 크기는 정해져 있다는 것을 생각 해보면 계속 enqueue와 dequeue 작업을 수행하면

                   계속 뒤로 밀려지게 되다가 결국 배열의 크기를 넘어 가게 되면 오류가 발생하게 될 것 입니다.

                   이 때는 환형 배열을 이용 하면 이 방식의 문제를 해결할 수 있습니다.

                   만약 자료가 많아서 배열을 모두 채울경우 배열의 크기를 두배로 늘려서 다시 모든 요소들을 새로운

                   큰 크기의 배열로 옮겨주고 수행해야 하는 경우 enqueue 는 O(n) 타임이 걸릴 것입니다.

                   만약 연결리스트(링크드 리스트)로 구현할 경우 이러한 문제는 해결 할 수 있을것입니다.

                   하지만 링크드 리스트로 구현할 경우 코드상의 즉 런타임시간에 동적할당을 자주 해야 할것이고

                   이로인해 성능이 배열을 통해 구현한 순환큐 보다는 성능이 떨어질 수도 있습니다.

                   그러므로 만약 큐(자료)의 크기가 어느정도 예측이 가능할 경우 배열을 통한 순환큐가 

                   더 적절한 상황이 나타날 수 있습니다.

* 큐 활용의 예

(큐의 특성을 생각해본다면 매우 많겠죠???)

- 프린트기

- 너비우선탐색(bfs)

- 은행업무

- 그외 등등

* 큐의 구현

< 배열 이용한 구현>