HJW's IT Blog

직사각형 (SCPC 2016) # n 개의 직사각형이 있다. # 직사각형의 포함 관계에서 가장 많은 직사각형들이 서로 포함 된 경우, 이 직사각형의 수를 구하시오 > 각 직사각형을 기준으로 다른 모든 직사각형을 순회하면서 포함관계를 확인한다. 3n + 1 (SCPC 2016) # 자연수 n 이 주어지면 이 수를 짝수이면 반으로 나누고 홀수이면 3배한 후 1을 더한다 # 이 과정을 거치면 어떤 수던지 1이 된다는 것이 알려져 있다 # 정확하게 K( 이 때 가장 큰 수는 2^n 임이 자명함 > 1 부터 재귀적으로 올라가며 (현재 수 -1) % 3 == 0 일 때를 구해 재귀적으로 올라가며 모든 수에 대해 n 번 반복했을 때 최소값 징검다리 (SCPC 2016) # 0 번 부터 n 번 까지 번호가 매겨진 징검..

Subset Sum # n 개의 서로 다른 숫자가 주어져 있다. # 이 중 k개를 더했을 때, 정확하게 합이 S 가 되는것이 있는가 방법 1> Brute force 로 모든 조합을 해본다면 O(n^k *k) 시간이 걸린다 방법 2> n개의 숫자를 모두 정렬 >> 가장 큰 수와 작은수를 더했을 때 합을 구해본다 if (min + max S): max index - 1 방법3> 배열 D 생성 (D[n][k]) >> D[i][j]: 만약 정확하게 i개의 수를 가지고 그 합이 j가 되게할 수 있다면 1, 아니면 0 >> 다음 조건을 만족하는 a가 있다면 1 - D[i-1][j-a] = 1 이고 D[..

#MAC address and ARP > MAC address란 >> 기능: 로컬에서 사용되며, 한 인터페이스에서 다른 물리적으로 연결된 인터페이스로부터 frame 을 로컬로 받아올때 사용한다 >> Burned in NIC ROM (구워져 있다) >> 48 bit: MAC Address = Manufacturer ID + Product ID (represented in hexadecimal) >> LAN 의 각 adapter는 LAN 주소가 있다 >> MAC 주소 할당은 IEEE 가 도맡는다 >> Manufacturer 들은 MAC 주소 공간의 일부를 구매 >> MAC 주소 : 주민번호와 같다, IP 주소: 우편번호와 같다 >> MAC flat address -> Portability - LAN card..

Link Layer > Host 와 router 는 nodes 라 부른다 > 이웃하는 노드들을 잇는 경로: links >> wired, wireless, LANs > datagram -> frame >Datagram 은 다른 링크 프로토콜을 통해 링크 사이에 전달된다 > 각 프로토콜은 서로 다른 서비스를 제공한다. > Transportation Analogy >> tourist: Datagram >> transport segment: Communication Link >> Transportation mode: Link Layer Protocol >> Travel agent: Routing Protocol Link Layer Services > Framing, Link Access >> Datagram을 ..

#Polygon > 선분들로 이루어진 닫혀진 도형 > n 개의 점 (x1,x2,...,xn) 과 n개의 선분 {ei|ei=(xi,x(i+1) and x(n+1)=x}가 다음 조건을 만족해야 한다 >> 두 선분 ei 와 e(i+1) 이 만나는 점은 v(i+1) 뿐 >> 그 외 다른 선분들은 만나지 않는다. > Convex Polygon ( 볼록 폴리건 ) >> 모든 내각 n 개의 점이 주어졌을 때, 이 점을 모두 포함하는 가장 작은 볼록 다각형 >> 만들어진 볼록 다각형 안의 두 점을 잇는 직선은 항상 다각형 안에 있다. #Brute-Force > 가장 y 좌표가 작은 점을 기준점으로 다른 모든 점이 선분 (u,v)의 왼쪽으로 가는 점 v를 찾는다. > v에..

Paging 이란? > 프로세스를 작은 고정크기의 partition을 나누는 것을 말한다 >> Physical Memory의 이 공간을은 frame 이라 부른다 >> Page size = frame size >> 전체 프로세스는 여전히 메모리에 로드되어 있다 >> 하지만 연속적일 필요는 없다 >> 가상 주소는 페이지 수와 페이지의 시작에 offset으로 구성된다. > Segmentation이랑 비교 했을 때 paging 은 >> 할당과 swapping 이 더 쉽다 >> No external fragmentation Paging 구현 > Page Table 은 특정 프로세스의 모든 페이지를 기록 >> 각 entry는 메인 메모리에 있는 알맞는 frame을 가지고 있다 >> Protection bit 을 가..

Segementation 기본 개념 > 프로세스를 메모리 내에서 여러 segement로 나눈다 > 각 segement는 분명한 목적이 존재: >> 예) code, static data, heap, stack >> Segement 는 다른 크기일 수 있다 > 전체 프로세스는 여전히 메모리에 로드 되어 있지만, 그 프로세스를 구성하는 segment들은 연속적으로 메로리에 올라가지 않아도 된다 > Segment는 protection bit 을 가진다 >> Read-only (code) >> Read-write (data, heap, stack) >> 프로세스들이 코드와 데이터를 공유할 수 있게 해준다. Segment Address > Segment의 가상 주소는 다음으로 이루어 진다 >> Segment Num..

> MMU는 주소공간을 보호하고, 가상 주소로 변환한다(Translation) >> Base register는 프로세스의 최하위 가상 주소를 가지고 있다 (loader가 정함) >> Limit register는 프로세스의 최상위 가상 주소를 가지고 있다 (compiler가 정함) >> Translation 이란? >>> Physical addr = Virtual addr + base reg >> Protection 이란? >>> if (virtual addr > limit) ~>address exception으로 OS에 가두어 둔다 Dynamic Relocation - OS vs. User Programs > User program(aka. process) 는 각자의 가상 메모리를 가진다 >> Reloc..

#개요 > Network Flow란 노드들과 그들 사이의 에지로 이루어진 흐름을 나타내는 개념 > 노드들이 출발지와 목적지로 구성되며, 에지들은 용량(capacity)를 가진다 > 목표: 출발지에서 목적지로 가는 흐름의 양을 최대화/최소화 하는것 > Flow Network란? >> 네트워크 플로우 문제를 모델링하기위한 그래프이다. >> 각 에지에 허용가능한 최대 흐름이 지정되어 있다 >> 시작점과 목적지가 지정되어 있어야 한다 >> 출발지에서 목적지로 흐르는 실제 흐름량이 나와있다 #입력 > 가중그래프 > 에지의 가중치: c(e) > 시작점 s: 들어오는 에지 x > 도착점 t: 나가는 에지 x #Flow 란? > 그래프 G,s,t 가 주어졌을 때, flow f는 각 에지 e에 정수값 f(e)를 다음 조..

Router Scaling > Destination 이 너무 많다 --> 모든 destination 정보를 routing table에 저장할 수 없다 > 라우팅 테이블끼리 swamp link 공유 > Administrative Autonomy > Internet 은 network of networks > 각 network admin은 자체 network에서 라우팅을 관리 > Internet Approach >> Intra-AS routing (AS: domains) >>> 같은 AS 내 호스트오 라우터 간의 라우팅 >>> 같은 AS 내의 모든 라우터는 same intra-domain protocol을 실행해야 한다 >>> 다른 AS에 있는 라우터들은 다른 intra-domain protocol 실행 가능..