one Book a Day

CPU Scheduling 스케줄링 실행준비가 된 프로세스 중에서 하나를 선택해 CPU를 할당 하는 것. 결국 CPU를 잘 사용하기 위해 프로세스를 잘 배정하기 위함. 조건 : 오버헤드는 낮고, 사용률은 높고, 기아 현상은 낮을때. 목표 Batch System : 가능하면 많은 일을 수행한다. 시간(time)보다 처리량(throughout)이 중요하다. Interactive System : 빠른 응답 시간, 적은 대기 시간 Real-time System : 기한(deadline) 맞추기 선점 / 비선점 스케줄링 선점(preemptive) : OS가 CPU의 사용권을 선점 할 수 있는 경우, 강제 회수하는 경우 비선점(nonpreemptive) : 프로세스 종료 or I/O 등의 이벤트가 있을 때까지 실행..

분기있는 bfs. 벽을 뿌순 횟수에 따라 분기를 나눠준다. import sys input = sys.stdin.readline from collections import deque def bfs(x,y): queue = deque() queue.append([x,y,0]) visited = [[[0]*(K+1) for _ in range(M)] for _ in range(N)] visited[x][y][0] = 1 while queue: x,y,b_cnt = queue.popleft() if x==N-1 and y==M-1: return visited[x][y][b_cnt] for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0

다익쓰 다익써야한느 이유는 최소 거리로 갱신시키면서 가야 최대한 멀리 갈 수 있기 때문. import sys input = sys.stdin.readline from heapq import heappop,heappush def dijkstra(start): heap = [] heappush(heap,[start,0]) visited = {i: float('inf') for i in range(1,n+1)} visited[start] = 0 item_check = {i: False for i in range(1,n+1)} item_check[start] = True item_cnt = items[start] while heap: cur_node, total_dist = heappop(heap) for ne..

그냥 방향 바뀌는 부분만 체크해주면 댄당 import sys input = sys.stdin.readline N = int(input()) maps = input() cnt = 1 for i in range(1,N): if maps[i]=='E': if maps[i-1]=='W': cnt +=1 print(cnt)

라인스위핑 스위핑 알고리즘이란? 특정 선이나 공간을 한쪽에서부터 쓸어버리는 식의 알고리즘. 일정 좌표, 축기준 정렬 한 뒤 일정 시점의 좌우 가장 가까운 두 점사이의 거리보다 멀리떨어진 점은 조사하지 않는 방식. 가지치기를 하겠다는 이야기다.(O(NlogN)) 아래는 2261번 문제에 대한 분할정복 풀이. import sys input=sys.stdin.readline INF=sys.maxsize # 두 점 사이의 거리를 구하는 함수 def dist(a,b): return (a[0]-b[0])**2+(a[1]-b[1])**2 def divide(start,end): # 점 하나면 버림 if start==end: return INF # 점 두개면 거리구해서 리턴 elif end-start==1: retur..

Trie(트라이) = radix tree = prefix tree = digital search tree 탐색이라는 뜻의 retrieval에서 trie를 따온 것. 문자열 집합을 표현하는 트리 자료구조. 하나하나 비교가 아닌 key로 노드를 탐색. 원하는 원소를 찾는 작업을 O(M)에 해결 이진트리는 O(logN)*문자열의 길이 M => O(MlogN) 빠르지만 저장공간의 크기가 매우 크다.(자식들의 포인터를 모두 배열로 저장하고 있기때문.) 문자열 검색 문제에서 입력되는 문자열이 많을 경우 사용. 적용되는 기능. 검색엔진 사이트에서 제공하는 자동완성 및 검색어 추천기능에서 Trie 알고리즘 사용. 맞춤법 검사, IP라우팅 (라우터에서 packet을 포워딩해줄때 다음 라우터로 경로를 결정하기 위해 패킷의..

장고 생활코딩 장고 템플릿 문법. {% extends "base_generic.html" %} {% block title %}{{ section.title }}{% endblock %} {% block content %} {{ section.title }} {% for story in story_list %} {{ story.headline|upper }} {{ story.tease|truncatewords:"100" }} {% endfor %} {% endblock %} {{}}두개는 변수. 뷰에서 탬플릿으로 context전달이 가능하다. 함수에서 html문서로 객체의 전달이 가능하다. sectin.title은 뷰에서section이라는 객체를 html문서로 보냈다는 뜻이고 그 안에 title속성을 전달..

자바 스크립트 30개 미니 프로젝트 만들기 - 1 Drum Kit JS 30개 프로젝트 만들기. Wes Bos님 강의 Drum Kit data key값으로 오디오를 불러오는 것이 핵심. key와 audio에 대해 각 event 속성을 불러 control event를 트리거로 classList를 통해 class를 추가, 제거시키므로써 입력에 대한 제어를 가능케 함. const div = document.createElement('div'); div.className = 'foo'; // our starting state: console.log(div.outerHTML); // use the classList API to remove and add classes div.classList.remove("foo..

유니온 파인드. 정순, 역순으로 오르막길 포함된 갯수 파악해서 연산. import sys input = sys.stdin.readline def find(x): if parent[x] == x: return x parent[x] = find(parent[x]) return parent[x] def union(a,b): a = find(a) b = find(b) if level[a] >= level[b]: parent[b] = a if level[a]==level[b]: level[a] +=1 else: parent[a] = b N, M = map(int, input().split()) parent = {i:i for i in range(N+1)} level = {i:0 for i in range(N+1)..

오랜만에 직사각형 누적합 import sys input = sys.stdin.readline N, M = map(int, input().split()) areas = [list(map(int, input().split())) for _ in range(N)] K = int(input()) dp = [[0 for _ in range(M+1)] for _ in range(N+1)] dp[1][1] = areas[0][0] for i in range(1,N+1): for j in range(1,M+1): dp[i][j] = dp[i-1][j] + dp[i][j-1] + areas[i-1][j-1] - dp[i-1][j-1] for _ in range(K): x1,y1,x2,y2 = map(int, input(..