구름을 채우다

문제 보기 이 문제는 해쉬 문제이다. 문제를 해결하기 위해 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 ..

Thread 실행의 가장 작은 단위 스레드마다 별도의 stack과 register set이 있다. Code영역과 data영역은 공유한다. 왜 스레드를 사용해야 하는가? 더 나은 병렬성(Parallelism)으로 성능이 향상된다. 프로세스보다 스레드를 생성하는 것의 오버헤드가 더 적다. 자원을 더 효율적으로 사용한다. 동일한 작업을 병렬적으로 실행할 때, 별개의 프로세스를 생성하는 것은 자원 낭비이다. 데이터 공유가 더 쉽다. IPC를 사용할 필요가 없다. Concurrency vs. Parallelism Parallelism (병렬성) 다중 작업을 동시에 수행할 수 있는 능력 Concurrency (동시성) Time sharing으로 인해 단위시간마다 다중작업을 빠르게 진행하여 동시에 수행하는 것처럼 보..

Process Memory Layout Normal function을 실행하면 stack영역을 사용한다. System call은 kernel stack에서 사용 후 결괏값을 stack 영역에 저장한다. System call을 호출할 때마다 프로세스 1개당 kernel stack 1개를 할당한다. Stack 영역 함수들이 호출될 때 아래로 차면서 데이터가 저장된다. Heap 영역 동적 메모리가 요청될 때 위로 차면서 데이터가 저장된다. Data segment 전역변수가 저장된다. Text segment 바이너리 프로그램 코드가 저장된다. 왜 프로세는 Physical memory의 같은 Kernel memory 영역을 공유하지? 물리적으로는 1대의 컴퓨터에 1개의 OS만 사용 가능하다. 하지만 1개의 프로세..

System call 프로그래머들은 API를 통해 간접적으로 system call을 사용한다. System call을 직접적으로 호출하지 않고 API를 사용하는 이유 매우 많은 종류의 파라미터가 있기 때문에, system call을 직접적으로 사용하기 어렵다. 이식성 (다른 컴퓨터를 쓰더라도 API를 통해 똑같이 실행할 수 있는 능력) Windows API가 Linux에서 작동하지 않는 이유 OS가 다르기 때문에 전혀 다른 system call을 사용하기 때문. System call types: Communications Message passing 메시지 교환에 기반함 Sender와 Receiver가 우선적으로 확인되어야 한다. Shared memory 프로세스가 system call을 통해 다른 프로..

운영체제란? 하드웨어를 관리하기 위한 프로그램 컴퓨터 하드웨어와 사용자 사이에서 중간자 역할을 하는 프로그램 운영체제의 목표 사용자 프로그램을 실행하고 사용자 문제를 더 쉽게 해결한다. 컴퓨터 시스템을 더 사용하기 쉽게 만든다. 컴퓨터 하드웨어를 효율적으로 사용한다. 컴퓨터 시스템 구조 CPU와 Device controller는 동시에 작동한다. Memory controller는 메모리에 대한 접근을 동기화한다. (CPU 클럭에 의해 메모리 접근이 이루어진다. 아무 때나 메모리에 접근해서 값을 가져올 수 있는 게 아님) 컴퓨터 연산 Start-up Bootstrap 프로그램: 컴퓨터 전원이 켜질 때 가장 먼저 실행되는 프로그램 ROM이나 EEPROM에 저장된다. CPU 레지스터, device contro..