Algorithm: 문제풀이 1

Subset Sum

# n 개의 서로 다른 숫자가 주어져 있다.

# 이 중 k개를 더했을 때, 정확하게 합이 S 가 되는것이 있는가

 

          방법 1> Brute force 로 모든 조합을 해본다면 O(n^k *k) 시간이 걸린다

          방법 2> n개의 숫자를 모두 정렬

                    >> 가장 큰 수와 작은수를 더했을 때 합을 구해본다

                              if (min + max < S): min 탈락

                              else if (min + max == S) : OK

                              else 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[1][a] = 1

                    >> 만약 j가 n개의 숫자에 들어있다면 D[1][j] = 1

                    

주식

# n 일간의 주식가격이 주어지고, 딱 한번 주식을 사고 딱 한번 팔 수 있을때, 얻을 수 있는 최대 이익

# [17, 30, 42, 15, 20, 50, 10, 25]

          > 방법 1: Brute force (모든 방법을 다해본다)

          > 방법 2: i 번째 날 주식을 팔아 얻을 수 있는 최대 이익은 다음과 같다

                    >> [i 번째 날 가격] - [1 ~ i 일까지 최소값]

                    >> O(n) 시간이 걸린다

          > 방법 2.1 

                    >> 첫날은 그날의 주식값이 최솟값, 이익 = 0 이다

                    >> 매 i 번째날은, 만약 i번째 날의 주식 가격이 지금까지의 최소값보다 작다면 최소값을 변경한다

                    >> 만약 아니라면 (이 날 주식가격) - (지금까지의 최소값) 이 최대 이익

 

게임 (IOI 2014)

# n 개의 노드로 이루어진 그래프가 있다.

# 이 그래프를 가지고 A,B가 게임을 하는데, A는 질문을 하고 B는 질문에 대해 답을 한다

# 만약 질문을 하는 쪽이 그래프가 연결 그래프라는 것을 알게되면 게임은 끝난다.

# 이 때 A가 (n,2) 가지의 질문을 할 수 있을때, (n,2)번 째 질문에서 A가 답을 맞출 수 있도록 하는 프로그램을 짜시오

 

-> 모든 노드가 1 부터 N 까지 번호가 매겨져 있다면 1, ... , i-1중 반드시 하나는 i와 연결되어야 한다. 이 사실을 가장 마지막에  i-1 번째 질문에만 o 나머지는 x라 답한다.

 

반지름 (ICPC 2016)

# n개의 점이 2차원 공간에 주어져있다

# 이 점들을 2개의 집합으로 나누는데, 같은 집합에 속한 가장 먼 두 점 사이의 거리의 합이 최소가 되게 나누고

# 이 거리의 합을 구해라.

 

          > 가장 먼 점 t1, t2 를 찾는다

          > 이때 두 점은 서로 다른 그룹에 있으며, 답은 t1 과 t2의 거리보다 같거나 작다

          > 나머지 점들에 대해 각각 가장 가까운 그룹을 선택하여 추가

          

최대 clique

# clique는 주어진 그래프의 부분그래프이면서 완전그래프인 것이다.

# 최대 clique는 가장 많은 노드로 이루어진 clique 이다.           

# 일반적으로 최대 clique 는 NP hard 이지만 특별한 그래프는 다항식 시간 내에 최대 clique를 구할 수 있다

# 예를들어 구간 그래프의 경우 구간 하나는 노드가 되고 두 구간이 겹치면 해당 노드들을 에지로 잇는다

          > 그렇다면 최대 clique에 속하는 모든 노드는 겹쳐야 한다.

          > 구간 그래프의 좌표를 한축을 따라 (x or y) 정렬한다.

          > 점들을 좌에서 우로 처리하며 두 점의 좌표가 겹칠때 후보 집합에 추가한다