전체 글

    운영체제 · 프로세스, 스레드

    프로세스와 스레드의 차이점 ✓ 프로세스 : 운영체제로부터 자원을 할당받는 작업의 단위✓ 스레드 : 프로세스가 할당받은 자원을 이용하는 실행의 단위 프로세스 (Process) ✓ 정의 : 실행 중인 프로그램에 대한 인스턴스✓ 프로세스는 운영체제로부터 각각 독립된 자원(code, data, stack, heap, PC register 등)을 할당받는다.✓ 각 프로세스는 최소 1개 이상의 쓰레드를 가지고 있다.✓ 다른 프로세스의 자원에 접근하려면, 프로세스 간 통신(IPC)을 이용해야 한다. ✓ 프로세스와 프로그램의 차이프로그램 : Passive entity, 명령어 리스트를 지닌 실행 파일 클래스프로세스 : Active entity, 메모리에 적재되어 프로그램 카운터와 자원을 가진 인스턴스 스레드 (Thre..

    운영체제 · 운영체제 개념

    운영체제 (OS, Operating System) ✓ 정의 : 컴퓨터 시스템의 자원들을 효율적으로 관리하고, 사용자가 컴퓨터를 편리하게 사용할 수 있도록 환경을 제공하는 것✓ 종류 : Unix, Linux, MS-DOS, Windows, macOS 등 ✓ 운영체제의 역할하드웨어와 사용자 간의 인터페이스 제공 (CUI, GUI 등)프로세스 처리 및 스케줄링CPU, 입출력장치, 파일 등의 자원 관리하드웨어, 네트워크 제어 등 다양한 역할 수행 운영체제의 목적 ✓ 처리 능력(Throughput) 향상 : 처리 능력이란 일정 시간 내에 처리할 수 있는 작업량을 뜻하며, 시스템 전체의 생산성을 측정하는 단위이다.✓ 응답 시간(Turn Around Time) 단축 : 응답 시간이란 사용자가 처리를 요구한 시점부터 ..

    BOJ 17144 · 미세먼지 안녕!

    알고리즘 분류 : 시뮬레이션 문제에 주어진 조건을 그대로 구현하는 문제다. 크게 두 단계로 나눠서 설계해야 한다. 첫 번째, 미세먼지가 확산되는 과정, 두 번째 공기청정기의 바람이 순환하는 과정이다. 1. 모든 미세먼지는 5 이상의 양이 남아있으면, 상하좌우로 확산할 수 있다.확산할 때 상하좌우에 이미 먼지가 있는 경우가 있으므로, 별도의 배열을 만들어서 확산되는 먼지의 양을 저장해야 한다. 값을 바로 업데이트하면 다음 먼지 확산에 영향을 주기 때문에, 이 과정이 필요하다.현재 먼지의 양을 5로 나눈 후, 그 양을 상하좌우 칸에 더한다. 위에서 만든 별도의 배열 B에 더한다.모든 과정이 끝나면, 원래 먼지 배열 A에 확산 배열 B 값을 업데이트한다. 2. 미세먼지가 바람 방향에 따라 순환한다.입력받을 때..

    BOJ 17143 · 낚시왕

    알고리즘 분류 : 시뮬레이션 문제에 주어진 조건을 그대로 구현해야 하는 문제다. 크게 두 단계로 나눠서 설계해야 한다. 첫 번째, 낚시왕이 움직인 후 상어를 낚는 과정, 두 번째, 모든 상어가 제각기 움직이면서 서로를 잡아먹는 과정이다. 1. 낚시왕은 매 턴마다 한 칸 움직인 후, 상어 한 마리를 낚는다.먼저 낚시왕이 한 칸 앞으로 이동한다. 낚시왕은 최대 R(열의 개수)번 움직일 수 있다.도착한 열에서 땅에 가장 가까운 상어 한 마리를 낚는다. 땅에 가장 가까운 상어는 0에 가까운 행(C)에 위치한다. 2. 상어가 제각기 주어진 속도와 방향에 따라 움직이고, 자신보다 작은 상어를 잡아먹는다.상어의 속도는 움직일 수 있는 칸의 개수를 의미한다. 가장자리에 도달하면 방향을 바꿔서 남은 횟수만큼 움직여야 한..

    BOJ 17142 · 연구소 3

    알고리즘 분류 : BFS, 브루트 포스 연구소에 바이러스를 퍼트리는 데 걸리는 최소 시간을 구하는 문제다. 바이러스를 놓을 수 있는 경우를 모두 만든 후, 각 케이스에 대해 BFS로 바이러스를 퍼트려서 최솟값을 구하면 된다. BOJ 17141번 '연구소 2'와 거의 동일한 문제이다. 일부 값만 수정하면 된다. 연구소의 사이즈는 N이며, 바이러스의 개수는 M이다.바이러스를 놓을 수 있는 칸(2)의 좌표를 별도의 리스트 V에 저장한다.빈칸(0)의 개수를 모두 세고, 이를 K라 하자. 이 값은 바이러스를 퍼트려야 하는 칸의 총개수가 된다.조합(combination) 방법을 통해 M개의 바이러스를 바이러스 칸(2)에 둔다. 이때 리스트 V를 활용하여, 바이러스를 놓은 칸의 좌표를 큐에 모두 집어넣는다.BFS를 ..

    BOJ 17141 · 연구소 2

    알고리즘 분류 : BFS, 브루트 포스 연구소에 바이러스를 퍼트리는 데 걸리는 최소 시간을 구하는 문제다. 바이러스를 놓을 수 있는 경우를 모두 만든 후, 각 케이스에 대해 BFS로 바이러스를 퍼트려서 최솟값을 구하면 된다. 연구소의 사이즈는 N이며, 바이러스의 개수는 M이다.바이러스를 놓을 수 있는 칸(2)의 좌표를 별도의 리스트 V에 저장한다.빈칸(0)의 개수를 모두 세고, 여기에 바이러스를 놓을 수 있는 칸(2)의 개수를 더한 후, M을 뺀다. 이 값은 바이러스를 퍼트려야 하는 칸의 총개수가 된다. 이를 K라 하자.조합(combination) 방법을 통해 M개의 바이러스를 바이러스 칸(2)에 둔다. 이때 리스트 V를 활용하여, 바이러스를 놓은 칸의 좌표를 큐에 모두 집어넣는다.BFS를 통해 바이러스..

    BOJ 17140 · 이차원 배열과 연산

    알고리즘 분류 : 시뮬레이션 문제에 주어진 조건을 그대로 구현하는 문제다. 여러 개의 변수를 가진 구조체(또는 벡터)를 정렬해야 한다. 연산자 오버로딩을 통해 우선순위를 구현하거나, STL pair를 사용하면 된다. 정렬 대신, 우선순위 큐를 사용할 수 있다. 행의 최대 사이즈를 N, 열의 최대 사이즈를 M이라고 하자.이 문제는 N >= M일 때 각 행을 정렬하고, N < M일 때 각 열을 정렬한다.정렬의 우선순위는 1) 수의 등장 횟수, 2) 해당 숫자이며, 오름차순으로 정렬한다.수의 등장 횟수는 별도의 카운터 배열을 만들어서 해당 숫자가 얼마나 등장하는지 센다.배열에 값이 들어갈 때는 숫자가 먼저 들어가며, 그다음으로 수의 등장 횟수가 들어간다.정렬 연산이 수행되면, 행 또는 열이 커질 수 있다. 커..

    BOJ 17069 · 파이프 옮기기 2

    알고리즘 분류 : 다이나믹 프로그래밍 파이프를 옮겨서 한쪽 끝을 (N, N)으로 이동시키는 방법의 개수를 구해야 한다. BOJ 17070번 '파이프 옮기기 1'이 업그레이드된 문제이다. N의 범위가 최대 32로 증가했다. 하지만 시간제한은 0.5초로 줄어들었으므로, 백트래킹으로 구현할 수 없다. 때문에 이 문제는 DP를 이용하여 구현해야 한다. DP로 구현하면 1번 문제도 해결할 수 있다. 파이프의 상태는 3가지로 나눌 수 있다. 1. 가로로 놓여있는 상태 (0) : 가로(0) → 가로(0) 또는 대각선(2)2. 세로로 놓여있는 상태 (1) : 세로(1) → 세로(1) 또는 대각선(2)3. 대각선으로 놓여있는 상태 (2) : 대각선(2) → 가로(0) 또는 세로(1) 또는 대각선(2) D[M][X][Y]..