public string DevelopmentDiary(Knowledge knowledge) {
if (knowledge != null) {
return "level up"
} else {
return "level down"
}
}컴퓨터 과학
1.5 캐시가 중요하다.
프로그램을 실행하면 복잡한 복사과정이 일어난다.
이 과정들은 실제 작업들을 느리게 하는 오버헤드들이다.
물리학적으로 봤을 때, 저장장치가 클수록 장치들이 느린 속도를 갖는다.
레지스터 파일은 메모리보다 100배 빠르게 데이터를 읽는다. 따라서 프로세서와 메모리간 격차를 줄이기 위해 프로세서가 단기간에 필요로 할 가능성이 높은 정보를 임시 저장할 목적으로 캐시 메모리를 사용한다.
지역성(loacality): 지엽적인 영역의 코드와 데이터를 액세스하는 경향
1.6 저장장치들은 계층구조를 이룬다.
컴퓨터 시스템 저장장치의 계층구조
L0: 레지스터
L1: L1캐시
L2: L2캐시
L3: L3캐시
L4: 메인메모리
L5: 로컬디스크
L6: 웹서버
1.7 운영체제는 하드웨어를 관리한다.
운영체제의 목적
- 제멋대로 동작하는 응용프로그램들이 하드웨어를 잘못 사용하는 것을 막음
- 응용 프로그램들이 단순하고 균일한 매커니즘을 사용하여 복잡하고 매우 다른 저수준 하드웨어 장치들을 조작
파일 - 입출력 장치의 추상화
가상메모리 - 메인 메모리와 디스크 입출력 장치의 추상화
프로세스 - 프로세서, 메인 메모리, 입출력 장치 모두의 추상화
1) 프로세스
다수의 프로세스들은 동일한 시스템에서 동시에 실행될 수 있다.
동시에-라는 말은 한 프로세스의 인스트럭션들이 다른 프로세스의 인스트럭션들과 섞인다는 것을 의미한다.
운영체제
- '문맥 전환'이라는 방법을 통해 프로세스의 인스럭션 교차실행을 수행한다.
- 프로세스가 실행하는 데 필요한 모든 상태정보(컨텍스트)의 변화를 추적한다.
- 현재 프로세스에서 다른 새로운 프로세스로 제어를 옮기려고 할 때 현재 프로세스의 컨텍스트를 저장하고 새 프로세스의 컨텍스트를 복원한다.
커널
- 운영체제 코드의 일부분으로 메모리에 상주함
- 별도의 프로세스가 아님
- 모든 프로세스를 관리하기 위해 시스템이 이용하는 코드와 자료구조의 집합
- 다른 프로세스로의 전환 관리
동시성 프로세스 (쉘 프로세스와 hello 프로세스를 중심으로)
- hello라는 프로그램을 실행하라는 명령을 받으면
- 쉘은 시스템 콜이라는 특수 함수를 호출하여 운영체제로 제어권을 넘겨준다.
- 운영체제는 쉘의 컨텍스트를 저장하고 새로운 hello프로세스와 컨텍스트를 생성한 뒤
- 제어권을 새 hello 프로세스로 넘겨준다.
- 운영체제는 쉘 프로세스의 컨텍스트를 복구시키고 제어권을 넘겨주면서 다음 명령 줄 입력을 기다림
작업 요청 과정
- 컴퓨터 특정 파일 읽기나 쓰기 같은 특정 시스템 콜을 실행하여 커널에 제어를 넘겨줌
- 커널은 요청된 작업을 수행하고 응용 프로그램으로 리턴
2) 쓰레드
- 프로세스는 쓰레드라고 하는 다수의 실행 유닛으로 구성
- 동일한 코드와 전역 데이터를 공유함
- 프로세스들보다 데이터 공유가 더 쉬우며 쓰레드가 프로세스보다 효율적임
3) 가상 메모리
각 프로세스는 가상주소 공간이라고 하는 균일한 메모리의 모습을 갖게됨
주소 공간
- 최상위 영역: 모든 프로세스들이 공통으로 사용하는 운영체제의 코드와 데이터를 위한 공간
- 하위 영역: 사용자 프로세스의 코드와 데이터를 저장
상위 영역
- 커널 가상메모리 - 주소 공간의 맨 윗부분은 커널을 위해 예약 됨, 커널 코드 내에 정의된 함수를 직접 호출하는 것도 금지됨. 커널을 직접 호출해야 가능함.
- 스택 - 함수 호출을 구현하기 위해 사용하는 스택이 위치함
- 공유 라이브러리
- 힙 - 런타임 힙. 프로그램과, 프로세스가 실행되면서 필요한 메모리 공간을 할당. 런타임에 동적으로 크기가 변함.
가상 메모리가 작동하기 위해서는 프로세서가 만들어내는 모든 주소를 하드웨어로 번역하는 등의 작업이 필요함. 프로세스의 가상메모리의 내용을 디스크에 저장하고 메인 메모리를 캐시로 사용함. (CPU 캐시 시스템과 유사함)
자료구조와 알고리즘
이분 탐색(Binary Search)
정렬된 배열에서 사용하는 알고리즘, 말 그대로 자료를 반으로 나눠가며 검색하기 때문에
자료의 양이 ^(1/2)로 줄어듦. 따라서 시간복잡도가 O(logN)
ex)
| 0 (left) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 (right) |
|---|---|---|---|---|---|---|---|---|---|
| 5 | 10 | 15 | 30 | 31 | 35 | 51 | 88 | 91 | 99 |
위 자료에서 30을 찾고 싶을 때 left, right를 설정 후 mid에 할당
(1번) mid = (left + right) // 2
| 0 (left) | 1 | 2 | 3 | 4 (mid) | 5 | 6 | 7 | 8 | 9 (right) |
|---|---|---|---|---|---|---|---|---|---|
| 5 | 10 | 15 | 30 | 31 | 35 | 51 | 88 | 91 | 99 |
list[mid]를 기준으로 left와 right 설정
30 < list[mid]이므로 right의 값을 변경
(2번) right = mid - 1
| 0 (left) | 1(mid) | 2 | 3 (right) | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 5 | 10 | 15 | 30 | 31 | 35 | 51 | 88 | 91 | 99 |
(3번) left = mid + 1
| 0 | 1 | 2(left, mid) | 3 (right) | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 5 | 10 | 15 | 30 | 31 | 35 | 51 | 88 | 91 | 99 |
(4번) left = mid + 1
| 0 | 1 | 2 | 3 (left, mid, right) | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 5 | 10 | 15 | 30 | 31 | 35 | 51 | 88 | 91 | 99 |
list[mid] == 30 이므로 종료
list의 길이가 10이므로 최대 4번에 걸쳐 수행함.
- Parametric Search
최적값을 찾아나가는 문제, 배열의 인덱스로 찾아나가기보다
배열의 최솟값과 최댓값을 찾은 뒤 이를 기준으로 최적값을 찾아나가는 문제
출처: 백준 2805번
| 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 4 | 42 | 40 | 26 | 46 |
경우에 따라서 배열을 정렬해야 될 수도 아닐 수도 있다.
최적값을 A라고 하고, 찾아야하는 값을 B라고 하자
위 배열의 값들 중 A를 넘는 수 중 A를 빼고 나온 값을 다 더했을 때 B값이 되는 A를 찾는 것이다.
예를 들면 A를 26이라고 했을 때
4는 26을 넘지 못하므로 패스(0으로 취급한다), 42는 26을 넘으므로 42-26=16, 40역시 26을 넘으므로 40-26=14 ... 이를 표로 정리하면
ex) A=26
| 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 0 | 16 | 14 | 0 | 20 |
위 값을 다 더하면 50이 된다.
주어진 문제에서는 B값이 20이 되는 A를 찾아야 한다.
그렇다면 이 20은 어떻게 찾아야 하는가?
A를 배열에 있는 수들로 한정짓지 않는 것이 핵심이다.
위 배열의 최솟값은 4이고 최댓값은 46이다.
따라서 A가 가질 수 있는 값들은 4에서 46 사이이다.
이를 표로 나타내면
| 0 | 1 | 2 | ... | 40 | 41 | 42 |
|---|---|---|---|---|---|---|
| 4 | 5 | 6 | ... | 44 | 45 | 46 |
이를 다음과 같이 표현한다.
| 0 (left) | 1 | 2 | ... | 21 (mid) | ... | 40 | 41 | 42 (right) |
|---|---|---|---|---|---|---|---|---|
| 4 | 5 | 6 | ... | 25 | ... | 44 | 45 | 46 |
처음에는 mid에 있는 값들로 다 빼본다.
A = 25 (list[21])
| 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 0 | 17 | 15 | 1 | 21 |
B = 54
찾고자 하는 36보다 크므로 (36 < 54)
left를 이동한다.
left = mid + 1
| 22 (left) | 23 | 24 | ... | 32 (mid) | ... | 40 | 41 | 42 (right) |
|---|---|---|---|---|---|---|---|---|
| 26 | 27 | 28 | ... | 36 | ... | 44 | 45 | 46 |
A = 36 (list[32])
| 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 0 | 6 | 4 | 0 | 10 |
B = 20
따라서 A = 36이다.
분할정복(Divide and Conquer)
출처: AI
분할 정복(Divide and Conquer)은 큰 문제를 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법입니다. 이 방법은 다음 세 가지 주요 단계로 구성됩니다:
분할 (Divide): 문제를 더 작고 관리하기 쉬운 하위 문제로 나눕니다. 이 과정은 문제가 더 이상 나눌 수 없을 때까지 반복됩니다.
정복 (Conquer): 나눠진 하위 문제들을 개별적으로 해결합니다. 일반적으로 이 단계에서는 재귀적 방법이 사용됩니다.
결합 (Combine): 해결된 하위 문제들의 결과를 합쳐 원래 문제의 해답을 도출합니다.
특징
재귀적 접근: 분할 정복은 주로 재귀를 활용하여 문제를 해결합니다.
효율성: 많은 경우에 O(n log n)의 시간 복잡도를 가집니다.
병렬 처리에 적합: 문제를 독립적인 하위 문제로 나누기 때문에 병렬 처리에 유리합니다.
스택(Stack)
스택은 자료구조의 하나이며 리스트형 배열로 입력과 출력 순서는 후입선출(Last In First Out, LIFO)다.
Push: 스택에 데이터를 넣는 작업
Pop: 데이터를 꺼내는 작업
Top: push, pop하는 데이터 가장 윗부분
Bottom: 데이터의 가장 아랫부분(가장 처음 들어간 데이터)
underflow: 배열이 없는 상태에서 pop을 하면 발생하는 오류
overflow: 스택이 꽉 찼을 때 데이터를 넣으면 발생하는 오류
큐(Queue)
큐는 자료구조의 하나이며 리스트형 배열로 입력과 출력 순서는 선입선출(First In First Out, FIFO)다. 데이터를 처리하는 곳에 데이터가 들어온 순서대로 전달할 때 유용하다. 일상 속에서 찾을 수 있는 예시에는 은행 창구나 마트 줄이 있고, 컴퓨터와 관련해서는 네트워크에서 많이 사용된다.
Enqueue: 데이터를 추가하는 작업
Dequeue: 데이터를 꺼내는 작업
Front: 데이터를 꺼내는 쪽
Rear: 데이터를 넣는 쪽
참고-
순환 큐 - 일반적인 큐는 데이터를 넣거나 빼면 앞쪽의 공간이 낭비되고, 배열이 가득차면 새로운 배열을 할당해야 한다. 그러나 순환 큐를 사용하면 이러한 문제를 해결할 수 있다.
우선순위 큐(Priority Queue)
큐에 데이터를 enqueue할 때 데이터에 우선순위를 부여하여 dequeue할 때 우선순위가 가장 높은 데이터를 꺼낸다. 리스트 배열에서 사용하면 매번 정렬을 해야하는 문제가 있기 때문에 시간복잡도를 고려해 heap을 활용하여 구현한다.
링크드 리스트(Linked List)
배열은 메모리상에서 연속된 주소에 할당이 된다. 특정 위치에 있는 데이터를 접근하기 위해 인덱스를 쓰면 O(1)안에 접근할 수 있다. 다만, 연속된 주소에 할당되는 문제로 인해 배열의 삽입이나 제거가 까다롭다. 이를 해결하기 위해 각 노드들에 다음(혹은 다음과 이전) 노드의 위치를 담은 자료구조가 연결 리스트이다.
해시테이블(Hash Table)
데이터의 값을 해시 함수에 넣고 도출된 값을 인덱스로 사용하는 테이블이다. 데이터의 검색, 추가 및 삭제가 용이하나. 도출된 값의 범위는 제한적이므로 많은 양의 데이터를 넣을 때는 충돌이 발생할 수도 있다. 따라서 이를 해결하기 위해 다양한 방법을 사용하기도 한다.
체인법: 해시테이블에 링크드 리스트를 연결하여 충돌이 일어나는 지점의 데이터를 해당 위치 링크드 리스트의 끝에 저장하는 방법이다.
오픈주소법: 새로운 공간을 차지하지 않고, 해시테이블 내부에서 빈 버킷을 찾아 데이터를 추가하는 방법이다.
