Ray`s Tech Lab

https://www.acmicpc.net/problem/1309

0마리를 배치하는 것도 가능하고, 가로 세로로 붙지 않도록 배치해야 하므로 이론상 N마리까지 배치가능하다.

1. 브루트한 방법으로 풀이

직접 0 ~ N마리의 사자들을 하나하나 배치하는 방법이 있는데, 이 방법은 러프하게 생각하면 2^2n번 정도의 연산을 하게 될텐데 n은 100,000까지 주어질 수 있으므로 시간 내에 통과할 수 없을 것이다.

그렇다면 DP나 그리디를 통한 방법을 의심헤야 한다.

2. 우선 부분문제로 쪼갤 수 있는가?

쪼갤 수 있다. K마리(K <= N)의 사자를 배치한다고 할 때

1) 첫 사자를 첫째 줄 왼쪽 칸에 배치하는 경우

2) 첫 사자를 첫째 줄 오른쪽 칸에 배치하는 경우

3) 첫 사자를 첫째 줄에 배치하지 않는 경우

로 쪼갤 수 있다.

3. 그럼 중복되는 구조가 있는가? 있다면 DP로 풀이가 가능할 것이다.

중복되는 구조 역시 있다. N개의 행에 사자 K마리를 배치한다 할 때

첫 사자를 첫 줄 왼쪽에 배치할 땐 두 번째 사자를 다음 줄의 오른쪽에 배치하거나 아예 그 줄에 배치를 안 하거나

첫 사자를 첫 줄 오른쪽에 배치할 땐 두 번째 사자를 다음 줄의 왼쪽에 배치하거나 아예 그 줄에 배치를 안 하거나

첫 사자를 첫 줄에 배치하지 않을 땐 두 번째 사자를 그 줄의 왼쪽 또는 오른쪽에 배치하거나 아예 그 줄에 배치를 안 하거나

정리하자면

f(N, K, left)를 N개의 행에 사자 K마리를 배치하는데 첫 줄 왼쪽에 사자를 두는 경우

f(N, K, right)를 N개의 행에 사자 K마리를 배치하는데 첫 줄 오른쪽에 사자를 두는 경우

f(N, K, no)를 N개의 행에 사자 K마리를 배치하는데 첫 줄에 사자를 두지 않는 경우라고 한다면

f(N, K, left) = f(N-1, K-1, right) + f(N-1, K-1, no)f(N, K, right) = f(N-1, K-1, left) + f(N-1, K-1, no)f(N, K, no) = f(N-1, K, left) + f(N-1, K, right) + f(N-1, K, no)이라는 관계를 구할 수 있고, 중복되는 케이스들을 관찰가능하다.

4. 점화식을 세워보자

사실 점화식은 위에서 이미 세웠다. dp[i][j][k]라는 배열을 만들어서 그대로 적용라면 되며, 최종적으론 dp[N][0] ~ dp[N][N]까지를 합치면 그것이 답이 될 것이다.그러나 문제가 있다. 저 식 그대로 DP배열을 만들어서 사용하자면 3차원 배열이 만들어지는데, N은 최대 10만이고 K도 N까지의 범위를 가지니 10만 X 10만 X 3 = 3백억의 크기를 갖는 배열이 만들어지고 이는 메모리 제한에 걸릴 것이다..여기서 막혔고, 많은 고민을 하다가 다른 분들이 푼 걸 참고하게 됐다..

위의 점화식은 "몇 마리의 사자를 배치하는가"에도 중점이 있는 점화식이며, 첫 줄의 왼쪽에 배치하는 경우와 오른쪽에 배치하는 경우 그리고 첫 줄에 배치를 하지 않는 경우라는 3가지 케이스로 쪼개어 경우의 수들을 관리한다. 그러나 X개의 행에서 K마리의 사자를 배치하는 여러 방법들이 있다고 할 때, 행의 수 X만 같다면 그 방법들 모두 한꺼번에 묶어서 첫 줄의 왼쪽/오른쪽에 배치하는 경우와 첫 줄에 배치하지 않는 경우라는 3가지 케이스로 분류할 수 있다. 행의 수만 같다면 마리 별로 배치하는 방법까진 고려하지 않아도 되는 것.

즉 dp[x]를 x개의 행(즉 2*x칸의 우리)에 사자들을 배치하는 방법이라 하면, dp[x] = dp[x][left] + dp[x][right] + dp[x][no]라는 3가지 케이스로 보는 게 더 편하다는 것임 

이렇게하면 점화식이 훨씬 쉬워진다.

dp[N][left] = dp[N-1][right] + dp[N-1][no]

dp[N][right] = dp[N-1][left] + dp[N-1][no]

dp[N][no] = dp[N-1][left] + dp[N-1][right] +dp[N-1][no]

N = int(input())

mod = 9901

dp = [[0, 0, 0] for _ in range(N + 1)]
dp[1] = [1, 1, 1]

for i in range(2, N + 1):
    dp[i][0] = (dp[i - 1][1] + dp[i - 1][2]) % mod
    dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % mod
    dp[i][2] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % mod

print(sum(dp[N]) % mod)

느끼고, 배운 점

이 문제의 난이도가 실버1에 불과하단 걸 알고 현타가 왔다. 다른 사람들은 쉽게 생각하는 걸 나는 어렵게 생각했구나..라면서,, 

직관적으로 N=1일때의 배치방법, N=2일때의 배치방법들을 써가면서 규칙을 찾아 쉽게 푸는 방법도 있었다. 그래도 내가 한 방법이 잘못됐다고는 생각하지 않는다. 나만의 푸는 패턴을 만들어가며 연습하면서 감각을 길러가고, 실전에선 그 감각을 토대로 직관적으로(브루트하게 풀 수 있는지 없는지 따지고 그런 과정 없이) 풀 수 있을 거라고 생각한다..

배운 점은 글쎄..잘 모르겠다. 경험만이 살 길이란 생각이 들던 문제.

https://www.acmicpc.net/problem/1759

무식하게 풀어본다면 어떻게 풀 수 있을지 어림짐작을 하려고 했는데, 못 했다. 어떻게해서 풀 수 있을지는 구상이 되는데, 그 방법을 토대로 어떻게 어림짐작을 할 수 있을지를 모르겠었다. 직관적으로 떠오른 방법은 주어진 알파벳들을 자음과 모음들로 구분하고, 자음에서는 2개 이상을 고르는 모든 조합, 모음에서는 1개 이상을 고르는 모든 조합을 서로 매핑시켜서 암호를 만드는 것이었다. 일단 떠오르는 무식한 방법(비단 브루트포스 방식이 아니더라도)에 대한 어림짐작이 잘 안되면 일단 그 방법으로 풀어보는 것도 하나의 방법이라고 한다.

파이썬에서는 순열/조합에 관해서 쓸 수 있는 편리한 라이브러리가 있다.  이를 활용하기로 했으며, 코드는 다음과 같다.

from itertools import combinations
import sys

L, C = map(int, sys.stdin.readline().split())

# data[0] = 자음, data[1] = 모음
data = [list(map(str, sys.stdin.readline().split())), []]
password_list = []
# 자음 모음 분리 .
for ch in ['a', 'e', 'i', 'o', 'u']:
    if ch in data[0]:
        data[1].append(ch)
        data[0].remove(ch)

# 주어진 알파벳들로 암호를 만들 수 있을 경우는 자음이 2개, 모음이 1개 이상인 경우
if len(data[0]) >= 2 and len(data[1]) >= 1: 

    # i는 모음의 개수를 의미
    for i in range(1, len(data[1]) + 1):
        if L - i >= 2:
            vowels = list(combinations(data[1], i)) # 가능한 모든 모음의 조합
            consos = list(combinations(data[0], L - i)) # 그로부터 생기는 가능한 모든 자음의 조합
            for v in vowels:
                for c in consos:
                    # 모음의 조합과 자음의 조합들을 합쳐 비밀번호만들기
                    password = ''.join(sorted(list(v + c)))
                    password_list.append(password)

    # 비밀번호들 사전순 정렬
    password_list.sort()

    for i in password_list:
        print(i)

모음은 총 5개까지 고를 수 있는데, 주어지는 알파벳들이 중복되어 주어지는 것이 없다고 했으므로 모음은 0개 ~ 5개까지 있을 것이다. 따라서 자음 / 모음을 분리했을 때 모음이 1개 이상, 자음이 2개 이상 있어야지 암호를 만들 수 있으므로 이에 대한 예외처리를 해준다. 

combinations()의 파라미터로 첫 번째는 반복 가능한 것(배열처럼), 두 번째는 요소의 개수를 넣어주면 첫 번째로 받은 반복 가능한 객체에서 두 번째 파라미터로 받은 개수만큼의 조합을 튜플 형태들로 반환해준다. 주어진 알파벳들로 L글자의 암호를 만든다고 할 때, 모음의 개수를 정했다면 자음의 개수는 L - 모음의 개수이므로 이를 활용해 가능한 모음의 조합과 자음의 조합들을 만들어주고 이들을 합치고 정렬하여 알파벳 순서로 된 비밀번호를 만드는 식으로 코드를 짰다.

24번째 줄, if L - i >= 2를 처음엔 넣어주지 않아 틀렸다고 나왔다. 자음은 2개 이상, 모음이 1개 이상 있어도 모음의 개수에 따라 암호를 못 만들 수도 있는 상황이 있음을 간과한 것이었다. 예를 들어 자음이 3개, 모음이 3개 있을 때 4글자짜리 암호를 만들라고 했다고 하자. 자음이 2개 이상 모음은 1개 이상있는 상황이니 비밀번호를 아예 못 만드는 상황은 아니지만, 모음이 3개인 비밀번호는 만들 수 없다! 이 경우 자음은 1개만 써야 4글자짜리 비번을 만들 수 있는데, 문제의 조건 상 자음은 2개 이상 써야 하기 때문이다. 즉 이에 대한 예외처리를 해줘야했다. 

https://www.acmicpc.net/problem/9465

이 문제를 무식하게 모든 경우의 수를 따져서 풀려고 하면 어떻게 할 수 있을까? 각 열에서 하나의 스티커만 뽑을 수 있으므로 최대 n개의 스티커를 뽑을 수 있다. 즉 각 열에 대해 위의 스티커를 뽑던가, 아래의 스티커를 뽑던가, 안 뽑던가의 3가지 갈래가 있고 n열까지 있으니 3^n개의 조합들이 나오고, 여기서 변을 공유하는 스티커를 뽑은 케이스를 쳐내야한다. 즉 이 방법의 시간복잡도는 O(3^n)정도가 될 것이고 n은 문제에서 최대 100,000으로 주어진다 했으니 연산횟수는 천문학적인(?) 숫자가 된다. 주어진 시간제한 1초 내에 이 방법으로 문제를 푸는 것은 매우 힘들다..고 봐야 한다.

그럼 어떻게 접근할 수 있는가. 그리디하게 접근한다면 일단 각 열에서 무조건 스티커를 떼는데, 가장 높은 값의 스티커들만 떼가야 한다. 그러나 당연히 이는 불가능하다. 변을 공유하는 스티커를 뗄 수 없으니 1번째 열의 스티커를 떼면 그 다음 열에서 뗄 수 있는 스티커, 또 그 다음 열에서 뗄 수 있는 스티커가 정해진다. 이 방법은 최적의 답을 도출할 수 없다.

이번엔 dp를 의심해보자. 일단 이 문제는 부분 문제로 쪼갤 수 있다. 1번째 열부터 차례차례 스티커를 떼고 n번째 열의 스티커를 뗀다고 해보자. 물론 각 열의 스티커는 안 뗄 수도 있다. 이 때 정답은 가장 큰 점수를 얻는 스티커 조합이므로, 위쪽 스티커든 아래쪽 스티커든 간에 n번째 열의 스티커는 떼야 한다. 그렇다면 답은

마지막 스티커(n번째 열)을 위쪽을 뽑은 경우

마지막 스티커(n번째 열)을 아래쪽을 뽑은 경우

이 둘 중 하나다. 여기서 단순히 n번째 열 스티커를 위쪽을 뽑았다면, 이 점수를 n - 1번째 스티커를 아래쪽을 뽑은 경우에 나오는 값에 더해야 합니다. 라고 하면 안된다.  다음 예시를 보자

1 ~ 3열까지 스티커를 뽑았을 때 나오는 최대 점수는 몇인가? 라는 문제라면 1, 2열에서 뭘 뽑던 3열에서 스티커 하나를 뽑은 케이스가 정답이 된다. 3열에서 아래쪽을 뽑은 케이스를 알기 위해 2열에서 위쪽을 뽑은 케이스를 더한다면 이 때 구해지는 점수는 2 + 2 + 25 = 29가 된다. 그러나 3열에서 아래쪽을 뽑은 케이스의 최대값은 35다! 1열에서 10을, 2열에서 아무것도 안 뽑고 3열에서 25를 뽑은 케이스. 즉, n번째 열의 위쪽을 뽑은 경우 얻는 점수의 최대는

n - 1번째 스티커를 아래쪽을 뽑은 경우의 최대누적합

n - 2번째 스티커를 뽑은 경우(위, 아래 상관없음)의 최대누적합

이 둘 중 더 큰 값에 n번째 열의 위쪽스티커의 점수를 합한 것이다. dp[1][i]이 i번째 열에서 위쪽 스티커를 뽑은 경우의 최대누적합, dp[2][i]가 i번째 열에서 아래쪽 스티커를 뽑은 경우의 최대누적합이라 하면 점화식은 다음과 같이 얻어진다.

dp[1][n] = max(dp[2][n-1], max(dp[1][n-2], dp[2][n-2]))

dp[2][n] = max(dp[1][n-1], max(dp[1][n-2], dp[2][n-2]))

이걸 고대로 코드로 옮기면 된다.

import sys

T = int(sys.stdin.readline())

for _ in range(T):
    n = int(sys.stdin.readline())
    sticker = [[0]]
    sticker.append([0] + list(map(int, sys.stdin.readline().split())))
    sticker.append([0] + list(map(int, sys.stdin.readline().split())))

    dp = [[0 for i in range(n + 1)] for j in range(3)]
    dp[1][1] = sticker[1][1]
    dp[2][1] = sticker[2][1]

    for i in range(2, n + 1):
        dp[1][i] = max(dp[2][i - 1], max(dp[1][i - 2], dp[2][i - 2])) + sticker[1][i]
        dp[2][i] = max(dp[1][i - 1], max(dp[1][i - 2], dp[2][i - 2])) + sticker[2][i]

    print(max(dp[1][n], dp[2][n]))

https://www.acmicpc.net/problem/2468

무식하게 풀어보자.

2차원 배열 형태로 필드가 주어졌을 때, 비의 양을 0부터 100까지 해주면서 생기는 영역의 개수를 하나하나 세보면 된다. 영역의 개수를 세는 것은 N * N짜리 필드의 칸들을 하나하나 순회하면서 센다고 할 때, N으로 가능한 최댓값은 100이므로 이론상 최악의 경우 100 * 100 * 100 = 100만번 정도의 계산을 하게 된다. 문제의 제한시간은 1초인데 파이썬은 1초 내에 충분히 100만번의 연산이 가능하므로 통과할 수 있으리라 어림짐작이 가능하다.

조금만 더 최적화시켜서, 비의 양을 굳이 0부터 100까지 순회할 필요는 없다. 비의 양이 0이면 안전영역의 개수는 무조건 1이고(각 영역의 높이는 무조건 1이상이므로), 비의 양이 주어진 필드의 최고높이가 되는 순간 모든 지역이 물에 잠겨 안전영역의 개수는 0이 된다. 따라서 비의 양을 0 ~ 100까지가 아니라 1 ~ 필드에서 주어진 최고높이까지만 순회하면 됨

import sys
sys.setrecursionlimit(10000)

N = int(sys.stdin.readline())
height, checked = [], []

for _ in range(N):
    height.append(list(map(int, sys.stdin.readline().split())))
    checked.append([True] * N)

# 인접한 영역들 싹 다 표시하기
def checkArea(N, r, c):
    checked[r][c] = False
    directions = [(r - 1, c), (r, c + 1), (r + 1, c), (r, c - 1)]
    for nr, nc in directions:
        if (0 <= nr < N) and (0 <= nc < N) and checked[nr][nc]:
            checkArea(N, nr, nc)  


# 빗물의 높이가 rain으로 주어졌을 때 안전영역 개수 계산
def calculate(N, rain):
    areas = 0
    # 잠기는 영역들 구하기 - False로 표현
    for r in range(N):
        for c in range(N):
            if rain >= height[r][c]:
                checked[r][c] = False
            else:
                checked[r][c] = True
    # 안전 영역 개수 구하기
    for r in range(N):
        for c in range(N):
            if checked[r][c]:
                checkArea(N, r, c)
                areas += 1
    return areas


# 안전영역의 최대 개수 리턴
def solution(N):
    # 답이 될 수 있는 값의 최소 = 1 (각 지점 높이 최소 = 1, 빗물 최소높이 = 0이므로)
    answer = 1
    for rain in range(1, 101):
        areas = calculate(N, rain)
        # 만약 특정 빗물 높이에 대해 안전영역이 0이면 break -> 빗물이 height의 최댓값과 같아진 거니까
        if areas == 0:
            break
        if answer < areas:
            answer = areas
    return answer

print(solution(N))

인접한 영역을 어떻게 셀 것인가에 대해 고민해본 문제다. 이는 재귀를 통해 방문한 지역들을 모두 방문처리(본 코드에선 cheked배열을 이용)하는 것으로 구현했다. 어떤 지점으로부터 상하좌우방향으로 1칸씩 이동하며 순회해야 할 때, checkArea함수에서 쓴 것처럼 방향배열을 설정해두고 사용하면 매우 편리하다. 아니면 다음처럼 해도 편리한 것 같다. 스터디에서 다른 스터디원이 쓰는 걸 참고했음ㅋㅋ

# global하게 방향배열 만들기
direction = [(0, -1), (0, 1), (-1, 0), (1, 0)]

# 어딘가에서 만든 함수에서 이용
def some_func(r, c):
	...
    for dr, dy in direction:
        nr = r + dr                               # 다음 row좌표구하기
        nc = c + dc                               # 다음 col좌표구하기
        ...

왜 이문제가 DFS, BFS분류에도 들어가는지 궁금했는데, 현재 위치에서 상하좌우에 있는 칸 중 잠기지 않은 칸들을 그래프처럼 표기할 수 있겠다는 생각이 든다. 그러면서 방문여부를 따지면서 "전에 방문한 적 있네? 그럼 넌 안 봐"하면서 따지니까 굳이 따지자면 내가 한 방식은 DFS인 듯.

https://www.acmicpc.net/problem/1167

문제

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.

입력

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다.

먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 거리는 모두 10,000 이하의 자연수이다.

출력

첫째 줄에 트리의 지름을 출력한다.

예제 입력 1 

5

1 3 2 -1

2 4 4 -1

3 1 2 4 3 -1

4 2 4 3 3 5 6 -1

5 4 6 -1

예제 출력 1 

11

 우선 결론적으로, 트리의 지름에 대해 알아야 풀 수 있는 문제다.

 처음에는 1을 루트노드로 잡고 DFS를 돌려서 가장 먼 거리의 노드를 구하면 그 노드까지의 거리가 트리의 지름이겠다 싶었는데, 풀다보니 "도대체 어떤 노드를 루트노드로 해줘야 가장 먼 거리의 노드까지의 거리가 트리의 지름이 될 것인가?"라는 문제에 봉착했다. 그러다가 임의의 노드(x) 하나를 루트노드로 잡고 거기서 가장 먼 거리의 노드를 구한 후, 구한 노드를 루트 노드로 잡고 거기서 다시 먼 노드를 구했을 때 구한 노드가 바로 전에 돌렸던 DFS에서의 루트노드라면 그 거리가 최장거리이지 않을까라는 생각을 하게 됐다. 왜냐하면 어쨌든 최장거리가 될 수 있는 후보들은 끝 노드와 끝 노드간의 거리들이기 때문이다. A가 만약 끝점이고, 여기서 가장 먼 거리의 노드가 B일 때 B에서 가장 먼 끝점도 A면 A와 B사이의 거리가 최장거리가 된다는 것. 근데 만약 B에서 가장 먼 거리의 노드가 A가 아니라면 A가 끝점이 아니거나, A까지의 거리보다 더 먼 거리를 가지는 끝점이 있거나 둘 중 하나가 되는 것이다.

 그럼 처음에 내 맘대로 루트노드를 1로 잡고 DFS를 돌려서 가장 먼 거리의 노드를 찾고, 다시 그 노드를 루트노드로 잡고 DFS를 돌려서 찾은 노드가 전에 돌렸던 DFS의 루트노드와 같다면, 그 때 측정한 거리가 루트의 지름이다!는 것을 알 수 있는데, 이렇게 연속된 두 번의 DFS결과를 비교하며 트리의 지름을 찾는 방식은 비효율적일것 같았다. 막말로 DFS를 몇 번 돌리게 될지도 모르는건데..그래서 그냥 루트의 지름에 대해서 공부했다.

참고한 링크 : https://blog.myungwoo.kr/112

요악하자면, 처음에 임의의 노드 하나를 루트노드로 잡고 가장 먼 거리의 노드를 찾은 다음, 그 녀석을 다시 루트노드로 잡고 가장 먼 거리의 노드를 찾으면 그 노드와의 거리가 트리의 지름이란 말이다.

암튼 뭐..그래서 코드는 다음과 같다.

import sys
sys.setrecursionlimit(10**6) # RecursionError 방지

V = int(sys.stdin.readline())
Tree = [[] for i in range(V + 1)]

for i in range(V):
    c = list(map(int, sys.stdin.readline().split()))
    for j in range(1, len(c) - 1, 2):
        Tree[c[0]].append([c[j], c[j + 1]])  # 각 노드에 연결된 노드와 간선의 길이 표현


def DFS(Tree, start_node, distance):
    for node, dis in Tree[start_node]:
        if not distance[node]:               # node까지 가는 거리가 0이라면 (기록되지 않았다면)
            distance[node] = distance[start_node] + dis  # node까지 가는 거리 기록
            DFS(Tree, node, distance)

distance = [0 for i in range(V + 1)]
DFS(Tree, 1, distance)
distance[1] = 0   # distance는 start_node에서 각 노드까지의 거리를 저장하는 리스트이므로, 자기 자신에서 출발해 자기 자신까지의 거리는 0으로 해야 함.

start_node, max_distance = -1, -1
        # 무지성으로 max(distance)를 하면 가장 먼 거리는 알 수 있는데, 어떤 노드까지의 거리
        # 인지는 모르게 돼서, 이렇게 선형탐색같은 방법으로 가장 먼 거리를 가지는 노드를 찾음
                                       
for i in range(1, V + 1):
    if distance[i] > max_distance:
        max_distance = distance[i]
        start_node = i

distance = [0 for i in range(V + 1)]
DFS(Tree, start_node, distance)
distance[start_node] = 0                  # distance는 start_node에서 각 노드까지의 거리를 저장하는 리스트이므로, 자기 자신에서 출발해 자기 자신까지의 거리는 0으로 해야 함.
print(max(distance))

 이걸 풀면서 배운 것은 배열을 통한 트리의 표현방법과, 재귀를 통한 DFS방법.

트리의 지름도 조만간 정리해서 올려야지.