곽의 개발 blog

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
height = list(map(int, input().split()))

def wood(height, a, n):
    sum = 0
    for i in range(n):
        if height[i] > a:
            sum += (height[i]-a)
    return sum

for i in range(max(height), 1, -1):
    result = wood(height, i, n)
    if result >= m:
        print(i)
        break

요렇게 풀었는데 예제에 대한 답은 다 정답으로 나왔지만 시간초과가 떴다.

나무들의 최대 높이에서 M미터의 나무를 가져갈 수 있을 때까지 하나씩 줄여가며 정답을 찾도록 구현했는데

아무 알고리즘을 적용하지 않아서 시간초과가 떴나 싶었다.

알고리즘 분류를 봤는데 이진 탐색으로 되어 있었다.

역시 순차탐색으로 구현했기 때문에 시간초과가 뜬 것이었다.

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
height = list(map(int, input().split()))

start, end = 1, max(height)

while start <= end:
    sum = 0
    mid = (start + end) // 2

    for l in height:
        if l > mid :
            sum += (l-mid)
    
    if sum < m:
        end = mid-1
    else:
        start = mid+1

print(end)

요렇게 이진탐색으로 수정했는데도 시간초과가 떴다...흠

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
height = list(map(int, input().split()))

start, end = 1, max(height)

while start <= end:
    sum = 0
    mid = (start + end) // 2

    for l in height:
        if l > mid :
            sum += (l-mid)
        if sum > m:   #추가된 두 줄
            break
    
    if sum < m:
        end = mid-1
    else:
        start = mid+1

print(end)

요렇게 이미 목표 길이를 넘었다면 더 이상 세지 않도록 하는 두줄을 추가했더니 시간 초과가 나지 않았다.

이번에도 아슬아슬하게 시간초과가 안 떠서 시간을 확실히 줄일 수 있는 방법이 있는 지 구글링을 해봤다.

이진 탐색 + Counter

import sys
from collections import Counter
input = sys.stdin.readline

n, m = map(int, input().split())
height = Counter(map(int, input().split()))

start = 1
end = 1000000000

while start <= end:
    mid = (start+end) // 2

    tot = sum((h-mid)*i for h, i in height.items() if h > mid)

    if tot >= m:
        start = mid+1
    else:
        end = mid-1

print(end)

나무의 높이들을 Counter 객체로 저장한다.

mid 보다 높은 높이의 나무들에 대해서만 높이차를 계산하여 개수를 곱한 값의 합을 tot 변수에 저장한다.

구글링해보니 이렇게 구현하게 되면 실행 시간이 앞의 코드의 거의 1/9이 된다고 한다.

Counter를 사용하면 내부적으로 해시 테이블을 사용하여 빠른 접근과 카운팅을 수행하기 때문에 실행 시간에 영향을 줄 수 있다고 한다.

코드

import sys
input = sys.stdin.readline

a = int(input())
num = list(map(int, input().split()))

dp = [1]*a

for i in range(a):
    for j in range(i):
        if num[j] < num[i]:
            dp[i] = max(dp[i], dp[j]+1)

print(max(dp))

최소 부분 수열의 길이가 1이기 때문에 dp 배열을 다 1로 초기화해준다.

num의 원소 i에 대하여 i보다 앞에 있는 원소들을 모두 확인할 때

만약 num[j] < num[i]를 만족한다면

dp[j] ( 인덱스 j까지의 증가하는 부분 수열의 최대 길이) + 1(num[i]) => dp[i]

가 되는 것이다.

예를 들어, 위의 예제를 살펴보면

i가 5일때 num = [10, 20, 10, 30, 20, 50]이고 dp = [1, 2, 1, 3, 2, 1] 이다.

num[i] = 50 보다 작은 인덱스 j는 0부터 4 모두 해당한다.

각각의 j 마다 dp[5] = max(dp[5], dp[4]+1)이 실행되고

결국 dp[j]가 가장 큰 dp[3]=3 에 +1한 값인 4가 dp[5]가 된다.

최종적으로 dp = [1, 2, 1, 3, 2, 4]가 되고 출력은 max(dp) = 4 이므로 4가 출력된다.

코드

import sys
from collections import deque
input = sys.stdin.readline

def dfs(v):
    visited1[v] = True
    print(v, end=' ')
    for i in range(1, n+1):
        if not visited1[i] and graph[v][i]:
            dfs(i)

def bfs(v):
    q = deque([v])
    visited2[v] = True
    while q:
        v = q.popleft()
        print(v, end=' ')
        for i in range(1, n+1):
            if not visited2[i] and graph[v][i]:
                q.append(i)
                visited2[i] = True

if __name__ == "__main__":
    n, m, v = map(int, input().split())

    graph = [[False] * (n+1) for _ in range(n+1)]

    for _ in range(m):
        a, b = map(int, input().split())
        graph[a][b] = True
        graph[b][a] = True
    
    visited1 = [False] * (n+1)
    visited2 = [False] * (n+1)

    dfs(v)
    print()
    bfs(v)

간선을 표시하기 위해 행렬을 구현하였고, 방문했는 지를 체크하기 위해 리스트를 만들었다.

DFS는 재귀함수로 구현하였고, BFS는 queue를 이용히여 구현하였다.

DFS와 BFS

DFS(Depth-First Search)와 BFS(Breadth-First Search)는 그래프를 탐색하기 위한 두 가지 주요 알고리즘이다.

각각 깊이 우선 탐색과 너비 우선 탐색을 수행한다.

차이점은 노드를 방문하는 순서와 탐색하는 방법이다.

DFS

• DFS는 한 경로를 끝까지 탐색한 후, 그 다음 경로로 넘어가는 방식이다. 즉 현재 경로를 완전히 탐색한 후 다음 경로로 넘어간다.
• 스택(Stack) 자료구조로 구현될 수 있으며 재귀 함수로도 구현할 수 있다.
• 주로 미로 찾기, 연결 요소 찾기, 위상 정렬 등에 사용된다.

BFS

• 한 노드에서 시작하여 그 노드와 가까운 노드들을 모두 탐색한 후, 그 다음으로 이동하는 방식이다. 즉, 같은 레벨의 노드들을 먼저 탐색한다.
• 큐(Queue) 자료구조를 사용하여 구현된다.
• 주변의 모든 노드를 방문한 후에 다음 레젤의 노드를 방문한다.
• 최단 경로를 찾을 때 사용된다.

코드

def d(n):
    a = str(n)
    sum = 0
    for i in range(len(a)):
        sum += int(a[i])
    return sum+int(a)

result = []
for i in range(1, 10001):
    if d(i) <= 10000:
        result.append(d(i))

for i in range(1, 10001):
    if i not in result:
        print(i)

d(n) : n을 입력값으로 받아 n과 n의 각 자리수를 더한 수를 리턴하는 함수

result 배열을 생성하고, i가 1부터 10000까지 돌면서 d(i)가 10000을 넘지 않았을 때 배열에 삽입하도록 구현하였다.

1부터 10000까지의 숫자 중 result 배열에 존재하지 않는 수들이 셀프넘버일 것이기 때문에 if문을 통해 출력하도록 하였다.

나는 배열을 사용하였지만, 중복을 제거하기 위한 set 자료형을 활용하여 푸는 것도 가능했다.

result = set()
for i in range(1, 10000):
    result.add(d[i])

for i in range(1, 10001):
    if i not in result:
        print(i)

문제

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

 

2606번: 바이러스

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍

www.acmicpc.net

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

코드

n = int(input())
v = int(input())
graph = [[] for _ in range(n+1)]
visited = [0]*(n+1)

for _ in range(v):
    a, b = map(int, input().split())
    graph[a] += [b]
    graph[b] += [a]

def dfs(v):
    visited[v] = 1
    for next in graph[v]:
        if visited[next] == 0:
            dfs(next)

dfs(1)
print(sum(visited)-1)

graph는 n+1개만큼 비어있는 리스트

컴퓨터 번호를 그대로 인덱스로 쓰고 싶어서 n+1로 생성했다.

visited 역시 동일한 이유로 n+1개의 0으로 이루어진 리스트 -> 1이면 방문 / 0이면 미방문

연결선 개수 v만큼 for문을 반복하여 입력 받은 연결선을 양방향으로 graph에 넣는다.

깊이 우선 탐색 (DFS) 알고리즘을 구현한 함수 dfs(v)

처음 방문할 컴퓨터 번호를 v로 입력 받는다.

vistied[v] = 1 로 방문을 표시한다.

graph[v]는 v에 연결되어 있는 컴퓨터들의 리스트

리스트에 들어있는 컴퓨터들을 next로 반복하며 if문을 통해 방문한 컴퓨터인 지 확인한다.

아직 방문하지 않은 컴퓨터라면 dfs(next)로 재귀 호출을 한다.

-> 결과적으로 v번 컴퓨터에 연결된 컴퓨터들을 차례대로 쭉 방문한다.

visited의 1의 개수와 같은 sum(visited)에서 첫방문 컴퓨터 1을 제외한 sum(visited)-1 을 답으로 출력한다.

NEW

dfs함수에 visited를 인자로 입력받지 않고, return 하지도 않았는데 print(sum(visited)-1)이 답이 되는 지?

-> 파이썬의 리스트는 함수 밖에서 선언되어, 함수 내부에서 변경되어도 함수 밖에서 변경이 적용된다.

dfs를 적용한 백준문제는 처음 풀어보는 것 같다.

그래도 쉬운 문제로 연습해볼 수 있어서 좋았고 다음에 관련 문제가 나왔을 때 잘 해결해나갈 수 있길 !!

시험 휴동기간동안 스터디 과제 없으니 알고리즘 개념 공부 좀 다시 해야겠댜 

import sys
input = sys.stdin.readline

n = int(input())

if n == 1 or n == 2:
    print(1)
else:
    answer = [0]*(n+1)
    answer[1] = 1
    answer[2] = 1

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

n자리 이친수를 생각해보면

n-1자리 이친수의 맨뒷자리가 0인지 1인지에 따라 답이 결정된다.

맨뒷자리가 0이라면 그 다음에 0이나 1 이 올 수 있고,

맨뒷자리가 1이라면 0만 올 수 있다.

따라서 n자리 이친수의 경우의 수는 

(맨뒷자리가 1인경우 : n-1자리 이친수의 맨뒷자리가 0이나 1인 경우 = answer[n-1])

+

(맨뒷자리가 0인경우 : n-1자리 이친수의 맨뒷자리가 1인 경우 = n-2자리 이친수의 맨뒷자리가 0이나 1인 경우 = answer[n-2])

= answer[n-1] + answer[n-2]

처음에 n이 1이나 2일 경우를 고려 안 하고 코드를 짰다가 인덱스 에러가 떴다.

동적 프로그래밍 구현할 때는 꼭 조심하기