CS
[Algorithm] 이분 탐색
정렬되어 있는 배열에서 데이터를 찾으려고 할 때 O(N)이 걸리는 순차탐색에서 시간을 줄여 O(logN)의 시간으로 값을 찾는 탐색 방법 특징 및 과정 이분 탐색을 하고자 하는 배열이 이미 정렬되어 있어야함 과정 left, right로 가운데롤 mid로 잡아줌 mid과 구하고자 하는 값을 비교 mid left = mid + 1 mid > 구하고자 하는 값 -> right = mid - 1 left > right이 될때까지 2-4번을 반복
[Network] Top Down Approach 3장: Transport Layer
Transport Layer Transport Layer는 Application layer와 Network layer 사이에 존재하는 layer로 서로 다른 host에서 동작하는 application 프로세스들 간의 논리적 통신을 제공함 Transport-layer services 특징 Transport protocol은 host에서만 존재한다. Send side: 보내는 App messages를 segment로 나눠서 network layer로 전달함 Receive side: segment를 다시 message로 재구성해서 app layer로 전달함 하나 이상의 transport protocol이 app에 존재함 ex) Internet: TCP, UDP Transport vs Network layer ..
[OS] Memory Management
Background - 프로그램은 실행을 위해 디스크에서 메모리로 적재되어야 함 - 메인 메모리와 레지스터들이 CPU가 접근할 수 있는 유일한 저장소임 - 레지스터에 접근하는 것은 1 CPU clock cycle 이하로 소요됨 - 메인 메모리에 접근하는 것은 수많은 cycle들을 소요할 수 있음 - Cache 접근은 메인 메모리에 접근하는 것과 CPU 레지스터에 접근하는 것 사이만큼의 시간이 소요됨 - 올바른 작동을 보장하기 위해 메모리 보안이 필요함 Memory Address Binding Memory Address Symbolic Address: 코드 단에서 설정하는 address (ex. a = 10) Virtual(Logical) Address: 프로그램이 이상적으로 사용하는 주소 체계 Physi..
[BaekJoon] 백준 17144번 미세먼지 안녕!
[BaekJoon] 백준 17144번 미세먼지 안녕! 🎈문제 https://www.acmicpc.net/problem/17144 💬설명 - 단순한 구현문제였다. - 다만 python3로 채점하니 시간초과가 나서 pypy로 채점했다. 👩💻코드 # BaekJoon17144.py import copy # 변수 및 배열 초기화 R, C, T = map(int, input().split()) dx = [0, 1, 0, -1] dy = [-1, 0, 1, 0] A = [[] for _ in range(R)] cleaner = [] for i in range(R): A[i] = list(map(int, input().split())) for _ in range(T): # 확산 new_A = copy.deepcopy..
[BaekJoon] 백준 2098번 외판원 순회
[BaekJoon] 백준 2098번 외판원 순회 🎈문제 https://www.acmicpc.net/problem/2098 💬설명 간단하게 말하자면, 해당 문제는 사이클을 구하는데 그 사이클을 돌 때 가장 적은 비용이 드는 사이클을 구하는 것이다. 즉, 1->0->2->3->1 이렇게 돌아서 오는 경우와 2->3->1->0->2 이렇게 돌아서 오는 경우가 드는 비용이 같다는 것을 우선 염두에 두고 생각을 해보자. (편의상 0번 도시부터 있다고 가정하자.) 그렇게 되면, 우리는 모든 경우를 돌 때 0번 도시에서 출발한다고 가정해도 무방하다. 0->...->0 에서 ("..." 에 들어가는 도시들의 순서 + 모든 도시들을 돌았는지)만 고려해주면 되니까! 다시 말해서, 0번 도시에서 시작하는 경우만 생각하더라도..
[Network] Top Down Approach 2장: Application Layer
Application Layer Application Layer는 서로 다른 Host의 application이 서로의 message(data packet)을 교환하는데 사용됨 ex) HTTP, SMTP, FPT Principles of network applications Application Architectures (가능한 application 구조) Client - Server 구조: 서버와 클라이언트 간 통신 Server 항상 연결되어 있어야 한다. always-on 영구적인 IP 주소를 가진다. 규모에 따라 바뀌는 데이터 센터를 가진다. Client 서버를 통해서만 소통한다. 가끔 연결된다. always-on 유동적인 IP 주소를 갖는다. Peer to Peer (P2P) 구조: 호스트끼리 직접..
[OS] CPU Scheduling
[OS] CPU 스케줄러 CPU 스케줄러란 ready queue에 들어있는 프로세스들의 CPU 점유 순서를 정하는 알고리즘이다. CPU 스케줄러 이번에 얘기하는 CPU 스케줄러는 저번 포스팅에서 언급했던 ready queue에 있는 프로세스들의 CPU 점유 순서를 정하는 알고리즘을 말함 오늘은 이 CPU 스케줄러의 종류에 대해 좀더 자세히 알아보고자 함 CPU 스케줄러가 결정을 내리는 부분 running -> waiting (비선점형) running -> ready (선점형) waiting -> ready (선점형) terminates (비선점형) Dispatcher: CPU의 제어권을 CPU Scheduler에 의해 선택된 프로세스에게 넘김. dispatcher의 처리속도가 빠르면 빠를 수록 좋음 Sc..
[OS] Process and Thread
Process Process: 실행중인 프로그램 = 즉, 실행파일이 메모리에 적재되고, CPU를 할당받아서 명령 수행중인 상태 이때, 실행파일 전체가 메모리에 올라가지 않고 일부만 올라감 + 나머지는 디스크의 특정 영역에 존재 어쨌든 프로세스를 위해 제공된 메모리가 어떻게 구성되어 있는지 알아야함. 어떻게? Process 메모리의 구성요소 Code(Text) 실행할 프로그램의 코드가 저장되는 영역 CPU는 코드 영역에 저장된 명령어를 하나씩 가져가서 처리함 Data 프로그램의 전역 변수와 정적(static) 변수가 저장되는 영역 프로그램의 시작과 함께 할당되며, 프로그램이 종료되면 소멸함 Stack 함수의 호출과 관계되는 지역 변수와 매개변수가 저장되는 영역 함수의 호출과 함께 할당되며, 함수의 호출이 ..