Coding Kitsune

원래 수열을 [0] * N 으로 초기화 시킨 뒤, 정렬이 되어있다 생각하고 1부터 경우를 생각하며, 원래 수열의 0을 역수열의 원소만큼 카운팅 하면 간단한 문제이다. 이중반복문을 돌리면서 i -> 역수열의 인덱스번호  j-> 원수열의 0을 카운팅하기 위한 인덱스 번호라 생각하고 cnt로 0을 카운팅하면서 어차피 오름차순으로 정렬되어 있기에, 앞에 더 작은 숫자가 나와있는건 신경쓰않고 오로지 0만 카운팅 해서, cnt 와 역수열의 원소값이 같아지면 그때의 i+1 값을 원수열에 넣어주고 다음 반복문을 통해 다음값을 카운팅 해주면 된다. import sys#sys.stdin=open("input.txt", 'rt')N = int(input())rev = list(map(int, input().split()))..

결정 알고리즘을 이용할 때는 이분탐색을 이용하고, 문제에서 보통 답의 범위를 알 수 있다.  알고리즘은 다음과 같다. 주어진 수들 중에서 max를 찾는다. 그럼 범위는 1 ~ MAX의 수가 될 것이고, 이분탐색으로 중간값을 찾아 답이 되는지 찾아본다. 답이 되는지 찾아보기 위해, Count 함수를 만든다. 이 함수는 주어진 숫자들을 파라미터로 받은 값들로 모두 나누었을 때 그 합을 반환한다. 반환한 값과 K 값을 비교하여, 반환 값이 더 작으면 답이 될 수 없으므로 중간값 기준 더 작은 값, 즉 왼쪽을 탐색해야한다. 반환값이 K값보다 크거나 같을 때는 오른쪽을 탐색한다. 그렇게 while문을 반복하며 lt  이분탐색 기반의 가장 기본적인 알고리즘이며, 기본인 만큼 많이 쓰이고 중요한 알고리즘이니, 확실하..

코테 연습을 위해 알고리즘 복습을 하며 탐색의 기본격이라 할 수 있는 수토쿠 검사  알고리즘을 풀어보았다. 구간 검사를 위해 4중 포문을 돌려야하는 번거로움이 있지만, 알고리즘 자체는 그리 어렵지 않다.      3가지에 대한 검사를 해야한다.  1) 가로행에 1 ~ 9 가 다 있는지,2) 세로행에 1 ~ 9 가 다 있는지,3) 3*3 총 9개의 구간에 1 ~ 9 가 다 있는지, 먼저 9*9 총 81개의 숫자를 리스트(sudo) 에 담아준다.  sudo = [list(map(int, input().split())) for _ in range(9)] 그 뒤 check 라는 검사 함수를 만들어준다.  check 함수 안에는 1) 2) 3)을 차례로 검사해주는데 만약 거짓이 있는 순간 바로 False를 ret..

프로세스와 스레드가 뭐에요? 라고 말하면 답하는건 어렵지만 않지만 이둘의 차이점은 어떤것이 있는지, 깊게 파고들면 정확하게 대답하기가 쉽지않다. 우선 프로세스란 OS로부터 자원을 할당받은 작업의 단위다. 스레드란, 프로세스가 할당받은 자원을 이용하는 실행 흐름의 단위다. 즉 스레드는, 한 프로세스 내에서 나뉘어진 실행 단위인 셈이다. 가령 프로세스 두개가 동시에 실행하기 위해선, 프로세스1이 cpu에 적재되었다가, 준비상태로 내려가고 프로세스2가 적재되고, 이를 반복한다. 이것이 문맥교환이며, 이것이 반복되면 복잡하고 오버헤드가 발생하기 쉽다. 그래서 스레드는 프로세스의 메모리 구조에서, 코드 데이터 힙 영역을 공유한다. 스택 부분만 스레드마다 따로 가지고 있는 것이다. 공유되는 자원이 있기에, 문맥교환..

데드락의 개념: Blocked / Asleep state => 프로세스가 특정한 이벤트, 자원을 기다리는 상태 Deadlock state => 프로세스가 발생 가능성이 없는 이벤트를 기다리는 상태 그렇다면 Deadlock과 starvation의 차이는??? 데드락은 asleep 상태에서 일어날 가능성이 zero를 기다리는 것이고, starvation은 ready상태에서, cpu를 기다리는 것 이다. 자원을 분류할 때 일반적으로 HW / SW 로 분류할 수 있으며, 이외 다른 분류법은, 선점 가능여부 할당 단위에 따른 분류 동시 사용가능 여부 재사용 가능 여부 4가지가 있으며, 각각의 특징은 아래와 같다. 선점 가능 여부에 따른 분류 => cpu는 선점 당해도 돌아와서 다시 일을 할 수 있다(Context..

다중 프로그래밍이란, 여러 개의 프로세스들이 존재할때(보통의 경우에 해당) 프로세스들은 서로 독립적으로 동작하고, 공유자원 or 데이터가 있을 때 문제가 발생한다. 이때 동기화가 필요하며, 동기화란 프로세스들이 서로 정보를 공유하며 동작을 맞추는 것이다. 비동기적 => 프로세스들이 서로에 대해 모름 병행적 => 여러 개의 프로세스들이 동시에 시스템에 존재 병행 수행중인 비동기적 프로세스들이 공유 자원을 동시 접근할 때, 문제가 발생할 수 있다. 그러므로 동기화가 필요하다! Shared data(공유 데이터) => 여러 프로세스들이 공유하는 데이터 Critical section(임계 영역) => 공유 데이터를 접근하는 코드영역 Mutual exclusion(상호배제) => 둘 이상의 프로세스가 동시에 cr..

class Node: #기본 노드 클래스 def __init__(self, key=None): self.key = key self.next = None def __str__(self): #객체를 호출하면 이 함수가 호출된다. return str(self.key) 한방향 연결리스트 (SinglyLinkedList) => 노드들이 한 방향으로 연결된 리스트 head node와 tail 노드가 있고, 특정 key값을 찾는데 걸리는 시간은 가장 앞인 head노드로부터, 떨어진 거리의 시간과 같다. 삽입연산(pushFront(), pushBack()) / 삭제연산(popFront(), popBack()) / 탐색연산 / 제거연산 이 있다. 그렇다면, 이 한방향 연결리스트를 구현해보자 class SinglyLink..

A라는 [3, 9, -1, 2, 5] 배열이 있을 때 중간에 값을 insert 하려면 데이터값들이 밀리기 때문에 많은 시간이 걸리며 Worst case의 경우 n만큼의 시간이 걸려 O(n)의 시간복잡도를 가진다. 연결리스트는 순차적 자료구조로, 이런 경우 더 효율적인 연산을 가능하게 해준다. 가장 기본적인 연결리스트의 구조이며, 각 노드들은 (data값(key값), link(next노드를 가르키는 값)) 두가지 정보를 담고있다. 그리고 가장 앞의 노드는 head 노드이며, 마지막 노드가 가르키는 값은 NULL값이다. 이제 앞에서 O(n)의 시간이 걸렸던 insert 연산을 다시 해보자. B와 C 사이에 K라는 값을 대입하고자 할때, K값을 갖는 노드를 하나 만들어주고, B노드를 next를 K노드로, K노..

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

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