대엉코딩

0. 스케줄링의 목적

- CPU나 자원을 효율적으로 사용하기 위함

- 멀티 프로그래밍에서 CPU 효율을 극대화 하기 위함

1. 스케줄러 종류

- 장기 스케줄러 ( Long Term )

- 단기 스케줄러 ( Short Term )

- 중기 스케줄러 ( Medium Term )

2. 장기 스케줄러 

- 디스크와 메모리 사이의 스케줄링을 관리

- 디스크에 비해 메모리 크기는 한정되어 있음으로 수행해야할 일(pool)에서 선택적으로 프로세스에 메모리를 할당하여

  Ready Queue로 보내는 역할

- 즉, 실행을 위해 메모리에 적재한다.

- I/O가 자주 필요한 프로세스들은 I/O 시간이 오래 걸리므로 이러한 프로세스들만 많이 올라가면 CPU가 비효율적으로

  사용됨

- CPU 사용이 많은 프로세스들만 올라가면 사용자는 불편함을 느낄 수 있음

- 적절히 섞어서 올려주는 것이 장기 스케줄러의 역할

3. 단기 스케줄러

- 메모리와 CPU사이의 스케줄링을 관리

- Ready Queue에서 어떤 프로세스를 Running 할 지 결정

- 10개의 프로세스가 장기 스케줄러에 의해 Ready Queue로 올라왔다고 가정하자

- CPU는 이 중 하나의 프로세스를 선택해서 실행해야 하는데 그것을 스케줄링 해주는 것이 단기 스케줄러

  (CPU 스케줄러라고도한다.)

- CPU 자원을 효율적으로 사용하기 위함이다.

- 사용자에게 여러개의 프로세스를 동시실행되고 있는 것 처럼 보이게 하기위해 아주 짧은 시간으로 쪼개서 스케줄링

- 또는 A프로세스를 실행하다가 I/O를 해야하면 이를 기다리는 시간동안 B프로세스를 올려서 작업한다.

- 매우 짧은 시간단위로 수행되므로 단기 스케줄러라고 한다.

4. 중기 스케줄러

- 너무 많은 프로세스가 메모리에 올라와있을 경우 이를 다시 디스크로 보낸다.

- CPU를 사용하려는 프로세스들 사이에서 중재하여 일시 보류, 재활성화를 수행한다. (swapper라고도 한다.)

- 일정시간 이상 CPU에서 수행되지 않았거나, 우선순위를 기준으로 판단하여 내려보낸다.

1. HTTP란?

- Hypert Text Transfer Protocol

- 80번 포트 사용

- 서버/클라이언트 모델을 따라 데이터를 주고받기 위한 프로토콜

- 암호화되지 않은 평문 데이터를 전송하는 프로토콜

- Application 레벨의 프로토콜이고, TCP/IP 위에서 작동

- Stateless 프로토콜

2. HTTPS란?

- Hyper Text Transfer Protocol Secure

- 443번 포트 사용

- 데이터 암호화가 추가된 프로토콜

- 공개키 암호화방식 사용

   (간단하게 말씀드리면 공개키 암호화방식에서는 공개키로 암호화, 개인키로 복호화는 암호화/복호화로 사용되고

     개인키로 암호화, 공개키로 복호화 하는 과정을 통해 자신이 작성한? 것임을 서명하는 용도로 사용)

- 통신과정

1) P기업은 HTTPS를 적용하기 위해 공개키/개인키를 발급한다.

2) CA(Certificate authority) 기업에 돈을 내고 공개키를 저장하는 인증서 발급을 요청(CA는 엄격하게 인증된 기업)

3) CA기업은 P기업의공개키 를 포함한 정보들을 기반으로 인증서를 생성하고, 이를 CA기업의 개인키로 암호화하여 P기업에 제공

4) P기업은 클라이언트(고객)에게 이 암호화된 인증서를 제공한다.

5) 브라우저는 CA기업의 공개키를 가지고 암호화된 인증서를 복호화한다. (브라우저는 인증된 CA기업의 공개키를 가지고 있음)

6) 5의과정을 통해 P기업의 공개키를 알게되었다.

7) P기업의 공개키로 데이터를 암호화해서 요청을 보낸다. (P기업의 개인키는 P기업만 알고있으므로 P기업만 요청을 확인가능하다., 중간에 제 3자는 이 암호화된 요청을 볼 수 없다.)

3. HTTP와 HTTPS의 장단점,활용

- HTTP는 보안에 취약, HTTPS는 안전하게 데이터를 주고 받을 수 있다.

- HTTPS는 암호화/복호화의 추가과정 때문에 시간이 더 소요된다고 하지만  요즘은 체감할 정도로 심하진 않다.

- CA기업 인증서 발급을 위한 추가비용 소모된다(HTTPS).

- 거의 대부분 HTTPS를 쓴다. 구글등의 검색포털에서 이를 권장하고 노출도 증가등의 이점이 있다

1. 멀티 프로세스

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

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

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

2. 멀티스레드

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

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

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

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

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

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

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

1. 풀이방법

- N개의 수중에 주어지는 M개의 수들이 각각 존재하는 지 확인해야합니다

- 선형탐색을 진행할 경우 O(N*M) 이므로 약 10,000,000,000 는 시간초과에 걸릴 것 같습니다.

- O(NlogN) 정렬 + O(M*logN) 이분탐색 으로 해결했습니다.

2. 주의사항

- 조건으로 인한 시간초과

3. 나의코드

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

int Narr[100000];
int N, M;
bool existnum(int target) {
	int ep = N - 1;
	int sp = 0;
	int mid;
	while (sp<=ep) {
		mid = (sp + ep) / 2;
		if (Narr[mid] == target) { return true; }
		else if (Narr[mid] < target) {
			sp = mid + 1;
		}
		else if (Narr[mid] > target) {
			ep = mid - 1;
		}
	}
	return false;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> Narr[i];
	}
	sort(Narr, Narr+N); //이분탐색을 위한 정렬
	cin >> M;
	int target;
	for (int i = 0; i < M; i++) {
		cin >> target;
		cout << existnum(target)<<"\n";
	}
	return 0;
}

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

1. 풀이방법

- N의 숫자의 범위가 큰편입니다.

- O(N^2)은 100,000,000 시간제한 0.5초에 타임리밋 걸릴 수 있습니다.

- 투포인터를 이용해 한번의 순회로 해결했습니다.

- 단, 이는 A[i]가 자연수 (음수 아님) 조건이 있기 때문에 사용할 수 있습니다.

2. 주의사항

- 문제 조건을 정확히 파악해야 합니다.

3. 나의코드

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

int N, M;
vector<long long> arr;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> N >> M;
	long long tt;
	for (int i = 0; i < N; i++) {
		cin >> tt;
		arr.push_back(tt);
	}
	int tmpsum = arr[0];
	int resultcount = 0;
	int sp = 0;
	int ep = 0;
	while (1) {
		if (tmpsum == M) {
			resultcount++;
			tmpsum -= arr[sp];
			sp++;
			ep++;
			if (ep == N) break;
			tmpsum += arr[ep];
		}
		else if (tmpsum < M) {
			ep++;
			if (ep == N) break;
			tmpsum += arr[ep];
		}
		else if (tmpsum > M) {
			tmpsum -= arr[sp];
			sp++;
		}
	}
	cout << resultcount;
	return 0;
}

"유닉스에서 모든 것은 파일이다" - 유닉스프로그래밍 수강하면서 기억나는 말... ㅋㅋㅋ

리눅스를 찬찬히 공부하며 다시 정리해봅니다

1. 리눅스 디렉토리 구조

- linux file system hierarchy standard가 존재.

- 제일 상단에 root filesystem(/)가 있는 트리구조.

2. 디렉토리 종류 및 역할

- /(root) : 최상위 디렉토리

- /bin (/usr/bin) : 리눅스 기본 명령어

- /sbin (/usr/sbin) : 리눅스 시스템 관리용 명령어

- /usr : 애플리케이션, 유틸리티 설치 디렉토리

- /etc : 시스템 설정파일

- /var : 비교적 변동이 잦은 파일 ( /var/log- 로그파일 존재 )

- /tmp : 임시디렉토리

- /proc : 메모리에서 동작중인 프로세스들 정보를 확인

- /sys : 시스템 하드웨어 정보나 가상 파일 시스템들

- /root : 시스템 최고 관리자인 root 사용자의 홈 디렉토리

- /home : 일반 사용자들의 홈 디렉토리 ( ubuntu가 보통 여기 존재 /home/ubuntu 익숙.....)

- /dev : 하드웨어 장치 파일

- /lib : 라이브러리

3. 기본적인 리눅스 명령어

- pwd : 현재 작업중인 디렉토리 [present working directory]

- cd : 디렉토리 이동 [change directory]

- ls : 위치한 디렉토리의 파일목록 표시 

- mkdir : 디렉토리 생성

- cp : 파일을 복사

- mv : 파일을 이동

- rm : 파일을 제거

- cat : 파일의 내용을 화면에 출력하거나 파일을 만드는 명령어 [ concatenate ]

- chmod : 권한 변경 (rwxrwxrwx)  

- touch : 파일이나 디렉토리의 최근 업데이트 일자를 현재시간으로 변경

- find : 특정 파일이나 디렉토리를 검색한다. [ find 경로  -name 파일명 ]

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

1. 풀이방법

- 최대 깊이가 500입니다.

- 모든 경우의 수를 모두 구하면 매우 커짐을 알 수 있습니다.

- 점화식을 세우고, 0과 i==j 일때 (한변에서 양 끝은 선택권이 한개씩 뿐) 처리를 따로 해주시면 됩니다.

- 바텀업 방식으로 작성했습니다.

2. 주의사항

- 없음

3. 나의코드

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

int triangle[500][500];
int dp[500][500];
int n;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < i + 1; j++) {
			cin >> triangle[i][j];
			dp[i][j] = -1;
		}
	}
	dp[0][0] = triangle[0][0];
	
	for (int i = 1; i < n; i++) {
		for (int j = 0; j < i + 1; j++) {
			if (j == 0) {
				dp[i][j] = dp[i - 1][j] + triangle[i][j];
			}
			else if (j == i) {
				dp[i][j] = dp[i - 1][j - 1] + triangle[i][j];
			}
			else {
				dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j];
			}
		}
	}
	int maxr = -1;
	for (int i = 0; i < n; i++) {
		maxr = max(dp[n - 1][i], maxr);
	}
	cout << maxr << "\n";
	return 0;
}

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

1. 풀이방법

- 최대값은 쉽습니다. 자릿수를 크게 하는 것이 가장 큰 값을 만드는 것입니다.

- 같은 성냥을 사용할 떄, 가장 작은 수를 쓰면 됩니다. 쉬우므로 생략하겠습니다.

- 최솟값이 어렵습니다.

- dp로 좀 더 쉽게 접근했고 오랜만에 dp하려니까 머리가 너무 안돌아갔습니다 ㅠㅠ

- makenum배열에 성냥으로 만드는 수를 넣어놓고, 바텀업으로 아래의 점화식과 같습니다.

- for (int i = 9; i < 101; i++) {
           dp[i] = dp[i - 2] * 10 + makenum[2]; //init 설정

               for (int j = 3; j < 8; j++) {
                    dp[i] = min(dp[i], dp[i - j] * 10 + makenum[j]);
                }
    }

2. 주의사항

- 0으로 시작하면 안된다.

- 그러므로 dp[6]은 6으로 초기화 하고 makenum[6]에는 0을 넣습니다.

- 즉 makenum[6]은 6 성냥으로 만들 수 있는 수 인데, 이후 점화식에서는 6개의 성냥으로는 0을 만들어 쓰겠다입니다

3. 나의코드

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

int T, n;
int makenum[9] = { 0, 0, 1, 7, 4, 2, 0, 8, 10 }; //일단 6은 0을 넣어놓자 (초기 값 셋팅 이후에는 6개 성냥으로는 0을 만들어야함)
long long dp[101];

void getmin() {
	for (int i = 1; i < 9; i++) {
		dp[i] = makenum[i]; // 성냥 i 개를 가지고 만들 수 있는 min값
	}
	dp[6] = 6; //0으로 시작하는 것을 방지하기 위해

	for (int i = 9; i < 101; i++) {
		dp[i] = dp[i - 2] * 10 + makenum[2]; //init 설정

		for (int j = 3; j < 8; j++) {
			dp[i] = min(dp[i], dp[i - j] * 10 + makenum[j]);
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int T,n;
	cin >> T;
	getmin();
	while (T--) {
		cin >> n;
		cout << dp[n];
		cout << " ";
		//가장 큰수
		if (n % 2 == 1) { //홀수
			cout << 7; n -= 3;
		}
		while (n != 0) {
			cout << 1; n -= 2;
		}
		cout << "\n";
	}
	return 0;
}