0. 서문

오늘 시험본것과 새로운 한주를 시작하며 간단하게 풀어본 DP, 그리디 알고리즘 문제들을 적어보려한다.

1. 단지번호붙이기

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

이런류의 문제는 대체로 bfs 또는 dfs 의 틀을 짜두고 (내 경우는 bds) 추가로 dx, dy 리스트를 짜서 기준점의 상,하,좌,우를 파악하는 틀을 더하면 코드짜는 시간을 어느정도 줄여두면서 생각할 시간을 확보하기에 좋더라.

일단, 2중 for 문을 돌려서 그래프상에서 1인 지점을 찾아서 그 지점에서부터 dx, dy 를 통해 그래프를 탐색한다. 그래프를 탐색하면서 1인 부분을 0으로 바꾸고 그 횟수를 기록했다가 더이상 탐색이 불가능해지면 기록한 값을 반환하여 리스트에 저장한다. 그리고 모든 그래프가 0이 되면 값을 저장한 리스트의 크기를 출력하여 리스트를 정렬하여 그 값을 차례대로 출력한다.

원래 visited 를 써서 방문한 1의 좌표값이면 따로 체크를 안하게 할려고 했는데 해당하는 방식으로 하니 뭔가 제대로 답이 안나와서 위의 방식으로 바꾸었다.

import sys
from collections import deque
sys.setrecursionlimit(10 ** 4)
input = sys.stdin.readline


def bfs(start, end):
    visited[start][end] = True
    queue = deque()
    queue.append((start, end))
    graph[start][end] = 0
    count = 1

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = 0
                queue.append((nx, ny))
                visited[nx][ny] = True
                count += 1
    return count


n = int(input())

graph = [list(map(int, input().strip())) for _ in range(n)]
visited = [[False]*(n) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

cnt = []
for i in range(n):
    for j in range(n):
        if graph[i][j] == 1:
            cnt.append(bfs(i, j))

cnt.sort()
print(len(cnt))
for i in cnt:
    print(i)

2. 케빈 베이컨의 6단계 법칙

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

일종의 최단거리를 구하는것이라고 생각하여 다익스트라 알고리즘으로 푼 사람도 있었고, 해당 문제에서 n이 100을 넘지 않는다고 제시하였기에 벨만 포드를 통하여 푸는 사람도 있었다.
나의 경우는 그냥 평범하게 bfs 로 진행하였다.

visited 를 통하여 방문한 여부와, 방문 횟수를 체크하고 해당하는 수를 기록하여 해당 값에서 가장 낮은 수의 인덱스를 뽑아서 제출하는 방식으로 진행하였다.

import sys
from collections import deque
sys.setrecursionlimit(10 ** 4)
input = sys.stdin.readline


def bfs(start):
    visited[start] = 1
    queue = deque([start])

    while queue:
        a = queue.popleft()
        for i in person[a]:
            if not visited[i]:
                visited[i] = visited[a] + 1
                queue.append(i)


n, m = map(int, input().split())
person = [[] for _ in range(n+1)]
result = []

for _ in range(m):
    a, b = map(int, input().split())
    person[a].append(b)
    person[b].append(a)


for i in range(1, n+1):
    visited = [0] * (n+1)
    bfs(i)
    result.append(sum(visited))


print(result.index(min(result))+1)

3. 피보나치 수 2

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

난이도가 낮은 문제라 사실상 어떻게 풀었다 기 보다는 DP 의 기초가 어떻게 이루어지는지를 공부하고 그냥 코드를 적은 그런 문제였다.

분할정복과 다이나믹 프로그래밍이 다른점은 분할정복은 큰 문제를 한번에 풀기 어려우니 작게 나누어서 진행하는것 이라면 다이나믹 프로그래밍은 큰 문제에서 반복하는 작은 문제를 반복하여 문제를 해결한다는 점이었다.

import sys

def fibo(n):
    memo[0] = 0
    memo[1] = 1

    if n < 2:
        return memo[n]

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

    return memo[n]

n = int(sys.stdin.readline())
memo = [0 for i in range(n+2)]
print(fibo(n))

4. 01 타일

피보나치 수에서 크게 달라진것 없는 문제였다. 다만, 그냥 숫자만 조금 바꿔서 제출하면 메모리 초과가 걸리기 때문에 계산하는 과정에서 %15746 를 해주어야 한다는 점 정도가 예상치못했던 점이었다.

def fibo(n):
    arr[0] = 1
    arr[1] = 2

    if n < 2:
        return arr[n]

    for i in range(2, n+1):
        arr[i] = (arr[i-2] + arr[i-1])%15746

    return arr[n]


n = int(input())
arr = [0 for _ in range(n+2)]

print(fibo(n-1))

5. 동전 0

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

목표값보다 큰 동전들은 모두 빼버리고 목표값보다 작은 동전들 중에서 가장 큰 동전부터 목표값에 넣을 수 있는만큼 최대한 넣고 그 동전을 넣을 수 없다면 낮아진 목표값에 넣을 수 있는 최대크기에 동전을 반복해서 넣는것을 반복하는것으로 해결 할 수 있었다.

이보다 심화된 그리디 문제라면 이렇게 단순한 방법으로는 풀지 못하겠으나 기초적인 문제라서 단순하게 접근하여 풀 수 있었던것같다.

좀 아쉬운점이라면 python3 가 아니고 pypy3 로 통과했다는 점. 시간 복잡도를 여기서 더 줄일 방법이 마땅히 생각나지가 않았다.

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
coin = [int(input()) for _ in range(n)]
cnt = 0

for i in reversed(coin):
    if m < i:
        continue
    else:
        while m >= i:
            m = m - i
            cnt += 1

print(cnt)

6. 잃어버린 괄호

어떻게 코드를 짜야할지 구현이 쉽지 않았던 문제였다.

일단, 문제의 경우 + 부분을 가능한 먼저 처리를 해주는것이 해결의 답안인데 이걸 어떻게 해야하는지가 생각나지 않았다.

결국 해당하는 부분을 알기위해서 답안을 찾아보았는데 그냥 - 를 기점으로 입력받은 문자열을 나눠서 하면 될거라고는 생각을 못하였다.

이럴때마다 기초의 부족함을 느낀다.

import sys
input = sys.stdin.readline

a = input().split('-')

hap = 0
for i in a[0].split('+'):
    hap += int(i)

for i in a[1:]:
    for j in i.split('+'):
        hap -= int(j)

print(hap)

7. 회의실 배정

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

주어진 시간을 뒷부분을 기준으로 하여 정렬하고 그것을 기준으로 하여 시작 시간과 끝 시간을 비교하여 범위에 해당하는 값을 카운트하여 해당하는 카운트를 출력하는 방식으로 해결하였다.

import sys
input = sys.stdin.readline


def find(start, end):
    cnt = 0
    for a, b in room:
        if a >= end:
            end = b
            cnt += 1
    print(cnt)


n = int(input())
room = [list(map(int, input().split())) for _ in range(n)]
room.sort(key=lambda x: (x[1], x[0]))

find(0, 0)

8. 신입 사원

무한경쟁사회의 슬픔을 보여주는 그런 문제였다.

푸는 방법은 신입사원의 목록을 받아서 해당하는 리스트를 서류점수로 정렬 후 면접점수를 비교하여 더이상 낮은 사원이 없을때까지 카운트를 하는 방식으로 진행하였다.

import sys
input = sys.stdin.readline

n = int(input())  # 테스트케이스 수

for _ in range(n):
    m = int(input())
    member = [list(map(int, input().split())) for _ in range(m)]
    member.sort(key=lambda x: x[0])
    cnt = 1

    maxmum = member[0][1]
    for x, y in member:
        if maxmum > y:
            maxmum = y
            cnt += 1

    print(cnt)