Awesome

http://boj.kr/14501 

DP로도 풀 수 있고, 완전탐색(DFS)로도 풀 수 있다. N이 최대 15이므로 완전탐색으로 풀어도 문제가 없다.

하지만 항상 중요한건 아이디어로,

완전탐색으로 풀 수 있는 아이디어를 얻었다면 조금만 더 시간을 쓰면 DP로도 풀 수 있을 것이다.

완전탐색(DFS)에서도 DP와 같이 주요 해결 실마리는 해당 day를 선택하지 않음 vs 선택함이다.

문제에서는 1일부터라고 나와있지만 취향따라 0부터 시작하기로 했다.

위 그래프는 DFS 트리를 그려본 것이다. (0일, 0원)에서 시작해서

왼쪽은 (0일에 일하지 않고 +1일, 여전히 0원)

오른쪽은 (0일에 일하고 +3일, 0일 상담비) 를 의미한다.

함수가 저런식으로 양쪽으로 진행된다는 것을 보여주기 위함이다.

경계값 때문에 조금 헷갈리는 문제인데, 그럴 때는 직접 대입해보자.

N이 10으로 주어졌다고 해보자. 배열은 0부터 시작하므로 마지막 상담일자는 9일이 될 것이다.

그래프 옆에 적어뒀듯이 함수 내에서 dfs(day, total) 에서 day는 상담을 시작하는 날짜이므로 기저사례에 해당하는 것은 day = N 인 경우이다. 9일이 마지막 근무일이었는데 10일에 상담을 시작할 수는 없기 때문이다.

이렇게 생각하면 마지막 근무일을 넘겼는데도 day에 10을 넣어서 dfs를 호출하는것 자체가 이상하게 보일수가 있는데, 그럴 땐 그 날을 정산하는 날짜(max_total = max(max_total, total) & return )라고 생각하자. 저 정산 과정(기저사례처리)이 필요하기 때문!

import sys


def dfs(day, total):
    global max_total

    # 기저 사례: 일하러 갈 수 있니?
    if day >= N:
        max_total = max(max_total, total)  # 마지막 day는 정산하는 날
        return

    # 일하러 가라
    dfs(day+1, total)  # 선택 X
    if day + T[day] <= N:
        dfs(day+T[day], total+P[day])  # 선택하고 해당 일로 점프


input = sys.stdin.readline
max_total = 0
N = int(input())  # 퇴사일
T, P = [0] * N, [0] * N  # T=time, P=pay (입력)
for i in range(N):
    T[i], P[i] = map(int, input().split())
dfs(0, 0)  # 0 ~ N일까지의 최댓값
print(max_total)

http://boj.kr/14501 

페이의 최댓값을 구하려면 각각의 모든 날짜에 대해서 선택을 하거나 / 하지 않거나 모든 경우를 고려해 봐야 한다.

점화식

d[n] = max(d[n+1], d[n+T[n]] + P[n])

=

N~n일까지의 최대 페이 = max(N~n+1일까지의 최대 페이, N~n+T[n]까지의 최대 페이+n일의 페이)

=

N~n일까지의 최대 페이 = max(n일에 일을 하지 않았을 때, n일에 일을 했을 때)

즉 d[i]가 0일부터 i일까지의 페이가 아니라 i일부터 N일까지의 페이라고 생각해야 한다.

N~i일의 페이라고 생각하면 편하다. 미래에서 돌아온다고 생각.

다시한번 점화식의 의미를 하나하나 살펴보면 다음과 같다.

N : 문제에서 주어진 퇴사 전날

d[n] : N일부터 n일까지의 최대 페이 (n이 1이면 문제의 답이 된다)

d[n+1] : n일에 일을 하지 않았을 때의 페이. n일에 일을 하지 않았으므로 N일~n일의 페이 = N일~n+1일의 페이

d[n+T[n]] : N일~n+T[n]일까지의 페이. 

T[n] : n일에 있는 상담에 걸리는 시간

예를 들어 문제에서 주어진 대로 이렇게 표가 있다고 했을 때 (N=7)

답을 구하려면

d[1] = max(d[2], d[1+T[1]] + P[1]) = max(d[2], d[4] + 10) 이 된다.

7일~1일까지의 최대 페이를 구하려면

7일~2일까지의 페이 + 1일에는 쉼

7일~4일까지의 페이 + 1일에 맡은 상담을 함(10원을 받음)

둘 중에 큰 것을 선택해야 하기 때문이다.

+ 추가 설명

d[n] = max(d[n+1], d[n+T[n]] + P[n])

n일에 일을 하지 않은 게 d[n+1]이라는 건 이해하기 쉬운데,

일을 한 것이 d[n+T[n]] + P[n] 이라는 게 이해가 잘 되지 않았다. 일단 괄호가 많아서 눈에 잘 들어오지도 않는다.

풀어서 말하면 d[n + 상담일수] + n일의 상담 페이 라는 뜻이다. 

점화식 우변 max()에 안에 있는 두 값을 그림으로 다시 보자. 이번엔 n 대신 a를 써 보자.

이게 a일에 일을 하지 않았을 때를 의미하는 d[a+1]다.

빨간색은 그 사이에 벌어들인 돈이다. a일에 일을 하지 않았으므로 0원+d[a+1]이다.

이건 d[a+T[a]] + P[a] 이다. 그림 순서대로 보면 P[a] + d[a + T[a]] 이다.

마찬가지로 빨간 글씨는 페이, 그 사이 벌어들인 돈이다. 

뒤에 있는 파란 네모는 d[a + T[a]] 인데,

아직 모르므로 재귀를 호출해서 알아낼 수 있을 때까지 간 다음, 다시 d[1]로 돌아오면 답을 알아낼 수 있다.

(알아낼 수 있을 때까지=d[N]이다)

웹 프레임워크란?

- 애플리케이션 개발에 필요한 공통적인 부분을 모아 제공해주는 것. MVC 모델을 따른다.

장점

- 효율적 (기본 설계나 기능 라이브러리를 제공해 생산성이 높다)

- 유지보수가 용이하다

- 코드 재사용성이 높다

Flask ?

마이크로 웹 프레임워크

Django와는 달리 URL 라우팅, 템플릿, Cookie, Debugger 및 개발서버 등 기본 기능만을 제공

http://boj.kr/15685 

규칙을 찾아내면 되는 문제이다.

(x, y) 증가량으로 규칙을 찾아내려고 하면 눈에 잘 보이지 않는다.

문제에서 제시한 

• 0: x좌표가 증가하는 방향 (→)
• 1: y좌표가 감소하는 방향 (↑)
• 2: x좌표가 감소하는 방향 (←)
• 3: y좌표가 증가하는 방향 (↓)

를 사용한다.

0세대에서부터 K세대까지 직접 그려보는데,

새로 생겨난 변의 번호를 직접 써보면 규칙이 보인다.

K세대 드래곤 커브의 각 선분 정보를 담은 리스트를 directions 라고 하면,

K+1세대 드래곤 커브의 것은 directions을 역순으로 하고 (x+1)%4 한 것이다.

import sys


# 네 꼭짓점이 모두 드래곤 커브인 정사각형 갯수 구하기
def calc():
    ret = 0
    for i in range(SZ):
        for j in range(SZ):
            if j < SZ - 1 and i < SZ - 1:
                if board[i][j] and board[i + 1][j] and board[i][j + 1] and board[i + 1][j + 1]:
                    ret += 1
    return ret


def draw(x, y, d, generation):
    # draw 0st dragon
    directions = [d]
    board[x][y] = 1
    x += dx[d]
    y += dy[d]
    board[x][y] = 1

	# draw Kst dragons
    for g in range(1, generation + 1):
        tmp = []  # 이번 세대에 새로 생긴 선분들의 방향
        for d in reversed(directions):  # 역순
            d = (d + 1) % 4
            tmp.extend([d])
            x += dx[d]
            y += dy[d]
            board[x][y] = 1
        directions.extend(tmp)  # directions 업데이트


SZ = 101  # 전체 좌표의 크기. 0 <= x, y <= 100 이므로 크기는 101이 되어야 함
input = sys.stdin.readline
N = int(input())
all_curves = [list(map(int, input().split())) for _ in range(N)]
board = [[0] * SZ for _ in range(SZ)]
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]

for x, y, d, g in all_curves:  
    draw(y, x, d, g)  
    # 문제에서의 (x, y) = (col, row)이므로 여기서만 거꾸로 전달하고
    # 나머지 보드 위에서의 움직임은 원래 하던 row, col으로 하면 된다.

print(calc())

http://boj.kr/15684 

import sys
from copy import deepcopy


def i_is_i(ladder):
    for i in range(N):  # i가 i로 가는지 확인한다
        col = i
        for row in range(H):  # 마지막 가로줄(H) 가기 전까지 확인
            if ladder[row][col]:  # col번 세로선과 col+1번 세로선이 row번 가로선에 의해 연결되는가?
                col += 1  # 다음 세로줄로 이동
            elif 0 < col and ladder[row][col-1]:  # col-1 세로선과 col 세로선이 row 가로선에 의해 연결되는가?
                col -= 1
        if col != i:
            return False
    return True


def dfs(idx, count, max_count, ladder):
    if count == max_count:

        if i_is_i(ladder):
            print(max_count)
            exit(0)
        return
    for i in range(idx, H):  # 가로. '조합'이므로 idx를 정하고 한 번 뽑은건 더이상 보지 않도록 한다
        for j in range(N-1):  # 세로
            if ladder[i][j] != 1:
                if 0 < j and ladder[i][j-1] == 1:
                    continue
                if j < N-1 and ladder[i][j+1] == 1:
                    continue

                ladder[i][j] = 1
                dfs(i, count+1, max_count, ladder)
                ladder[i][j] = 0


if __name__ == '__main__':
    input = sys.stdin.readline
    N, M, H = map(int, input().split())  # 세로선, 가로선, 가로선후보갯수
    ladder_origin = [[0] * N for _ in range(H)]

    for _ in range(M):
        i, j = map(int, input().split())  # j번 세로줄과 j+1번 세로선을 i번째 가로선이 연결하고 있음
        ladder_origin[i-1][j-1] = 1  #

    for h_num in range(4):  # 가로줄을 0~3개 놓아봄
        dfs(0, 0, h_num, deepcopy(ladder_origin))

    print(-1)

처음 문제를 보자마자 멘붕에 빠지게했던 문제.
보통 완전탐색이나 DFS, BFS 문제는 '칸'을 탐색하게 되는데 이 문제는 line을 따라서 탐색하라고 하고 있었다.
하지만 이게 헷갈렸던 이유는 문제를 끝까지 안 봐서 그렇다.

가로선의 정보는 두 정수 a과 b로 나타낸다. b번 세로선과 b+1번 세로선을 a번 점선 위치에서 연결했다는 의미이다.

라고 문제에 분명히 나와있기 때문이다.

즉 ladder 라는 이중 리스트를 만들고, ladder[a][b] 는 사다리에서 b와 b+1 세로선 사이에 a 가로선이 있다, 라고 생각하면 되는 것이다.
구글링해보면 a와 b를 반대로 쓴 사람이 많긴 한데 나는 실제 사다리 모양과 일치시키고 싶어서 row를 가로선으로, column을 세로선으로 놓고 풀었다.

이 문제의 정답률이 낮은 이유는 첫째 '칸' 대신 'line'을 탐색하기 때문에 헷갈려서, 둘째는 시간초과가 나서 그런 것 같다. 이를 해결하기 위한 방법은 대충 몇 가지가 있다.

- 일단 주어진 사다리를 내려가는 함수부터 만들어본다.

- 그 다음 가로선을 추가하는 함수를 만들어본다.

- 둘을 연결한다.

시간초과를 줄일 수 있는 방법은...

- 놓을 수 있는 '최소' 가로선의 갯수를 구하라고 했으므로 0부터 3까지 가로선의 갯수를 올려가면서 알고리즘이 실행되도록 하고 i=i인 경우가 나온다면 곧바로 종료한다. 예를 들어 0에서 i=i인 경우가 나왔으면 1~3은 보지 않아도 되는 것.

- 놓을 가로선을 뽑을 때 순열이 아닌 조합으로 뽑는다. <-당연한건데 본인은 이것 때문에 한참 헤맸다. 25 line 참고.

- 놓을 가로선을 뽑을 때 사다리 배열을 deepcopy 해서 재귀호출하지 말고, 가로선 check->DFS호출->가로선 uncheck 식으로 진행한다.

- i_is_is 함수는 실제로 사다리를 내려가보면서 i=i인지 확인하는 함수인데, i != i인 경우가 나오면 더이상 남은 세로선은 시도하지 않고 바로 종료하도록 한다.

http://boj.kr/14891 

한 번 명령이 주어질 때 톱니바퀴들이 연쇄적으로 어떻게 회전할지에 대해 생각해보고 그대로 만들면 된다.

톱니바퀴들을 collections의 deque로 저장해서 반시계방향 회전, 시계방향 회전을 쉽게 만들었다. (rotate)

반시계, 시계 방향이 잘 와닿지 않아서 왼쪽, 오른쪽 방향 회전이라고 대충 이름붙였다.

방법은 두 가지가 있다. 하나는 반복문, 하나는 재귀.

코드는 재귀가 더 깔끔해보이지만 실행시간은 완전히 똑같았다.

재귀에 익숙해지지 않는다면 좀 처음부터 와닿긴 힘들고, 반복문이 더 이해하기 쉬운 듯 하다.

# 반복문

각 톱니바퀴의 회전 여부(-1, 0, 1)를 담을 move 리스트를 만들고,

모든 톱니바퀴들의 회전 여부를 검사하고 난 후에 move 대로 회전한다.

import sys
from collections import deque


def calc():
    ret = 0
    for i in range(4):
        if wheel[i][0] == '1':
            ret += 1 * pow(2, i)
    return ret


def start(num, direction):
    move = [0] * 4  # 톱니바퀴들의 회전 여부를 담을 move 리스트
    move[num] = direction  # 일단 주어진 톱니바퀴는 무조건 회전

    # 왼쪽 톱니바퀴들이 회전하는지?
    next_num, next_di = num, direction  # 원본 보존을 위해 next 변수 사용 (오른쪽 톱니바퀴들도 봐야 하기 때문에)
    while 0 <= next_num-1:  # next_num-1 이 회전하는지 안하는지를 볼 것임
        if wheel[next_num][6] != wheel[next_num-1][2]:
            next_di = -next_di
            move[next_num-1] = next_di
            next_num -= 1
        else:  # 움직이지 않으면 바로 빠져나온다
            break

    # 오른쪽 톱니바퀴들이 회전하는지?
    next_num, next_di = num, direction
    while next_num+1 < 4:
        if wheel[next_num][2] != wheel[next_num+1][6]:
            next_di = -next_di
            move[next_num+1] = next_di
            next_num += 1
        else:
            break

    # move 리스트에 작성한 대로 실제로 톱니바퀴를 돌림
    for n, direction in enumerate(move):
        if direction != 0:
            wheel[n].rotate(direction)


if __name__ == '__main__':
    input = sys.stdin.readline
    wheel = [deque(input()[:-1]) for _ in range(4)]
    K = int(input())
    order = [list(map(int, input().split())) for _ in range(K)]

    for num, direction in order:
        start(num-1, direction)
    print(calc())

# 재귀

톱니바퀴 번호 n과 방향 di을 매개변수로 넣어 매번 move_left 함수를 호출하고

함수 내에서는 n이 아닌 n-1 이 회전하는지 확인한다. (if wheel[n][6] != wheel[n-1][2])

회전할 수 있다면 n-1 을 매개변수로 다시 move_left 함수를 호출한다.

재귀에서 돌아올 때 rotate를 실행한다. (위에서 말했듯이 n이 아닌 n-1이 회전하는지 확인했으므로, n-1을 회전시킨다)

n이 아닌 n-1 부터 회전시켰으므로 마지막으로 n을 회전시키고 프로그램을 종료한다.

(n-1 -> n+1, move_left -> move_right 동일)

import sys
from collections import deque


def calc():
    ret = 0
    for i in range(4):
        if wheel[i][0] == '1':
            ret += 1 * pow(2, i)
    return ret


def move_left(n, di):
    if n < 1:
        return
    if wheel[n][6] != wheel[n-1][2]:
        move_left(n-1, -di)
        wheel[n-1].rotate(di)


def move_right(n, di):
    if 2 < n:
        return
    if wheel[n][2] != wheel[n+1][6]:
        move_right(n+1, -di)
        wheel[n+1].rotate(di)


def start(num, direction):
    move_left(num-1, -direction)
    move_right(num-1, -direction)
    wheel[num-1].rotate(direction)


if __name__ == '__main__':
    input = sys.stdin.readline
    wheel = [deque(input()[:-1]) for _ in range(4)]
    K = int(input())  # K번의 명령어
    order = [list(map(int, input().split())) for _ in range(K)]

    for num, direction in order:
        start(num, direction)

    print(calc())

http://boj.kr/16236 

가장 가까운 물고기는 BFS로 찾는다. 코드 내에서 fishes 리스트가 그것이다.

새로운 물고기를 먹을 때마다 상어의 위치가 변경되므로 fishes 리스트를 매번 갱신한다.

itemgetter를 이용해 물고기를 거리, row, col 순으로 손쉽게 정렬해줄 수 있다.

상어의 크기가 증가하는 규칙이 상어의 크기 += 물고기의 크기가 아니라,

상어 크기=지금까지 먹은 누적 물고기 갯수(in_belly) 일때마다 상어의 크기가 1씩 늘어난다는 점에 유의하자. 당연히 상어 크기가 늘어났으면 in_belly를 0으로 초기화해야 답이 나온다.

import sys
from collections import deque
from operator import itemgetter


def get_distance(shark):
    fishes = []
    visited = [[0] * N for _ in range(N)]
    visited[shark[ROW]][shark[COL]] = 1
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]

    queue = deque([[shark[ROW], shark[COL], 0]])
    while queue:
        r, c, dist = queue.popleft()
        for i in range(4):
            next_r = r + dx[i]
            next_c = c + dy[i]
            if 0 <= next_r < N and 0 <= next_c < N:
                if not visited[next_r][next_c]:
                    if board[next_r][next_c] <= shark[SIZE]:  # 지나갈 수 있는 물고기
                        if 0 < board[next_r][next_c] < shark[SIZE]:  # 먹을 수 있는 물고기
                            fishes.append([next_r, next_c, board[next_r][next_c], dist+1])
                        visited[next_r][next_c] = 1
                        queue.append([next_r, next_c, dist+1])

    fishes.sort(key=itemgetter(DIST, 0, 1))  # 거리, row, column 순으로 정렬
    return fishes


def start(shark):
    global in_belly
    
    sec = 0
    while True:
        fishes = get_distance(shark)
        if not fishes:  # 물고기가 없으면 종료
            print(sec)
            break
        prey = fishes[0]  # 희생양 물고기

        in_belly += 1
        if shark[SIZE] == in_belly:
            shark[SIZE] += 1
            in_belly = 0

        shark = [prey[ROW], prey[COL], shark[SIZE]]  # 상어 정보 업뎃
        board[prey[ROW]][prey[COL]] = 0
        sec += prey[DIST]
        del fishes[0]
    return


if __name__ == '__main__':
    ROW, COL, SIZE, DIST = 0, 1, 2, 3
    input = sys.stdin.readline
    N = int(input())
    board = [list(map(int, input().split())) for _ in range(N)]
    shark_sz = 2  # 상어의 기본 크기는 2
    in_belly = 0  # 누적된 먹은 물고기 갯수
    
    for i in range(N):
        for j in range(N):
            if board[i][j] == 0:
                continue
            elif board[i][j] == 9:  # 상어
                shark_init = [i, j, shark_sz]
                board[i][j] = 0  # 나중에 물고기로 착각하지 않도록 0으로 변경

    start(shark_init)

http://boj.kr/14503 

정말 꼼꼼하게 문제 조건을 살펴야 하는구나...라고 느낀 문제.

그리고 코딩 전 직접 시뮬레이션을 해보는 것이 중요하다.

import sys
from copy import deepcopy


def get_back_direction(direct):
    if direct < 2:
        return direct + 2
    else:
        return direct - 2


def get_left_direction(direct):
    if direct == 0:
        return 3
    else:
        return direct - 1


def start(row, col, di):
    visited = deepcopy(board)
    visited[row][col] = 1
    clean_area = 1  # 청소한 영역
    turn_times = 0   # 4방향을 봤는지 카운트해줌
    next_di = di  # 다음 방향

    while True:
        while turn_times < 4: 
            next_di = get_left_direction(next_di)  # 왼쪽으로 한번 돌려봐라
            turn_times += 1
            if visited[row+x[next_di]][col+y[next_di]] == 0:  # 갈 수 있으면 가고
                di = next_di
                row += x[di]
                col += y[di]
                visited[row][col] = 1
                clean_area += 1
                turn_times = 0

            # 왼쪽으로 돌렸는데 갈 수 없으면 실제로 방향을 변경하는 것은 아니고
            # while로 돌아가 다시 왼쪽으로 돌려보는 것

        back_di = get_back_direction(di)  # 4방향 모두 봤는데 갈 수 없으면 후진 시도

        # 후진할 수 있으면(=벽이 아니면) 방향은 유지하고 한칸 빽->while로 돌아가서 거기서 다시 왼쪽으로 돌려보기 시작
        if board[row+x[back_di]][col+y[back_di]] != 1:
            row += x[back_di]
            col += y[back_di]
            turn_times = 0

        # 프로그램 종료
        else:
            break

    return clean_area


if __name__ == '__main__':
    input = sys.stdin.readline
    N, M = map(int, input().split())
    r, c, d = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(N)]
    x = [-1, 0, 1, 0]
    y = [0, 1, 0, -1]
    print(start(r, c, d))

왼쪽으로 돌려볼 때 next_di 를 사용하는 이유.

di를 왼쪽으로 돌릴 때마다 바로바로 업데이트하면 4방향 모두 봤는데 막혀있을 때,

후진 전에다시 원래 방향으로 돌아와야 하기 때문이다. 

board와 로봇 청소기가 사용한 visited는 따로 사용했다. 

로봇청소기가 후진하려고 할 때 벽일 때는 바로 프로그램이 종료되어야 하지만 

청소한 영역(visited = 1)일 때는 후진 가능하기 때문이다...

다시 생각해보니 청소 영역을 2로 체크해도 됐었을 듯.