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

문제 및 입출력 

풀이방법

처음의 파이프는 이와 같이 가로로 되어 있습니다. 

입력받은 N x N 의 DP행렬을 생성합니다. 각각의 행렬안에는 크기가 3인 배열이 있으며 각각 대각선, 세로, 가로입니다.

* 입력받은 행렬을 matrix로 표현합니다.

이후 DP[i][j]의 칸의 값을 구하는 방법은 다음과 같습니다.

(대각선)

matrix[i-1][j-1], matrix[i-1][j], matrix[i][j-1]의 칸이 모두 0인 경우 (모두 벽이 아닌 빈칸)

DP[i][j][0] = sum(DP[i-1][j-1])

(세로)

matrix[i-1][j-1] 이 0인 경우(벽이 아닌 빈칸)

현재칸의 세로 파이프 = 위칸에서의 대각선으로 들어온 파이프 + 위칸에서의 세로로 들어온 파이프

dp[i][j][1] = dp[i-1][j][0] + dp[i-1][j][1]

(가로)

matrix[i-1][j-1] 이 0인 경우(벽이 아닌 빈칸)

현재칸의 가로 파이프 = 왼쪽칸에서의 대각선으로 들어온 파이프 + 왼쪽칸에서의 가로로 들어온 파이프

dp[i][j][2] = dp[i][j-1][0] + dp[i][j-1][2]

코드

import sys

# 입력
N = int(input())
matrix = [list(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)]
# 대각선, 세로, 가로
dp = [[[0] * 3 for _ in range(N+1)] for __ in range(N+1)]
dp[1][2][2] = 1
for i in range(1,N+1):
    for j in range(3, N+1):
        if matrix[i-1][j-1] == 0:
            # 대각선
            if matrix[i-1][j-2] == 0 and matrix[i-2][j-1] == 0:
                dp[i][j][0] = sum(dp[i-1][j-1])
            # 세로
            dp[i][j][1] = dp[i-1][j][0] + dp[i-1][j][1]
            # 가로
            dp[i][j][2] = dp[i][j-1][0] + dp[i][j-1][2]

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

결론

처음의 초기값을 잘 주는 것을 성공적으로해서 생각보다 빨리 풀 수 있었습니다.

마지막 DP배열을 증가시키는 과정에서 다른 방법을 쓰면 DP배열을 확장하지 않아도 될 것 같지만 코드의 가독성을 위해 썼습니다.

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

문제

입출력 보기

풀이방법

m = 수의 합, n = 사용한 수의 개수

왼쪽의 표를 보게 되면 형광색으로 칠한 것의 합이 빨간색 화살표로 가리킨 숫자와 같습니다.

그 이유는 오른쪽의 한 예시를 보면 알 수 있습니다. 

예시) f(4,2)에서  1 + 3, 2 + 2, 3 + 1 이렇게 3개의 숫자입니다. 이 숫자들은 각각 1, 2, 3에 3, 2, 1를 더한 것입니다.

이 예시를 통해 정리한 식은 우하단의 식과 같습니다.

f(m, n) = f(m-1, n-1) + f(m-2, n-1) + f(m-3, n-1) -> 각각의 수들에서 1, 2, 3을 더한 수들의 합이라고 보시면 됩니다. 

코드

import sys

input=sys.stdin.readline
MAX = 1001
MOD = 1_000_000_009

# 초기값 설정
dp = [[0] * MAX for _ in range(MAX)]
dp[1][1] = 1
dp[2][1], dp[2][2] = 1,1
dp[3][1], dp[3][2], dp[3][3] = 1, 2, 1

for i in range(4, MAX):
    for j in range(1, i + 1):
        dp[i][j] = (dp[i-1][j-1] + dp[i-2][j-1] + dp[i-3][j-1]) % MOD

# 출력
N = int(input())
for i in range(N):
    n, m = map(int, input().split())
    print(dp[n][m])

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

문제

인터넷을 사용하기 위해서는 컴퓨터에 인터넷 회선을 연결하거나 Wi-Fi를 연결해야 한다. 이렇게 연결된 네트워크를 통해 컴퓨터에는 통신이 가능하다. 마음에 드는 노래나 동영상이 있는 곳에 파일을 전송해달라는 요청을 보내고 파일을 받는 식으로 말이다.

우리가 보낸 요청은 어떻게 목적지까지 도달하는 것일까? 컴퓨터에서는 패킷이라고 하는 형태로 정보를 주고 받는다. 네트워크의 유저들은 1:1로 연결되어 있지 않으므로, 일반적으로 패킷은 라우터라는 장비를 여러 번 거친다. 그러면 라우터에서는 패킷을 다른 라우터로 보내거나, 만약 목적지와 직접적으로 연결되어 있다면 그곳으로 보낼 수도 있다. 즉, 택배 회사의 물류 센터와 비슷한 역할을 한다고 보면 된다.

그림1. 네트워크에 존재하는 라우터들의 구성 예시

라우터 내부를 들여다보면 처리해야 할 패킷을 임시적으로 보관하기 위한 버퍼가 존재한다. 이 버퍼에는 라우터에 입력으로 들어온 패킷들이 순서대로 위치하고, 라우터에서는 먼저 온 패킷부터 하나씩 처리한 후 버퍼에서 제거한다. 만약 라우터가 패킷을 처리하는 속도보다 패킷이 들어오는 속도가 더 빠를경우 버퍼가 꽉 차거나 넘쳐버릴 것이다. 그렇게 되면 버퍼에 공간이 생길 때까지 입력받는 패킷은 모두 버려진다.

통신의 원리를 배웠으니까 간단하게 라우터의 작동 원리를 구현해보자. 물론 하나의 라우터만 존재한다고 가정하며, 우리가 다룰 부분은 라우터의 입출력이 주어졌을 때 버퍼의 상태가 어떻게 변하는가이다. 그러니까 라우터가 패킷을 구체적으로 어떤 방식으로 처리하고, 어디로 보내고 이런 것들은 생각하지 말자.

풀이방법

사용한 알고리즘 : 큐

1. 버퍼의 사이즈를 입력을 받습니다.

2. -1을 입력받을 때까지 실행합니다.

3. 0과 -1을 제외한 입력은 버퍼에 추가를 합니다.

4. 버퍼의 크기가 N과 같은 경우 넘어갑니다.

5. 0을 입력받은 경우 버퍼에서 하나를 제거합니다.

6. -1을 입력받은 경우 while문을 탈출합니다

7. 버퍼가 비었다면 empty, 비어있지 않다면 버퍼 내부를 출력합니다.

코드

# silver 4
# 15828번, Router

import collections
import sys

input = sys.stdin.readline
deq = collections.deque()

# Queue size 입력
N = int(input())

while True:
    temp = int(input())
    if temp == -1:
        break
    elif temp == 0:
        deq.popleft()
    else:
        if len(deq) < N:
            deq.append(temp)
        else:
            continue

#출력부
if len(deq) == 0:
    print("empty")
else:
    for i in deq:
        print(i, "", end="")

결론

큐를 사용하니까 너무 간단했다.

다행히 학교 전공으로 Router에 대해 배워서 빠르게 이해할 수 있었다. 

상당히 간단한 문제다.

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

문제

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.

이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.

N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.

풀이방법

사용한 알고리즘 : 큐 

큐를 사용한 이유는 카드를 빼고나서 뒤에 넣는 과정을 반복한다. 즉, 선입선출(FIFO, First Input First Output) 방식을 사용한다는 것을 통해서 큐를 사용했다.

과정은 이러하다

1. queue에 입력받은 숫자만큼 카드를 넣는다.

2. 큐의 사이즈가 1이 된다면 큐의 남은 숫자를 출력한다.

3. 큐의 사이즈가 1이 아니면 맨 앞의 숫자를 제거한다.

4. 맨 앞의 숫자를 제거 후 맨 뒤에 추가한다.

5. 2의 과정으로 돌아간다.

생각보다 간단한 문제이다.

코드

# silver 4
# 2164번, 카드2

from collections import deque

que = deque()

N = int(input())

# queue에 카드 넣기
for i in range(1,N+1):
    que.append(i)

# queue size 가 1 될 때까지 카드를 버리고 옮기기 반복

while len(que) != 1:
    que.popleft()
    que.append(que.popleft())

print(que[0])

결론

큐를 알고있다면 상당히 간단히 풀리는 문제이다.

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

문제

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여섯 가지이다.

• push X: 정수 X를 큐에 넣는 연산이다.
• pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 큐에 들어있는 정수의 개수를 출력한다.
• empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
• front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

풀이과정

총 3가지의 방법을 사용하면서 1번째는 실패한 것, 2번째와 3번째는 성공한 방법이다.

 1번째는 제목을 보자마자 Queue 클래스를 생각해서 봐로 구현을 해봤다. 하지만 index에서 오류가 발생했다. len을 사용해보기도 하고 queue.qsize()를 사용해봤지만 index자체에 접근을 할 수 없다고 한다. queue클래스는 index사용을 하지 않을 때 사용할 것을 알았다.

2번째는 list를 사용했다. list에서 추가와 삭제를 할 수 있는 method가 insert, append, pop 정도가 있다. 

append와 pop은 모두 list원소의 마지막만을 수정하는 method이다. 그래서 FIFO인 큐를 구현하기 위해서 insert를 사용한다.

첫번째 원소에 insert method를 사용해 삽입하고 제거할 때 pop method를 사용해서 큐를 구현했다.

3번째 collections.deque 를 사용해서 구현했다. deque는 list와 다르게 popleft, pop, appendleft, append 형식으로 왼쪽과 오른쪽을 method를 사용해 가독성이 좋게 구현할 수 있다. 이것을 통해서 2번째 방법보다 쉽고 가독성있게 구현했다.

2번째와 3번째 모두 왼쪽은 back, 오른쪽은 front이다.

코드

1번째  큐 클래스 사용

# silver 4
# 10845번, 큐

import queue, sys
N = int(input())
que = queue.Queue()

for i in range(N):
    # 명령어 입력
    cmd = sys.stdin.readline().rstrip().split()
    if cmd[0] == 'push':
        que.put(cmd[1])
    elif cmd[0] == 'pop':
        if not que.empty():
            print(que.get())
        else:
            print(-1)
    elif cmd[0] == 'size':
        print(que.qsize())
    elif cmd[0] == 'empty':
        if que.empty():
            print(1)
        else:
            print(0)
    elif cmd[0] == 'front':
        if que.empty():
            print(-1)
        else:
            # 인덱스 오류 발생
            print(que[len(que)-1])
    elif cmd[0] == 'back':
        if que.empty():
            print(-1)
        else:
            # 인덱스 오류 발생
            print(que[0])

큐 클래스는 index를 지원하지 않기 때문에 오류가 발생한다. 

2번째 list 사용

# silver 4
# 10845번, 큐
# list 사용

import sys

N = int(input())
que = list()

for i in range(N):
    # 명령어 입력
    cmd = sys.stdin.readline().rstrip().split()
    # 왼쪽이 뒤, 오른쪽이 앞
    if cmd[0] == 'push':
        que.insert(0, cmd[1])
    elif cmd[0] == 'pop':
        if len(que) == 0:
            print(-1)
        else:
            print(que.pop())
    elif cmd[0] == 'size':
        print(len(que))
    elif cmd[0] == 'empty':
        if len(que) == 0:
            print(1)
        else:
            print(0)
    elif cmd[0] == 'front':
        if len(que) == 0:
            print(-1)
        else:
            print(que[-1])
    elif cmd[0] == 'back':
        if len(que) == 0:
            print(-1)
        else:
            print(que[0])

3번째 collections.deque 사용

# silver 4
# 10845번, 큐
# collections.deque 사용

import sys, collections

N = int(input())
que = collections.deque()

for i in range(N):
    # 명령어 입력
    cmd = sys.stdin.readline().rstrip().split()
    # 왼쪽이 뒤, 오른쪽이 앞
    if cmd[0] == 'push':
        que.appendleft(cmd[1])
    elif cmd[0] == 'pop':
        if len(que) == 0:
            print(-1)
        else:
            print(que.pop())
    elif cmd[0] == 'size':
        print(len(que))
    elif cmd[0] == 'empty':
        if len(que) == 0:
            print(1)
        else:
            print(0)
    elif cmd[0] == 'front':
        if len(que) == 0:
            print(-1)
        else:
            print(que[-1])
    elif cmd[0] == 'back':
        if len(que) == 0:
            print(-1)
        else:
            print(que[0])

결론

성능차이는 크게 없는 것 같지만 가독성이 좋은 collections.deque를 사용해야겠다.

참고로 시간복잡도는 2번째 O(n) 3번째 O(1)이라고는 하는데 큰 차이를 모르겠다..