공부하는 개발 블로그

구조

1) 초기화

2) 기저 사례 처리

3) 이미 처리한 값인지 확인(초깃값인지 확인)

4) 계산

시간 복잡도 : 부분 문제의 수 * 부분 문제를 처리하는데 걸리는 시간

메모이제이션을 위해서는 *참조적 투명성* 필요.

함수의 입력값에만 의해서 값이 결정됨.

전역 변수 등의 영향을 받지 않음

비둘기 집의 원리

- 경로는 무수히 많을 수 있지만, 입력의 수는 경로보다 적은 경우, 메모이제이션이 유용할 수 있음

배열의 크기를 하나 더 키워서

첫번째 인덱스를 -1이나 0을 넣어서 예외상황/초깃값 처리를 쉽게 할 수 있다.

관련 문제 : 가장 긴 부분 증가 수열(구종만 p.234 nlog n 해법 다시 공부하기)

quad tree

p.244 quantization 
배열 A를 s개의 숫자로 양자화 
-> 오차의 합을 최소로할 때, 오차합 구하기 

1) 배열을 s개의 집합으로 나누고 
2) 각 집합에서 적정한 숫자를 찾아, 오차합 구하기 

1) s개의 집합을 구하기 : 부분 문제 
2) 적정한 숫자 : 평균, 오차합: 부분합 이용 


p.256 우물을 기어오르는 달팽이 

문제를 분할 할때: 
1) 모든 경우를 포함한다 
1) 두 경우에 동시에 포함되는 경우는 없다.

완전 탐색

기저 사례 작성 -> 반복 제거

dx, dy를 별도의 변수로 분리하자

중복 제거 : 순서를 강제하기

4.1 프로그램의 구조와 인터럽트

프로그램을 수행하기 위해서는 명령의 주소가 메모리에 올라가있어야한다.

프로그램의 주소 영역 : 코드, 데이터, 스택

코드 - 기계어 명령 부분

데이터 - 전역변수

스택 - 복귀할 주소 및 데이터

돌아올 주소를 스택에 저장

프로그램 내에서 발생되는 함수 호출에 필요한 복귀 주소 : 프로그램의 주소 공간 중 스택

인터럽트에 의해 CPU를 선점당한 위치 : 운영 체제 커널

◆ PCB(PRocess Control Block) 프로세스 제어 블록:

인터럽트 발생시 프로그램의 어느 부분까지 수행했는가를 저장하기 위한 영역

A 수행 중 인터럽트 -> 현재 실행 중이던 지점을 A의 프로세스 블록에 저장

4.2 컴퓨터 시스템의 작동 개요

◆ PC(Program Counter) 프로그램 카운터:

CPU가 수행해야할 메모리 주소를 담고 있는 카운터

컴퓨터의 구조:

하드웨어 : CPU, 메모리

+ 입출력 장치의 CPU와 메모리 : 입출력 컨트롤러(I/O controller), 로컬 버퍼(Local Buffer)

프로그램 카운터가 운영체제가 존재하는 부분을 가리키는 경우 -> 커널 모드

사용자 프로그램을 가리키는 경우 -> 사용자 모드

CPU의 명령

일반 명령 : 메모리를 읽고 CPU에서 계산하고 다시 메모리에 적는 과정 - 모든 프로그램이 수행할 수  있음

특권 명령: 보안이 필요한 명령. 입출력 장치, 타이머 등 접근. - 운영체제만 수행할 수 있도록 제한.

모드 비티를 통해 제한

◆ 시스템 콜(system call) : 사용자 프로그램이 특권 명령의 권한이 필요한 경우 - 운영체제에 요청

예) 디스크에서 데이터 읽기:

CPU가 컨트롤 레지스터를 세팅해서 데이터를 읽어오도록 명령

-> 디스크 컨트롤러가 자신의 로컬 버퍼에 저장

-> 디스크 컨트롤러가 인터럽트 발생

◆ 인터럽트 라인(interrupt line): 주변장치가 인러텁트를 세팅할 사용하는 것

인터럽트의 발생 원인마다 라인이 다름

인터럽트 발생 -> 커널 내의 인터럽트 처리 코드 수행

4.3 프로그램의 실행

1) 메모리에 실행 파일이 적재

2) 프로그램이 CPU를 할당받고 기계 명령을 수행하고 있는 상태를 의미.

여러 프로그램이 짧은 시간 단위로 CPU를 나누어 씀.

프로그램 전체가 메모리에 적재 되지는 않음

4.1 프로그램의 구조와 인터럽트

프로그램을 수행하기 위해서는 명령의 주소가 메모리에 올라가있어야한다.

프로그램의 주소 영역 : 코드, 데이터, 스택

코드 - 기계어 명령 부분

데이터 - 전역변수

스택 - 복귀할 주소 및 데이터

돌아올 주소를 스택에 저장

프로그램 내에서 발생되는 함수 호출에 필요한 복귀 주소 : 프로그램의 주소 공간 중 스택

인터럽트에 의해 CPU를 선점당한 위치 : 운영 체제 커널

◆ PCB(PRocess Control Block) 프로세스 제어 블록:

인터럽트 발생시 프로그램의 어느 부분까지 수행했는가를 저장하기 위한 영역

A 수행 중 인터럽트 -> 현재 실행 중이던 지점을 A의 프로세스 블록에 저장

4.2 컴퓨터 시스템의 작동 개요

◆ PC(Program Counter) 프로그램 카운터:

CPU가 수행해야할 메모리 주소를 담고 있는 카운터

컴퓨터의 구조:

하드웨어 : CPU, 메모리

+ 입출력 장치의 CPU와 메모리 : 입출력 컨트롤러(I/O controller), 로컬 버퍼(Local Buffer)

프로그램 카운터가 운영체제가 존재하는 부분을 가리키는 경우 -> 커널 모드

사용자 프로그램을 가리키는 경우 -> 사용자 모드

CPU의 명령

일반 명령 : 메모리를 읽고 CPU에서 계산하고 다시 메모리에 적는 과정 - 모든 프로그램이 수행할 수  있음

특권 명령: 보안이 필요한 명령. 입출력 장치, 타이머 등 접근. - 운영체제만 수행할 수 있도록 제한.

모드 비티를 통해 제한

◆ 시스템 콜(system call) : 사용자 프로그램이 특권 명령의 권한이 필요한 경우 - 운영체제에 요청

예) 디스크에서 데이터 읽기:

CPU가 컨트롤 레지스터를 세팅해서 데이터를 읽어오도록 명령

-> 디스크 컨트롤러가 자신의 로컬 버퍼에 저장

-> 디스크 컨트롤러가 인터럽트 발생

◆ 인터럽트 라인(interrupt line): 주변장치가 인러텁트를 세팅할 사용하는 것

인터럽트의 발생 원인마다 라인이 다름

인터럽트 발생 -> 커널 내의 인터럽트 처리 코드 수행

4.3 프로그램의 실행

1) 메모리에 실행 파일이 적재

2) 프로그램이 CPU를 할당받고 기계 명령을 수행하고 있는 상태를 의미.

여러 프로그램이 짧은 시간 단위로 CPU를 나누어 씀.

프로그램 전체가 메모리에 적재 되지는 않음

프로그램 마다 코드, 데이터, 스택 공간을 각각 가짐.

커널도 프로그램이므로 독립적인 코드, 데이터, 스택 공간을 가짐.

커널의 코드: CPU, 메모리 등의 자원 관리 + 사용자 인터페스 제공 + 시스템 콜 및 인터럽트

◆ 프로세스(process) : 현재 실행되는 프로그램

프로그램 마다 코드, 데이터, 스택 공간을 각각 가짐.

커널도 프로그램이므로 독립적인 코드, 데이터, 스택 공간을 가짐.

커널의 코드: CPU, 메모리 등의 자원 관리 + 사용자 인터페스 제공 + 시스템 콜 및 인터럽트

커널의 데이터: 프로세스의 상태, CPU 사용 정보, 메모리 사용 정보를 유지하기 위한 자료구조인 PCB 블록

커널의 스택 : 프로세스 별로 별도 스택. 커널은 공유 코드로 모든 사용자 프로그램이 시스템 콜을 통해 커널의 함수를 접근할 있기 때문에 일관성을 유지하기 위함.

4.4 사용자 프로그램이 사용하는 함수

1) 사용자 정의 함수: 프로그래머가 작성한 함수

2) 라이브러리 함수: 프로그래머가 직접 작성하지 않았지만 누군가가 작성한 함수

1)과 2)는 컨파일시 프로그램의 코드 부분에 기계어로 삽입 -> 프로세스의 주소 공간에 포함됨.

3) 커널 함수: 운영 체제 커널의 코드에 정의된 함수. 시스템 콜 함수 + 인터럽트 처리 함수. 커널의 주소 공간에 위치

4.5 인터럽트

CPU는 PC 지점의 서비스 이후 인터럽트 라인이 세팅되었는지 확인

타이머 인터럽트 : 특정 프로세스가 CPU 독점하는 것 방지

◆ 트랩(trap): 소프트웨어가 발생시키는 인터럽트

1)예외 상황(exception): 프로그램이 허용되지 않은 연산을 할때. ex: 0으로 나누는 연산, 주소 공간을 넘어서는 메모리 참조. 인터럽트 처리 루틴처럼 운영체제의 코드 영역에 처리 루틴 존재

2) 시스템콜: 사용자 프로세스가 운영 체제의 서비스를 요청하기 위해 커널의 함수를 호출하는 것. 인터럽트 라인 세팅.

◆ 인터럽트 벡터: 인터럽트 발생시 처리해야할 루틴의 주소를 보관하는 테이블

◆ 인터럽트 핸들러: 실제 인터럽트를 처리하기 위한 루틴. 인터럽트 서비스 루틴.

인터럽트 처리 뒤엔 인터럽트 발생 직전 시의 프로세스에게 CPU 제어권이 넘어감.

타이머 인터럽트인 경우, 발생 직전의 프로세스에게 넘어가지 않음.

4.6 시스템 콜

모드비트가 0 : 커널모드

모드비트가 1 : 사용자 모드

CPU는 매 시점 명령을 수행하기 이전에 모드 비트 체크.

운영체제가 사용자 프로그램에게 CPU의 제어권을 넘길때는 모드 비트를 0에서 1로 바꿔서 넘김.

시스템 콜: 사용자 프로그램에서 특권 명령 수행 필요시 운영체제에게 대행 요청

예: 디스크에서 데이터 읽기

1) 프로세스가 인터럽트 라인 세팅

2) 운영체제가 인터럽트 확인 -> 해당 서비스 루틴으로 이동

3) 디스크 컨트롤러에게 파일 읽기 명령

4) 그 동안 다른 프로세스 처리

5) 디스크 컨트롤러의 인터럽트

6) 처음에 데이터 읽기 요청한 프로세스를 큐에 삽입

CPU를 선점당하는 경우

1) 타이머에 인한 인터럽트

2) 시스템 콜.

4.7 프로세스의 상태

실행: CPU를 할당 받고 기계어 명령을 수행하는 프로세스의 상태

준비: CPU를 할당 받으면 바로 실행할 수 있지만 CPU가 하나라서 아직 할당받지 못한 상태

봉쇄: CPU를 할당받더라도 명령을 수행할 수 없는 프로세스 상태. 예: 입출력 작업이 완료되기를 기다리는 상태

준비 -> 실행: 실행 상태의 프로세스가 봉쇄로 바뀌거나, 타이머 인터럽트에서 CPU 할당 시간 만료

준비 큐(ready queue)로 관리(준비 큐에 프로세스를 할당하는 방법 - CPU 스케줄링)

자원 별로 큐 존재. 예: 디스크 입출력 큐, 키보드 입출력 큐, 공유 데이터에 대한 접근. HW. SW 큐.

디스크 입출력 큐에 서있다가 -> 순서대로 작업 -> 완료 되면 디스크 컨트롤러가 CPU에게 인터럽트 발생-> 프로세스가 CPU의 준비 큐로 이동

SW의 경우 자원부족보다는 일관성을 위해 접근 권한을 제한하는 것

4.8 프로세스의 실행 상태(running)

1) 사용자 모드에서의 실행 상태(user mode running)

2) 커널 모드에서의 실행 상태(kernel mode running): 시스템 콜 + 인터럽트.

커널 모드에서의 실행 상태도 프로세스의 실행 상태임. 커널은 대행일 뿐.

https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/submissions/

class Solution: 
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]: 
        for i in range(len(nums)): 
            c = 0 
            while nums[i] != nums[nums[i]-1] and nums[i] != i+1 : 
                if c > 4: break 
                print(nums, nums[i], nums[nums[i]-1])
                # right
                nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i] 
                # wrong
                #nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1] 
                c+=1