내 잡다한 노트

프로세스와 프로그램의 차이점 프로그램은 PCB(프로세스 제어 블록)을 받지 않은 상태이고 메모리에 올라가지 않은 것을 뜻한다. 프로세스는 PCB를 받아 메모리에 올라간 상태를 말한다. 프로그램은 정적이고, 프로세스는 동적인 것이다. 프로세스의 다섯가지 상태 생성 -> 준비 -> 실행 -> 완료 -> 대기 생성은 프로그램을 메모리에 올려 PCB를 준 상태이다. 그렇게 되면 준비상태로 가게 된다. 준비 상태에서는 준비 큐가 있어 CPU 스케쥴링의 선택을 기다리며 준비한다. 각각의 프로세스들은 우선순위가 존재해 그 우선순위에 따라 CPU 스케쥴링은 선택을 하게 된다. 선택을 받으면 CPU가 프로세스를 실행시키게 된다. 이때 프로세스들은 타임 슬라이스를 받고 주어진 시간동안 실행을 하지 못하면 다시 준비상태로 ..

구현, 시뮬레이션 문제이다. board에는 deque를 기본값으로 둬서 상어가 해당 자리에 들어갈 수 있게 했다. 상어가 움직이는 것은 사이클을 구하려 했는데 못구해서 맨 끝으로 갈 수 있는지를 확인하고 갈 수 있다면 방향을 바꿔주고 맨끝으로 한번에 이동하는 과정을 반복하도록 했다. 처음엔 2번 틀렸었는데 그 이유가 상어가 다른 상어를 잡아먹을때 shark 리스트에서 제거도 했어야했는데 remove를 안해서 좀비 상어가 발생했었다...ㅎ # 소스코드 from collections import deque r, c, numShark = map(int, input().split()) shark = [] fishing_board = [[deque() for _ in range(c)] for _ in range(..

# 문제 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 유니온-파인드 알고리즘을 사용하는 기본 문제이다. 기본 문제라 굉장히 쉽다. 노드 수가 최대 100만개라 좀 걱정이 됐는데 유니온 파인드 알고리즘의 시간복잡도는 높이와 관련이 있어서 그런지 해결이 됐다. 유니온은 합치는 것. 즉 노드들을 연결시키는 것 파인드는 루트 노드를 찾아 루트 노드가 같은지 확인을 해 두 노드가 같은 노드 집합에 속해있는지 ..

# 정의 해시테이블은 해시함수를 이용하여 키를 해시값으로 매핑하고 이 해시값을 인덱스삼아 데이터를 key와 함께 저장하는 자료구조이다. # 해시함수 해시 함수의 정의는 key를 고정된 길이의 hash로 변경해주는 역할을 한다. 이 과정을 해싱이라고 한다. key ---(해시함수)---> 해시 해시는 저장위치 즉 인덱스가 된다. # 해시테이블 구성 key : 해쉬 함수의 input이고, key를 그대로 인덱스로 사용할 경우에는 key의 길이만큼의 정보를 저장해야하는 공간도 따로 마련해야 해서 고정된 길이의 해시로 변경하는 것이다. 해시 함수 : key를 고정된 길이의 해시로 변경해주는 역할을 한다. 서로 다른 key가 해싱후 같은 해시 값이 나오는 경우가 있다. 이를 해시충돌이라고 한다. 이 충돌이 안나올..

운영체제에서 명령어를 처리할 때 하나씩만 하면 효율이 떨어지므로 여러개를 동시에 처리함으로써 빠르게 데이터를 처리할 수 있는 방식. 여러개의 명령을 동시에 처리하는 병렬 처리는 코어가 여러개인 cpu는 물론이고 코어가 하나인 CPU에서도 가능하다. 한 주방에서 여러 개의 볶음밥을 동시에 조리하는 것을 CPU의 사양에 비유하면 하나의 코어에 여러 개의 스레드를 이용하는 방식과 같다. 이러한 방식을 파이프라인 기법이라고 부른다. 스레드는 CPU가 처리할 수 있는 작업의 단위이다. 여러 개의 스레드를 동시에 처리하는 방법을 멀티스레드라고 한다. 병렬처리 시 주의 사항 A작업에 B를 먼저 해야한다면 B가 끝날때까지 A는 할 수 없기 때문. 상호 의존성이 없어야 병렬처리가 가능하다. 시간을 거의 일정하게 맞추어야..

현대 컴퓨터 구조의 가장 큰 문제는 cpu와 메모리, 주변장치의 작업 속도가 다르다는 것이다. cpu내에는 cpu 내부 버스가 따로 있고 cpu와 메모리, 주변장치들을 연결시켜주는 시스템 버스는 느려서 cpu 내부 버스와 속도가 다르다. 이걸 해결하기 위한 운영체제와 관련되 기술들이 존재한다. 버퍼 데이터를 가져올 때 하나씩 전송하면 느리다. 하지만 일정량의 데이터를 모아 한꺼번에 보낸다면 적은 노력으로도 많은 양의 데이터를 전송할 수 있게 된다. 그렇게 해주는 장치가 버퍼이다. 하드디스크에서 버퍼를 사용한다. ex) 동영상 버퍼링. 내용을 한꺼번에 보내 사용자가 영상을 보는게 끊기지 않도록 도와준다. 스풀cpu와 입출력장치가 독립적으로 동작하도록 고안된 소프트웨어적인 버퍼이다.대표적인 예로 프린터에 사..

트리가 존재할 때, 해당 노드의 N번째 앞에 있는 조상노드를 빠르게 찾기 위해 사용하는 알고리즘이다. (그래프에서도 사용할 수 있기는 하는 것 같다.) 기본 아이디어는 2의 N제곱으로 조상 노드를 log만큼 이동하는 것이다. 그래서 O(logN) 만에 N번째 조상 노드를 찾아갈 수 있다. 여기서 N이 0일때는 부모 노드를 가리킨다. 보통 2차원 배열로 표현을 한다. parent [logn+1][n+1] 크기로 만든다. 각 노드들의 부모 노드들은 0번 이동한 것이니 parent[0][i] 노드에 부모 노드들을 넣어준다. i번 노드의 2^0번째 부모노드니 바로 위의 부모 노드가 될 것이다. for i in range(1, logn+1): # 2^i번 부모 노드 for j in range(1, n+1): # ..

CPU란 컴퓨터의 두뇌로 모든 것들을 총괄한다. cpu안에도 여러 기능을 하는 것들이 존재하는데 레지스터와 연산장치, 제어장치 등이 존재한다. 레지스터 명령어를 읽고 그 명령어대로 동작하는데 거기엔 메모리를 활용하는 경우도 있다. 그 메모리에서 꺼내온 데이터를 잠시 저장하거나 활용을 하는 곳이 레지스터이다. 즉, CPU 내부에서 임시로 데이터를 저장하는 곳이다. 제어장치 cpu의 논리들을 제어하는 장치 연산장치 덧셈 뺄셈과 같은 사칙연산과 논리연산을 수행하는 장치 레지스터의 종류 주소레지스터 어떤 데이터의 주소를 저장하는 레지스터 데이터레지스터 데이터 값을 저장하는 레지스터 프로그램 카운터 다음에 이루어질 명령어의 주소를 저장하는 레지스터 명령어 레지스터 현재 작동중인 명령어의를 저장하는 레지스터 메모리..