Algorithm: 문제풀이 2

직사각형 (SCPC 2016)

# n 개의 직사각형이 있다.

# 직사각형의 포함 관계에서 가장 많은 직사각형들이 서로 포함 된 경우, 이 직사각형의 수를 구하시오

          > 각 직사각형을 기준으로 다른 모든 직사각형을 순회하면서 포함관계를 확인한다.

          

 

3n + 1 (SCPC 2016)

# 자연수 n 이 주어지면 이 수를 짝수이면 반으로 나누고 홀수이면 3배한 후 1을 더한다

# 이 과정을 거치면 어떤 수던지 1이 된다는 것이 알려져 있다

# 정확하게 K(<= 63) 번 이 과정을 반복했을 때 1이 되는 수중 가장 큰 수와 가장 작은 수를 구하시오

 

          > 이 때 가장 큰 수는 2^n 임이 자명함

          > 1 부터 재귀적으로 올라가며 (현재 수 -1) % 3 == 0 일 때를 구해 재귀적으로 올라가며 모든 수에 대해 n 번 반복했을 때 최소값

 

징검다리 (SCPC 2016)

# 0 번 부터 n 번 까지 번호가 매겨진 징검다리가 있다.

# 다리를 건너는데 오른쪽으로 한 칸 부터 k칸 까지 건너갈 수 있고 두가지 제약 조건이 있다

# 이 때, 지뢰가 묻혀진 돌들이 있어서 밟으면 안되며 연속해서 두번 같은 칸을 뛰면 안된다.

# n번 돌까지 가는 가짓수를 구하시고

          > D[i][k] 를 i 번째 까지 오는데, 마지막 움직인 걸음 수가 k 인 가짓수

          > S[i] 는 i 번째 까지 오는 방법의 수

          > S[i] = sum(D[i][k])

          > i 번 째칸에 지뢰가 있다면 D[i][k] = S[i] = 0

          > D[i][j] = S[i-j] - D[i-j][j]

 

개구리 뛰기 (SCPC 2015)

# 일직선 상에 돌들이 있고, 개구리가 처음 좌표 0 에 있고 좌표 0 에는 항상 돌이 있다

# 개구리가 최대 K칸 뛸 수 있을 때, 가장 마지막 돌에 도착할 수 있다면 최서 점프 수를 구하시오

# 예를 들어 돌이 [0, 1, 2, 5, 7,9, 10,12,15] 에 있고 개구리가 최대 K = 4 칸 뛸 수 있다면 5번.

          > Greedy Algorithm을 사용한다.

          > 개구리는 가능한 가장 먼 돌로 점프해야 그 다음에 뛸 때 더 먼 돌로 뛴다.

 

          > 개구리위치는 처음에 0, 만약 고려하는 돌이 현재 위치 + K 이내: OK

          > 만약 목적지 돌이면 점프 횟수 출력

          >만약 아니면 개구리 위치는 바로 직전 돌

          > 다음에 고려할 돌은 이번 돌 부터

          > 개구리의 위치가 불변이면 불가능

 

Famous

# n 명의 사람이 있을 때, 어떤 사람 j 가 다른 n-1 명의 사람을 모두 모르지만 다른 사람들은 모두 j를 알고 있다면 j 는 famous

# n 명중 famous 한 사람을 찾는 프로그램

# 입력으로는 n명의 사람수, i 가 j를 아는지는 doesKnow(i,j)를 통해 알 수 있다.

          > 어떤 사람이 famous 한지는 brute force 로 O(n^2)내에 모두 점검하는 방법으로 알 수 있다

          > O(n) 풀이

                    >> 처음에는 n 모두 유명한 사람 "후보" 이다

                    >> 두 사람 A B 를 골라서 doesKnow(A, B) 를 했을때

                              if(True): A is not famous

                              if(False): B is not famous

                    >> 즉 질문 한번마다 후보가 줄어든다

 

n1 + n2

# 한 수 n1 이 있다.# 이 수에서 숫자 하나를 지워서 다른 수 n2를 만들자# n1 + n2 = n 이다.# n 이 주어졌을때 n1, n2 를 모두 구해라

 

          > 방법1: n1 은 0이상 n 이하이므로 모두 다 해본다

          > 방법2: n의 가장 높은 자리가 a 라면 n1 의 가장 높은 자리수는 a 또는 a-1

          > 방법3: 편의상 n1 = a * 1000 + b * 100 + c * 10 + d = abcd

                    >> n2 는 다음중 하나 [abc, abd,acd,bcd]

                    if ( n2 == abc )

                              n = abcd + abc = abc * 10 + d + abc = abc * 11 + d

                    if (n2 == abd)

                              n = abcd + abd = abc *10 + ab * 10 + 2 * d

                    n = a' b' c' d' 라고 할때 d' = 2 * d 또는 10 + d' = 2d

                    두가지 모두 풀면 d를 얻을 수 있고 각각 

                              - a'b'c'를 abc , ab 두 수의합

                              - a'b'c' -1 을 abc, ab 두 수의 합으로 구해야 한다

                    O ( log n) 시간