Algorithm: 문제풀이 3

# 부분배열의 합

# 배열 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개 이상 연속한 값의 합 중 최대 = "연속한 k개의 합" + "0개 이상 연속한 수의 합 중 최대"

          > S[i] 에 추가로, 각 위치에서 최근 k개의 합을 구해서 저장하고 이를 S'[i] 라고 하자

          > i 번 위치에서 답을 B[i] 라 하면, B[i]의 값은 일단 최근 k개는 반드시 들어가야 한다.

          > 따라서 B[i] = S'[i] + S[i-k], 답: max(B[i])

 

#문자 인코딩

# a를 1, b를 2, ... , z 를 26 으로 숫자에 대응시키자.

# 이때, 123 은 abc 일수도, aw 일 수도, lc 일 수도 있다. 즉 총 3개의 문자열에 대응

# 숫자로 이루어진 문자열이 주어졌을 때, 이 문자열에 대응되는 영어 소문자 문자열의 수를 구하라

          > 숫자가 한자리라면 1가지, 두자리라면 최대 2가지

          > 1,2,...,k 가지 까지 가능했고 이때의 답이 S[1] , ... S[k]에 저장되어있다 가정하자

          > 가장 마지막에 오는 글자는 만약 두자리가 27보다 작다면: S[k+1] = S[k] + S[k-1]

                    >> 그렇지 않다면: S[k+1] = S[k]

 

#변형: 최소 횟수로 구하라

          > 위와 마찬가지로 한자리라면 1가지

          > 두자리라면, 27보다 작다면 : 1가지

                    > else: 2가지

          > T[1:1], T[1:2],...,T[1:k] 까지 풀었고 이때 답이 S[1],...,S[k] 에 저장되어 있다 가정

          > S[i] = 2: 바꿀 수 있고 마지막 문자는 2개 숫자

                    = 1: 바꿀 수 있고 마지막 문자는 1개 숫자

                    = 0: 바꿀 수 없음 (T[i:i] 를 영어 문자열로 변형 x)

          > 그렇다면..

                    >> S[k+1] = 1 if S[k-1] !=0 and T[k:k+1] 이 27 이하

                    >> S[k+1] = 2 if S[k] != 0

                    >> S[k+1] = 0 otherwise

                    > 마지막 위치의 값을 구한 다음 거꾸로 읽어나가면 된다

 

#세 수의 합(FB)

# n개의 수가 주여져 있을 때, 어떤 수 k 가 주어졌을 때, 주어진 수중 세개의 수의 합이 k가 되는 경우를 모두 구하시오

          > O(n^2) 풀이

                              >> 주어진 수들을 오름차순으로 정렬

                              >> 왼 -> 오 순으로 읽어 나가는에, 이번에 읽은 수가 a 일 때, 남은 문제는 a 보다 큰 두 수의 합으로 k-a를 만들 수 있으면 된다.

                              >> 비교해 보면 되므로 모든수에 O(n^2), hi, lo pointer 정의

                              >> 예를 들어 다음 배열이 있다 [2,3,5,7,11]

                              >> 합이 14가 되게 만들고 싶을 때, 최소값 2 에 lo pointer, 최대값 11에 high pointer.

                              >> 2+ 11 < 14 이므로 lo pointer를 한칸 올린다. 3 + 11 = 14 이므로 [3:11] 이 답에 추가

                              >> lo = hi 가 되면 종료

 

 

# 낚시 

# 총 N 개의 점으로 이루어진 다각형 모양의 낚시터가 있을 때, K개의 낚시터가 원 안에 들어오는 최소 반지름을 구하시오

          > 원 안의 두 점은 두점을 이은 선이 반드시 원 안에 있다

          > 각 다각형마다 중심에서 가장 먼 점을 구한다

          > 이 점이 원 안에 있다면, 해당 다각형에 속한 모든 점은 원 안에 있다

          > 총 K개의 이런 점이 원 안에 들어오는 최소 반지름을 구하면 된다

 

# AhChoo

# 길이가 n인 두 정수 수열이 있을 때 각 대응되는 점의 차이가 제곱의 합이 최고가 되는 경우를 구하시오

          > A[1...n], B[1...n] 에 대해 D[i][j]를 A 와 B 의 답이라 하자

          > D[1][1] 의 답은 자명하다

          > 그렇다면 D[i][j]의 값을 알고 있을 때, D[i+1][j] 의 값은 어떻게 구할 까?

                    > A[i+1] 이 B[i] 에 대응 된다면, (A[i+1] - B[j]) ^ 2  + D[i][j-1]

                    > A[i+1] 이 B[j-1] 에 대응된다면, (A[i+1] - B[j])^2 + (A[i+1] - B[j-1]) ^2 + D[i][j-2] .. 

                    > 이 중 최소값이 D[i+1][j]의 값

                    > 총 O(n^3)

 

# MT 게임

# A, B 두 과 사람들이 다음과 같은 게임을 한다. 이때 A 는 a 명, B는 b명이다

# N, K 가 주어졌을 때 1부터 시작해서 모든 학생은 1부터 시작해서 최소 한개, 최대 K개의 연속한 숫자를 부르고 N을 부르는 학생이 속한 과가 진다.

# A 가 먼저 시작한다

          > A 그룹은 최소 a 최대 aK 사이의 수를 부를 수 있다

          > N 이 1 ~ a 사이의 수라면 A 가 진다

          > N 이 a+1 ~ a+b사이면 B가 진다

          > N 이 aK + 1 ~ aK+b 사이라면 B가 진다

          > 두 배열 winA, winB 를 생성 : winA[i] 는 i 가 남았을때 A가 이기면 True, 아니면 false

 

# 작업 배치

# 여러가지의 작업이 있고 이 작업을 A ~ Z 로 표현. 작업 하나당 1의 시간이 걸린다.

# 한 작업을 끝내면 k번은 다른 작업을 해야할 때, N개의 작업이 문자열로 주어졌을 떄, 모든 작업을 가장 빠른 시간 내에 끝내는 배치를 구하시오

          > max heap 을 만들어 작업을 다음 형태로 저장 (남은 작업 수, 가장 마지막에 이 작업을 한 시간)

                    > 작업이 많이 남을 수록, 작업을 한 시간이 작을수록 힙에서 위로 올라간다

          > AAABBBCCC, k = 2라면 처음에 힙에 A:(3,0) B:(3,0), C:(3,0) 이 들어있다.

          > 빈 큐를 하나 생성

                    i = 1: 힙의 루트가 A라면 A를 내보내고 힙에서 A를 제거, 다음 큐에 A:(2,1)을 추가 (A)

                    i = 2: 힙에는 B,C가 들어있고 둘 중 하나 B를 뽑아내어 큐에 추가, A(2,1) , B(2,2)    (A,B)

                    i = 3: 힙에는 C만 들어있고 뽑아낸다. 이제 힙은 empty, 큐에는 A(2,1)B(2,2)C(2,3), (A,B,C)

                    i = 4: 큐의 맨 앞 원소는 A(2,1) 이므로 A가 할 수 있는일.

                              > 큐의 맨앞이 A(2,1)이므로 이 값을 때버 힙에넣고 다시 루트를 제거

                              > A(1,4) 가 큐에 추가된다. (ABCA)

          > 총 시간복잡도: O(N log N)

 

#Job Assignment

# n개의 작업, m 개의 서버가 있을때, i 번째 작업은 A[i]개의 유닛으로 이루어 지고, j번째 서버에는 B[j] 개의 슬롯이 있다

# 작업에 속한 모든 유닛은 모두 다른 서버에서 동작해야 한다.

# 각 작업 수 n, 각 서버 슬롯 m 이 주어졌을때, 이 서버에서 동작이 가능한지 불가능한지 판별

          > 만약 작업이 k개의 유닛으로 이루어져 있을때, 1개 이상의 슬롯이 남아있는 서버가 k개 미만일 경우 불가능

          > 모든 작업의 유닛 수를 내림차순으로 정렬, 모든 서버도 남은 슬롯을 내림차순으로 정렬

          > n 개의작업에 대해 반복하며, 서버 슬롯이 남아있지 않을 때 작업이 남아있다면 불가능