Coding Kitsune

FCFS (선착순 알고리즘) (비선점) => 도착시간을 기준으로 하며, 들어온 순서대로 일만하기 때문에 자원을 효율적으로 사용, 즉 스케줄링 오버헤드가 작다. 배치시스템(일괄처리)에 적합하며, interactive에는 부적합한 방식 RR (Round Robin) (선점) => 도착시간을 기준으로 하며, 자원 사용에 대한 제한시간(time quantum)이 있음. 제한시간이 지나면 자원을 반납해야하며, context switch 오버헤드가 크다. interactive 시스템에 적합하고, 제한시간이 성능을 결정하는 핵심 요소이다. SPN (Shortest process next) (비선점) ====> 변형된 것이 SRTN(선점)(잔여시간 추적) => 실행시간을 기준으로 대기 프로세스들 중 Burst time..

문제링크: https://www.acmicpc.net/problem/10866 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 풀이과정 : 덱이란 앞과 뒤 모두 삽입 삭제가 가능한 양방향 큐이다. 큐와 마찬가지로 핵심은 모든 연산이 시간복잡도 O(1)에서 끝나야한다.(O(n)은 시간초과..) 처음에는 데큐 없이 push_front를 짜려고 하니 고생하다가... 데큐를 쓰기로 결정..! 나머지는 풀이랄것 없이 저번에 했던 큐 구현과 거의 동일하다. #덱을 사용하고, 시간복잡도가 O(1)이어야함 i..

문제링크 : https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 풀이과정: 몇일전 자료구조 수업을 다시들으면서 큐와 요세푸스 개념을 들었기 때문에, 쉽게 해결될 것이라 생각하였는데, 시간초과 때문에 생각보다 꽤나 고전했다. 처음에 풀었던 풀이다. #처음 시도(시간초과) def josephus(N, K): answer = [] current = 0 lst = [i for i in range(1, N+1)] while len(lst[current:]) != 1: if (current+1)%K == 0: answer.append(str(lst[..

문제링크 : https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 풀이과정 : 이전문제였던 스택과 거의 동일한 방식으로, 결국 큐를 구현할 수 있느냐 묻는문제다. 자료구조 수업때 배웠던 대로 큐 클래스를 구현해서 풀까도 생각했지만, 그냥 남들처럼 포문안에 다 때려넣었다... ;ㅅ;... 다행히 원큐에 통과! 삽입하는건 스택과 동일한 방식이기 때문에 다른게 없을것이고, 디큐하는 부분이 포인트, 결국 큐 입장의 가장 앞을 가르키는 fro..

다중프로그래밍(Multi- Programming) 이란, 여러개의 프로세스가 시스템 내 존재하는 것이고, 이에 따라 자원을 할당할 프로세스를 선택해야한다. 이것이 스케쥴링의 기본적인 개념이다. 자원관리에는 (시간분할, 공간분할) 방식이 있는데, 프로세스 스케쥴링 시간분할에 속한다. 스케쥴링의 목적은 시스템의 성능 향상에 있다. 성능의 지표 응답시간 (response time) 작업처리량(throughput) 자원활용도(resource utilization) 이 지표중에서 목적에 맞는 것을 고려하여 스케쥴링 기법을 선택하면 된다. 또, 스케쥴링은 선점 스케쥴링(preemtive scheduling) 비선점 스케쥴링(Non-preemtive scheduling)로 나뉜다. 선점 스케쥴링은 도중에 우선순위가 ..

Jesephus problem은 이번에 배운 큐를 이용하여 풀 수 있는 대표적인 문제다. Joesphus(n, k) => n 총 인원 k => 몇번째 사람마다 제외할것인가 가령 Joesphus(5, 2)일때 5명 중 2번째 마다 제외해서 마지막에 누가 남는지 알아보는 것이다. 이때 [1, 2, 3, 4, 5] 큐를 만들어서 enqueue와 dequeue를 이용하여 풀어보자 [1, 2, 3, 4, 5] 1은 dequeue하고 바로 enqueue => [1, 2, 3, 4, 5, 1] 2는 해당되기 때문에 dequeue만 실행 => [1, 2, 3, 4, 5, 1] 3은 dequeue하고 바로 enqueue => [1, 2, 3, 4, 5, 1, 3] 4는 해당되기 때문에 dequeue만 실행 => [1, ..

순차적 자료 구조 중 Last In First Out에 대표적으로 Stack이 있었다면, First In First Out 자료 구조에는 큐(queue)가 있다. 먼저 들어온 구조가 리스트 front에 자리잡고 스택과 같이 차곡차곡 쌓이다가 pop될때 (큐에서는 dequeue 라고한다), front에 있는 자료가 나가는 구조이다. stack에서 배웠던 push가 enqueue, pop이 dequeue로 표현된다. 이 큐를 파이썬을 사용하여 클래스로 구현하면 다음과 같다. class Queue: def __init__(self): self.items = [] self.front_index = 0 def enqueue(self, value): #push와 같은 역할 self.items.append(value..

문제링크 : https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 풀이과정 : 처음에 하나의 스택안에 입력문자들을 받고, 커서를 가르키는 인덱스를 추적하면서, 상황에 따라 포문을 돌려가며 문제를 풀어서 비교적 간단하게 문제를 풀었는데.. 역시 시간초과가 떴다...! #시간초과 import sys lst = list(sys.stdin.readline().split()) cur_idx = len(lst) testcase = int(input()) for ..

문제링크 : https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 풀이과정: 문제를 이해하는것이 정말 어려웠다... 스택에 1,2,3......순서로 계속해서 쌓아두고 차례로 뽑아쓰는 개념이다. 문제 처럼 4, 3, 6, 8 순서로 이 스택에서 뽑아쓰고 싶다면 스택을 먼저 만든다. 스타트가 4이기 때문에 [1, 2, 3, 4] 의 수열을 만들고, 내가 원하는 숫자 4를..

[코딩테스트 준비] (백준) [Front-End 준비] (Online bootcamp) 그 외 DataStructure, OS강의 다시 들으면서 블로그에 정리 中 [2월 계획] Deep dive 모던 자바스크립트 학습 백준 30 문제 React online bootcamp 시작(2월말 예정) HTML+CSS로 만들었던 사이트들 JS로 반응형으로 만들기 포토폴리오 제작 프리미어 프로 연습