HJW's IT Blog

# 부분배열의 합 # 배열 A 가 주어졌을 때, 이 배열의 부분배열 A[i:j]의 최대값을 구하시오 > Brute force : O(n^3) > 만약 A[i] + ... + A[j] 까지의 합을 구했다면, (A[i] + ... + A[j]) + A[j+1] 은 O(1) 에 구할 수 있다 >> 총 O(n^2) > 방법 3: 모든 구간은 어디선가 끝나야 하므로 각 위치마다 여기서 끝나는 값의 최대 값을 저장 >> 전체의 최대는 이 중 최대값 >> S[i] : i 위치에서 끝나는 합의 최대값 - ex) S[1] = max (0, A[1]), S[i] = max(0, S[i-1] + a[i]) # 부분배열의 합 변형 # 위와 동일하지만 자연수 k 가 주어지는데, 이때 j >= i + k 이다. # 즉 최소 k개..

# Multiple Label Switching (MPLS) > 목표: 고정 길이 label 을 사용해 빠른 속도의 ip forwarding >> 고정 길이 식별자를 통해 빠른 검색 (faster than prefix matching) >> > MPLS cable routers >> Label 값만 사용해 forwarding >> Ip forwarding table 과 MPLS forwarding table 은 다르다 >> Flexibility: MPLS forwarding 결정은 ip 와 다를 수 있다 - Dest 와 source 주소를 이용해 다른 목적지 다른 경로로 - 만약 link fail시 미리 계산해둔 다른 경로 사용 > MPLS vs IP >> IP: 목적지 주소로만 경로가 결정됨 >> MP..

1 File => 하나의 inode(index node) 를 가르킨다 inode list 1 open file table, 1 active inode table, many per-process file table #File System Issues > Important to user: >> Persistence: 데이터는 전원이 꺼지거나 시스템 충돌이 발생해도 유지된다 >> Easy to Use: 쉽게 찾고, 읽고, 변경이 가능하다 >> Efficiency: 디스크 공간을 효율적으로 사용 >> Speed: 데이터에 빠르게 접근 가능 >> Protection: 다른 사람이 데이터를 손상시키지 못하게 보호 > OS 는 다음 기능을 제공한다 >> Directory and Naming: 위치가 아닌 디렉토리 및..

직사각형 (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[..