해커를 꿈꾸는 개발자

파이썬 / BOJ 백준 / 1904번 01타일 - dp

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

문제 

지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다.

어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다.
그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되었다.) 또한 N=4일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2진 수열을 만들 수 있다.

우리의 목표는 N이 주어졌을 때 지원이가 만들 수 있는 모든 가짓수를 세는 것이다. 단 타일들은 무한히 많은 것으로 가정하자.

풀이 

1. 위와 같이 규칙을 찾아냅니다.
2. d[n] = d[n-2] + d[n-1] 구조의 피보나치 수열임을 알 수 있습니다.
3. 모든 2진 수열의 개수는 너무 큰 값을 가지고 있기 때문에, 문제의 출력에서 제시한 대로 15746을 나눈 나머지를 출력하도록 합니다.

전체코드

n = int(input())

dp = [0] * 1000001
dp[1] = 1
dp[2] = 2

for k in range(3,n+1):
    dp[k] = (dp[k-1]+ dp[k-2])%15746

print(dp[n])

파이썬 / BOJ 백준 / 9184번 신나는 함수 실행 - dp

문제

if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns:
  1

if a > 20 or b > 20 or c > 20, then w(a, b, c) returns:
  w(20, 20, 20)

if a < b and b < c, then w(a, b, c) returns:
  w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)

otherwise it returns: w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)

위의 함수를 구현하는 것은 매우 쉽다. 하지만, 그대로 구현하면 값을 구하는데 매우 오랜 시간이 걸린다. (예를 들면, a=15, b=15, c=15)
a, b, c가 주어졌을 때, w(a, b, c)를 출력하는 프로그램을 작성하시오.

풀이

1. 문제에서 주어진 함수를 그대로 사용하면, 시간초과가 발생합니다.
2. 재귀함수를 사용할 때, 동일한 계산을 수행하지 않도록 메모이제이션을 사용하는 방법을 묻는 문제입니다.
3. 계산한 값을 dp[a][b][c]에 저장하고, 이후 a, b, c를 구할 때, 계산하지 않고, 저장한 dp[a][b][c]를 return하게 되면 수행시간이 기하급수적으로 단축됩니다.

전체코드

import sys

def w(a1,b1,c1):
    if dp[a1][b1][c1] != -1:
        return dp[a1][b1][c1]

    if a1 <= 0 or b1 <= 0 or c1 <= 0:
        dp[a1][b1][c1] = 1
        return dp[a1][b1][c1]
    if a1 > 20 or b1 > 20 or c1 > 20:
        dp[a1][b1][c1] = w(20, 20, 20)
        return dp[a1][b1][c1]
    if a1 < b1 and b1 < c1:
        dp[a1][b1][c1] = w(a1, b1, c1-1) + w(a1, b1-1, c1-1) - w(a1, b1-1, c1)
        return dp[a1][b1][c1]
    else :
        dp[a1][b1][c1] = w(a1-1, b1, c1) + w(a1-1, b1-1, c1) + w(a1-1, b1, c1-1) - w(a1-1, b1-1, c1-1)
        return dp[a1][b1][c1]

    pass

dp = [[[-1 for _ in range(n)] for _ in range(n)] for _ in range(n)]
while True:
    a,b,c = map(int, sys.stdin.readline().split())

    if a == -1 and b == -1 and c == -1:
        break

    result = w(a,b,c)
    p = f'w({a}, {b}, {c}) = {result}'
    print(p)

파이썬 / 백준 알고리즘 / 1260번 DFS와 BFS 문제 및 풀이

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

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오.
단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다.
한 간선이 여러 번 주어질 수도 있는데, 간선이 하나만 있는 것으로 생각하면 된다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

예제 입력 및 출력

문제 풀이

너비우선탐색(BFS, Breadth First Search)와 깊이우선탐색(Depth First Search)의 전형적인 기초 문제입니다. 이 두 알고리즘은 그래프를 탐색하기 위한 알고리즘으로 모든 정점을 탐색하기 위해 사용됩니다.

DFS는 한 경로로 탐색하다가 특정 상황에서 최대한 깊숙히 들어가서 확인한 뒤 다시 돌아가 다른 경로로 탐색하는 방식이고,(스택의 방식을 이용함, 스택은 기본 동작이라 스택 자료 구조를 이용할 필요는 없음)
BFS는 갈림길에 연결되어 있는 모든 경로를 한번씩 탐색한 뒤 다시 연결되어 있는 모든 경로를 넓게 탐색하는 방식입니다. (자료 구조 큐 또는 덱 구조를 이용해야 함)

예를 들어 아래와 같은 그래프에서 DFS 동작은 다음과 같습니다. 
1) 정점 1에서부터 검색 시작
2) 1에 연결된 정점 2,3,4 중 가장 작은 수인 2(방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문해야 된다고 기입 됨)를 방문
3) 2에 연결된 정점 4를 방문
4) 4에 연결된 정점 3을 방문
5) 더이상 방문할 정점이 없으므로 종료
- 결국 1->2->4->3 순으로 방문하게 됩니다

예를 들어 아래와 같은 그래프에서 BFS 동작은 다음과 같습니다.
1) 정점 1에서부터 검색 시작 
2) 정점 1과 연결된 2를 검색(방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문해야 된다고 기입 됨) 
3) 정점 1과 연결된 3을 검색(방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문해야 된다고 기입 됨) 
4) 정점 1과 연결된 4를 검색 
- 결국 1->2->3->4 순으로 방문하게 됩니다. 

전체 코드

from collections import deque

def dfs(v):
    print(v, end=' ')
    visit[v] = 1
    for i in range(1, n + 1):
        if visit[i] == 0 and adj[v][i] == 1:
            dfs(i)

def bfs(v):
    queue = deque()
    visit[v] = 1
    queue.append(v)

    while (queue):
        v = queue.popleft()
        print(v, end=' ')
        for i in range(1, n + 1):
            if visit[i] == 0 and adj[v][i] == 1:
                queue.append(i)
                visit[i] = 1

#입력 n : 정점의 개수, m : 간선의 개수, v : 탐색을 시작할 정점의 번호
n, m, v = map(int, input().split())
adj = [[0] * (n + 1) for i in range(n + 1)]
visit = [0 for i in range(n + 1)]
for i in range(m):
    x, y = map(int, input().split())
    adj[x][y] = 1
    adj[y][x] = 1

#출력
dfs(v)
print()

visit = [0 for i in range(n + 1)]
bfs(v)