1. 운영체제가 뭐길래

• Operating System

  • a software that operates a computer system

• Computer

  • A machine that proccesses the informatin

• Information

  • Cladue Shannen

    • $$
      I(X) = - log_2{P(X)}
      $$

    • 정보의 양은 해당 정보의 확률의 로그를 취한것의 마이너스이다.

    • 정보 하나의 단위는 1bit이다.

  • A quantitative representation that measures the uncertainty

• 컴퓨터가 정보를 처리하는 법

  • 정보의 최소 단위 : bit(binary digit)
    • 8 bit = 1byte
  • 정보의 처리 : 정보의 상태 변환 (0에서 1로, 1에서 0으로)
  • 부울 대수(Boolean Algebra) : NOT, AND, OR
  • 논리 게이트 : NOT, AND, OR, XOR, NAND, NOR
  • 논리 회로 : IC,LSI,VLSI,ULSI,SoC...
    • 무어의 법칙, 황의 법칙
  • 정보의 저장과 전송 : 플립 - 플롭, 데이터 버스
  • 범용성 : universality
    • NOT,AND,OR 게이트 만으로 모든 계산을 할 수 있다.
    • NAND 게이트만으로 모든 계산을 할 수 있다.
    • 범용 컴퓨터 : general - purpose computer
  • 계산 가능성 : computability
    • Turing-computable : 튜링 머신으로 계산 가능한 것
    • 정지 문제 : Halting Problem : 튜링머신으로 풀수 없는 문제

• 튜링머신

• 컴퓨터의 구조와 튜링 머신의 구조가 비슷하다.

• 폰 노이만

  • A stored - program computer is
    • a computer that stores programs in memory

  

  • Instruction Set Architecture라 부른다

• 프로그램

  • A program is a set of instructions
    • that tells a computer's hardware to perform a task

• 운영체제

  • Operating System
    • is a program running at all times on the computer
    • to provide system services to application programs
    • to manage processes, resources, user interfaces and so on

1강 후기

기본적인 부분부터 알려주는 시간이었다 매일 1~2강씩 들으면서 정리해야겠다.

강의 주소

주니온 유튜브 운영체제 1강

import sys

sys.setrecursionlimit(1000)
def dfs(node,cnt):
    for next_node,val in enumerate(arr[node]):
        if val and visited[next_node] == 0:
            visited[next_node] = cnt
            dfs(next_node,cnt)





N = int(input())
M = int(input())
arr = [list(map(int,input().split())) for _ in range(N)]

tour_list = list(map(int,input().split()))

visited = [0]*N
cnt = 1
for i in range(N):
    if visited[i] == 0:
        visited[i] = cnt
        dfs(i,cnt)
        cnt += 1

result = 'YES'
init = visited[tour_list[0]-1]
for city in tour_list[1:]:
    if visited[city -1] != init:
        result = 'NO'
print(result)

첫 풀이 방식은 다음과 같았다.

DFS를 통해 모두 연결이 된대를 같은 cnt로 표시를 했다. 그런데 만약에 같은 cnt가 아니라면 tour_list에서 한번에 갈수 없는 곳 이므로 result를 No로 출력했다.

import sys
input = sys.stdin.readline

def union(A,B):
    x = find_parent(A)
    y = find_parent(B)
    if x > y:
        x,y = y,x
    make_set[y] = x
    for i in range(N+1):
        if make_set[i] != i:
            make_set[i] = find_parent(make_set[i])

def find_parent(ind):
    if make_set[ind] == ind:
        return ind
     
    return find_parent(make_set[ind])
N = int(input())
M = int(input())
edges = []
for i in range(N):
    graph_list = list(map(int,input().split()))
    for j in range(N):
        if graph_list[j] == 1:
            edges.append((i+1,j+1))

tour_list = list(map(int,input().split()))
make_set = [i for i in range(N+1)]

for edge in edges:
    node_a,node_b = edge
    if find_parent(node_a) != find_parent(node_b):
        union(node_a,node_b)

init_value = make_set[tour_list[0]]
result = 'YES'
for city in tour_list:
    if init_value != make_set[city]:
        result = 'NO'
        break
print(result)

좀 더 원론적인 union find를 해서 같은 집합인지 아닌지 판별을 했다.

그리고 난뒤에 같은 집합이 아니면 No를 출력하게 했다.

# 7576번 문제 
# 1은 익은 토마토 0은 익지않은 토마토

N,M = map(int,input().split())

tomatoarray = [list(map(int,input().split())) for _ in range(M)]

dx = [-1,1,0,0]
dy = [0,0,1,-1]
tomatocnt = 0
total = N*M
tomato = []
for x in range(M):
    for y in range(N):
        if tomatoarray[x][y] == 1:
            tomato.append((x,y))
            tomatocnt += 1
        elif tomatoarray[x][y] == -1:
            total -= 1
result = -1
day = 0
if total == tomatocnt:
    result = 0
else:
    while tomato:
        new_tomato = []
        for x,y in tomato:
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0<=nx<M and 0<=ny<N:
                    if not tomatoarray[nx][ny]:
                        tomatoarray[nx][ny] = 1
                        new_tomato.append((nx,ny))
                        tomatocnt += 1


        day += 1
        if tomatocnt == total:
            result = day
            break
        if len(new_tomato):
            tomato = [row[:] for row in new_tomato]
        else:
            result = -1
            break



print(result)

BFS를 활용해 day별로 새로 토마토가 된 곳을 찾아서 해주었다. 

N,K = map(int,input().split())

number =list(input())


result = [number[0]]
idx = 1
while K and idx <N:
    while result and K and number[idx] > result[-1]:
        result.pop()
        K -= 1
    result.append(number[idx])
    idx += 1
for _ in range(K):
    result.pop()
result = result + number[idx:]
print(''.join(result))

기본적인 원리는 다음과 같다.

반복문을 돌리면서 result에 마지막수보다 새로들어온 값이 클시에는 그 값들을 하나씩 빼준다. 그리고 난뒤 append를 해준다.

이렇게 끝까지 갔는데도, K가 남아있을시에는 남은 K만큼 pop을 해준다.

그리고, 만약 끝까지 가지 않았는데도, K만큼의 수를 이미 뺐다하면, 나머지 값들을 뒤에 붙여주면 된다.

N = int(input())
arr = list(map(int,input().split()))
LIS = [arr[0]]
parents = [-1]*N
parents[0] = 0
temp = 0
for i in range(1,len(arr)):
    if arr[i] > LIS[-1]:
        parents[i] = len(LIS)
        LIS.append(arr[i])
    else:
        start = 0
        end = len(LIS)
        idx = len(LIS)-1
        while start < end:
            mid = (start+end)//2
            if LIS[mid] >= arr[i]:
                idx = min(idx,mid)
                end = mid
            else:
                start = mid + 1
        LIS[idx] = arr[i]
        parents[i] = idx

LIS_CNT = len(LIS)
result = [-1]*LIS_CNT

for i in range(N-1,-1,-1):
    if parents[i] == LIS_CNT-1:
        result[LIS_CNT-1] = arr[i]
        LIS_CNT -= 1
print(len(result))
print(*result)
    
# https://jins-dev.tistory.com/entry/%EC%B5%9C%EC%A0%81%ED%99%94%EB%90%9C-LISLongest-Increasing-Subsequence-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EA%B3%BC-%ED%95%B4-%EC%B0%BE%EA%B8%B0

https://jins-dev.tistory.com/entry/%EC%B5%9C%EC%A0%81%ED%99%94%EB%90%9C-LISLongest-Increasing-Subsequence-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EA%B3%BC-%ED%95%B4-%EC%B0%BE%EA%B8%B0

위의 블로그를 참조해서 코드를 풀었다.

기본적인 원리는 다음과 같다. LIS를 구하면서 parents라는 배열에 해당 LIS에 들어갔던 idx를 저장해준다.

그리고 난뒤 마지막에 LIS의 크기에서부터 하나씩 내려가면서 그에 맞는 배열 값들을 찾아주면 된다.

from collections import deque
import sys
input = sys.stdin.readline

N,M,K = map(int,input().split())


AppendList = [list(map(int,input().split())) for _ in range(N)]
tree_info = [[[] for _ in range(N)] for _ in range(N)]
result = 0
forest = [[5]*N for _ in range(N)]

for _ in range(M):
    X,Y,age = map(int,input().split())
    tree_info[X-1][Y-1].append(age)
    result += 1

dx = [-1,-1,-1,0,0,1,1,1]
dy = [-1,0,1,-1,1,-1,0,1]
for year in range(K):

    for x in range(N):
        for y in range(N):
            if len(tree_info[x][y])>0:
                temp = []
                summer_forest = 0
                cnt = 0
                limited = len(tree_info[x][y])
                while cnt < limited:
                    age = tree_info[x][y].pop()

                    if forest[x][y] >= age:
                        forest[x][y] -= age
                        temp.append(age+1)
                    else:
                        summer_forest += (age//2)
                        result -= 1
                    cnt += 1
                temp.sort(reverse=True)
                tree_info[x][y].extend(temp)
                forest[x][y] += summer_forest
            forest[x][y] += AppendList[x][y]
    for x in range(N):
        for y in range(N):
            spread_cnt = 0
            if tree_info[x][y]:
                for val in tree_info[x][y]:
                    if val%5 == 0:
                        spread_cnt += 1

            if spread_cnt:
                for i in range(8):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if 0<=nx<N and 0<=ny<N:
                        result += spread_cnt
                        tree_info[nx][ny].extend([1]*spread_cnt)
print(result)

 구현을 하는 문제인데, 문제에 주어진 조건대로 면 된다. 문제는 시간초과의 벽이 너무 컸다. 시간초과가 나지 않도록 최대한 문제에 주어진 조건을 한번에 구현할수 있도록 하는게 중요했다.

import sys
input = sys.stdin.readline
N,M,K  = map(int,input().split())
store = [list(map(int,input().split())) for _ in range(N)]
tree_info = [[{} for _ in range(N)] for _ in range(N)]
forest = [[5]*N for _ in range(N)]

tree_cnt = 0
for _ in range(M):
    x,y,age = map(int,input().split())
    tree_info[x-1][y-1][age] = 1
    tree_cnt += 1

dx = [-1,-1,-1,0,0,1,1,1]
dy = [-1,0,1,-1,1,-1,0,1]

for _ in range(K):
    for x in range(N):
        for y in range(N):
            if tree_info[x][y]:
                summer_forest = 0
                new_dict = {}

                for age in sorted(tree_info[x][y].keys()):
                    if forest[x][y] >= age * tree_info[x][y][age]:
                        forest[x][y] -= age * tree_info[x][y][age]
                        new_dict[age+1] = tree_info[x][y][age]
                    else:
                        if forest[x][y] // age:
                            new_dict[age+1] = forest[x][y]//age
                            forest[x][y] -=  age*new_dict[age+1]
                            if tree_info[x][y][age] - new_dict[age+1]:
                                summer_forest += (age//2) * (tree_info[x][y][age] - new_dict[age+1])
                                tree_cnt -= (tree_info[x][y][age] - new_dict[age+1])
                        else:
                            summer_forest += (age//2)*tree_info[x][y][age]
                            tree_cnt -= tree_info[x][y][age]
                tree_info[x][y] = new_dict
                forest[x][y] += summer_forest
            forest[x][y] += store[x][y]
    for x in range(N):
        for y in range(N):
            spread_cnt = 0
            for age in tree_info[x][y]:
                if not age%5:
                    spread_cnt += tree_info[x][y][age]
            if spread_cnt:
                for i in range(8):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if 0 <= nx <N and 0<=ny<N:
                        if tree_info[nx][ny].get(1):
                            tree_info[nx][ny][1] += spread_cnt
                        else:
                            tree_info[nx][ny][1] = spread_cnt
                        tree_cnt += spread_cnt
print(tree_cnt)

import heapq
import sys

input = sys.stdin.readline
N = int(input())
arr = []
for _ in range(N):
    temp = list(map(int,input().split()))
    for number in temp:
        heapq.heappush(arr,number)
    while len(arr) > N:
        heapq.heappop(arr)



result = heapq.heappop(arr)
print(result)

문제의 조건 중 N이 1500이라서 전부 arr에 저장을 하면 메모리가 부족할 가능성이 있다.

그래서 arr의 크기를 N으로 고정시켜놓고 그보다 클시에는 pop을 해주는 방식으로 했다.

import heapq
import sys

input = sys.stdin.readline

N = int(input())
arr = []

for i in range(N):
    input_list = map(int,input().split())
    if i == 0 :
        for number in input_list:
            heapq.heappush(arr,number)
    else:
        for number in input_list:
            if number > arr[0]:
                heapq.heappushpop(arr,number)
big_list = heapq.nlargest(N,arr)
print(big_list[N-1])

 두번째 방식은 heapq의 기능을 좀 더 잘 쓰는것이다.

heappushpop을 하면 heapop을 하고 heappush를 하는 것보다 더 빠르다.

이걸 이용해서 위와 같이 똑같이 해주고,

마지막에는 전체 arr 중에서 N개의 큰 수 만을 뽑아내는 methods를 활용해준다.

# stkang9409 풀이 해석

def find_max_value(x):
    return arr[max_row_list[x]][x]

import sys

input = sys.stdin.readline


N = int(input())
arr = [list(map(int,input().split())) for _ in range(N)]

max_row_list = [N-1]*N
# 각 열마다 가장 큰 값은 N-1번 행에 있는 값이다.
# 매번 돌면서 각 열마다 가장 큰값들을 비교해, 가장 큰 값이 있는 열의 index 값을 하나씩 줄여나간다.
# 그렇게 하면 마지막 N번째에 가장 큰 값을 가지는 열의 값이 N번째로 큰 수의 열값이 되고
# 그 때 저장된 위치의 값이 행이된다.
for cnt in range(N):
    max_col_index = 0
    for col in range(N):
        max_col_index = max(col,max_col_index,key= find_max_value)
    if cnt == N-1:
        print(arr[max_row_list[max_col_index]][max_col_index])
    max_row_list[max_col_index] -= 1

다른 분의 풀이를 해석한 것으로, 문제의 조건을 활용해서 하는 방식이다.

각 열의 값은 다음 행의 값보다는 작다는 점을 이용해,

N번을 반복하면서 가장 큰 값들이 위치한 col의 row값을 하나씩 줄여주는 방식이다.

N = int(input())
K = int(input())
ST,EN = 1,K
while ST<=EN:
    mid = (ST+EN)//2
    cnt = 0
    for i in range(1,N+1):
        cnt += min(mid//i,N)

    if cnt < K:
        ST = mid + 1
    else:
        EN = mid -1

print(ST)

코드는 간단하지만 어려운 문제였다.

기본적인 원리는 이러하다. 

N*N 행렬이 있고, 그 안의 값은 해당 row index와 col index의 곱이 된다.

그렇다면 해당 줄에서 주어진 값 X보다 작은 값은 row_index로 나눈 몫일것이다.

만약 N = 5 이고 주어진 X가 12라면,

1행 : 1,2,3,4,5

2행 : 2,4,6,8,10

3행 : 3,6,9,12,15

4행 : 4,8,12,16,20

5행 : 5,10,15,20,25

이다. 이럴때 12보다 작은 값들은 1행에 5개, 2행에 5개 3행에 4개 4행에 3개 5행에 2개이다.

즉 12를 row의 index로 나눈 몫과 동일하다.

이를 통해, cnt가 K개가 될수 있는 X를 찾아주면 된다.

그리고 초기 값의 END가 K인 이유는 K번째 수는 K보다 작거나 같기 때문이다.