구름을 채우다

문제 보기 이 문제는 스택/큐 문제이다. (난 덱(deque)을 사용해서 문제를 풀었다..) 문제를 푼 로직은 다음과 같다. progress와 speed 리스트를 deque 자료형으로 변환한다. (7~8번째 줄) 각 진행속도만큼 progress를 증가시킨다. (12~14번째 줄) 만약 맨 첫 번째 작업이 끝이 나면, 연속된 작업 중 완료된 작업들의 개수를 구한다. (16~22번째 줄) 만약 배포된 작업이 있으면 정답 배열에 추가한다. (24~26번째 줄) 작업이 남아있는 동안 2~4번을 반복해서 실행한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 from collections import deque def sol..

문제 보기 이 문제는 해쉬 문제이다. 문제를 해결하기 위해 2가지의 dictionary 자료형 변수가 필요하다. 첫 번째는 각 장르별 재생 횟수를 위해, 두 번째는 각 노래별 재생 횟수를 위해서이다. 문제를 푼 로직은 다음과 같다. 각 장르별 총 재생 횟수를 구한다. (10~13번째 줄) 모든 노래에 대해 장르별로 해쉬 맵을 구성한다. (14~17번째 줄) 총 재생 횟수가 많은 순서대로 장르의 순서를 구한다. (19~20번째 줄) 재생 횟수가 많은 순서대로 각 장르에 속한 노래들의 순서를 구한다. (21~23번째 줄) 3번에서 구한 장르의 순서대로, 그 장르에 속한 노래들을 4번에서 구한 순서에서 첫 번째와 두 번째 노래를 베스트 앨범에 추가한다. (노래가 1곡이면 1곡만 추가한다.) (25~32번째 줄..

문제 보기 이 문제는 해쉬 문제이다. (그런데 정작 해쉬는 잘 안 쓰인 것 같다..) 처음엔 간단해 보였는데 경우의 수를 잘 못해서 한참 헤맸다.. 문제를 푼 로직은 다음과 같다. 먼저 옷의 각 종류에 대해서 옷의 개수를 센다. (옷의 이름은 중요하지 않다. 개수만 알면 된다.) (7~11번째 줄) 만약 옷의 종류가 한 가지라면 옷의 개수만큼 반환한다. (스파이는 최소 1개 이상의 옷을 입어야하기 때문) (13~16번째 줄) 만약 옷의 종류가 한 가지 이상이라면, (종류 1의 개수 + 1) * (종류 2의 개수 + 1) * ... - 1을 반환한다. (옷의 종류에서 1을 더하는 이유는 해당 종류의 옷을 안 입을 수 있기 때문이고, 마지막에 - 1을 하는 이유는 스파이는 최소 1개 이상의 옷을 입어야 하므..

문제 보기 이 문제는 해쉬 문제이다. 그런데 접두사라는 특징이 보여서 지금까지 한 번도 해본 적 없는 트라이로 풀어보았다. 문제를 푼 로직은 다음과 같다. 전화번호부에 있는 전화번호들을 정렬한다. (26번째 줄) 정렬이 끝나면 길이가 짧은 문자열부터 차례대로 나열되는데, 이 때 트라이에 삽입하면서 확장시켜나간다. 트라이에 삽입할 때, 문자열의 마지막 노드에 end라는 불리언 변수를 True로 설정한다. (21번째 줄) 만약 어떤 문자열을 트라이에 삽입할 때, end가 True인 노드를 만난다면 이전에 같은 문자열이 삽입되었다는 뜻이므로 False를 반환한다. (18~20번째, 29~30번째 줄) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2..

문제 보기 이 문제는 해쉬 문제이다. (매우 간단했다..) 문제를 푼 로직은 다음과 같다. 마라톤에 참가한 선수들에 대해서 dictionary를 생성하고, 이름의 개수를 센다. (4~10번째 줄) 마라톤을 완료한 각 선수들의 이름에 대해 갯수를 깎는다. (12~14번째 줄) 문제의 조건에서 마라톤을 완주하지 못한 선수는 1명이라고 명시되어있으므로, 1개 남은 이름을 찾는다. (16~19번째 줄) 난 이렇게 풀었지만 다른 사람의 풀이를 보니 collections 모듈의 Counter 함수를 사용한 것을 보았다. (정말 간단하다...) Counter 함수는 dictionary를 반환한다. 또한, dictionary 타입끼리는 덧셈, 뺄셈, 교집합과 합집합 연산이 가능하다는 것을 알았다. 1 2 3 4 5 6..

Deadlock 모든 프로세스가 다른 프로세스의 작업이 끝나기를 기다리고있는 상태 Deadlock(교착상태) 발생 필수 조건 4가지 Mutual exclusion (상호배제) 최소한 1개의 자원은 공유할 수 없어야 한다. Hold and wait (점유대기) 최소한 1개의 자원을 소유한 프로세스가 다른 프로세스가 소유하고 있는 자원을 얻기를 기다려야 한다. No preemption (비선점) Preemption이 없어야 한다. Circular wait (순환대기) 서로 다른 프로세스가 자원을 소유하고 요청하는 사이클이 존재해야 한다. Resource Allocation Graph Resource 종류마다 1개의 인스턴스만 있고, 사이클이 존재한다면 항상 데드락이 발생한다. Resuorce 종류마다 여러개..

Process Scheduling 실질적인 스케줄링 객체는 스레드이다. (리눅스는 스레드 단위로 스케줄링을 함) 왜 프로세스 스케줄링이 필요하지? CPU 활용을 최대한으로 하기 위해서 (CPU utilization) 실행시간을 공평하게 분배하기 위해 (Fairness) 프로세스의 빠른 응답을 위해 (Responsiveness) CPU Scheduler CPU가 비가동 상태일 때 CPU 스케줄러에 의해서 ready 큐로부터 한 개의 프로세스를 선택한다. 스케줄링 결정을 해야 할 때 프로세스가 running state에서 waiting state로 바뀔 때 (CPU가 I/O 상태로 바뀔 때) 프로세스가 running state에서 ready state로 바뀔 때 (프로세스가 running 큐에서 ready ..