포시코딩

알고리즘에서 logN의 밑은 2이므로 만약 N이 10억이라고 할 때, N = 10억 = 10^9 log2N = log2(10^9)가 된다. 이건 다시 9log2(10)이 되는데 log2(10)은 3.3정도로 생각하면 되므로 9*3.3 = 약 30이라는 결과를 얻을 수 있다. 만약 문제가 MlogN의 시간복잡도를 요구하는데 M이 200,000이었을 경우 MlogN = 20만 * 30 = 6,000,000이 된다. 메모리 사용량은 1000 = 1KB. 1,000,000 = 1MB가 되므로 MlogN의 메모리 사용량은 약 6MB가 된다는 것을 알 수 있다.

키워드 cpu scheduling, cpu burst, i/o burst, i/o-bound process, cpu-bound process, cpu scheduler, dispatcher, nonpreemptive, preemptive CPU Scheduling CPU burst: CPU만 연속적으로 쓰는 단계 I/O burst: I/O만 연속적으로 쓰는 단계 어떤 프로그램이든 프로그램이 실행된다는 것은 CPU burst와 I/O burst를 반복하며 실행된다. 컴퓨터 안에는 똑같은 종류의 프로그램이 있는게 아니라 아래의 종류가 섞여있음 CPU를 짧게 쓰고 중간에 I/O 작업이 들어오는 작업을 I/O bound job이라 함 CPU를 굉장히 오랫동안 쓰는 작업을 CPU bound job이라 함 이렇게 ..

키워드 fork, exec, wait, exit, 시스템 콜, 협력, IPC, message passing fork() 시스템 콜 부모 프로세스가 코드를 실행하다 fork()를 만나면 자식 프로세스가 생성됨 부모 프로세스는 이어서 밑의 코드 계속 실행 자식 프로세스는 새롭게 만들어졌지만 메인 함수의 처음부터 실행하는게 아니라 fork()를 실행한 그 이후부터 실행 부모 프로세스의 문맥(컨텍스트)를 그대로 복사하기 때문에 PC가 가리키는 곳 그대로 복사되어 fork()가 끝나는 시점부터 실행 ex) 한 사람이 복제되면 애기를 낳는게 아니라 똑같이 생긴 사람이 하나 만들어진다고 생각 만약 자식 프로세스가 원본이라고 주장하거나, 제어 흐름이 같은 경우를 대비해 부모와 자식을 구분해야 함 -> 부모 프로세스는 ..

키워드 프로세스 생성, 프로세스 종료 프로세스 생성 직접 생성하지 않고 운영체제를 통해 생성한다. (시스템 콜) 부모 프로세스가 자식 프로세스 생성(복제 생성) 복제? -> 프로세스의 문맥을 모두 복제. 즉, 부모 프로세스의 주소 공간(메모리)인 code, data, stack을 그대로 복사해서 자식 프로세스를 만듦 또한, 부모 프로세스의 cpu 문맥(인스트럭션을 어디까지 수행했는가)을 나타내는 레지스터인 PC(Program Counter) 레지스터도 부모 것 그대로 복제 프로세스의 트리(계층 구조) 형성 프로세스는 자원을 필요로 함 운영체제로부터 받음 부모와 공유 자원의 공유 부모와 자식이 모든 자원을 공유하는 모델 리눅스나 일부 모델에선 자식 프로세스 생성 시 카피 전에 공유할 수 있는 건 일단 공유..

https://www.acmicpc.net/problem/2747 2747번: 피보나치 수 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net https://www.acmicpc.net/p..

문제 https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 코드 N, r, c = map(int, input().split()) def z(n, x, y): global result if n == 2: if x == r and y == c: print(result) return result += 1 if x == r and y+1 == c: print(result) return result += 1 if x+1 == r and y == c:..

개요 재귀 호출 시 반복되는 작업에 대한 결과를 계속 반복 수행하는게 아닌 따로 저장해놓고(캐싱) 갖다 쓰는 방법을 다이나믹 프로그래밍이라 한다. 문제 https://www.acmicpc.net/problem/2747 2747번: 피보나치 수 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 한 예로 위 문제에 대해 재귀 함수를 사용한다면 금방 제시되는 입/출력을 구현해낼 수 있을 것이다. 하지만 그대로 코드를 제출하면 시간 초과가 나온다. 코드 1 n = int(input()) def recursio..

키워드 thread, 스레드 Thread(스레드) 프로세스 내부의 CPU 수행 단위가 여러 개 있는 경우 프로세스 하나에 CPU 수행 단위만 여러 개 두고 있는 것을 스레드라 부름 "A thread (or lightweight process) is a basic unit of CPU utilization" 구성 스레드가 독립적으로 가지는 부분 program counter register set stack space thread 끼리 공유하는 부분(=task) code section data section OS resources 전통적인 개념의 heavyweight process는 하나의 스레드를 가지고 있는 task로 볼 수 있다. 장점 하나의 프로세스 안에 스레드를 여러 개 두게 되면 스레드 하나가 b..

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net https://www.acmicpc.net/problem/16..