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

 

9440번: 숫자 더하기

강민이가 초등학교 3학년일 때, 담임선생님이 이런 문제를 냈었다. 숫자 1, 2, 7, 8, 9 를 사용해서 만든 두 숫자를 더했을 때, 나올 수 있는 가장 작은 수는 무엇일까요? 강민이는 이 문제의 답이 2

www.acmicpc.net

 

풀이 과정

  1. 그리디 알고리즘 문제인데 처음 생각할 때 꼬여서 어떻게 풀어야 할지 고민을 정말 많이한 문제다ㅜ
  2. 숫자를 오름차순으로 정렬한다.
    1. 숫자들로 두개의 정수를 만들어야 하므로 a, b 리스트를 만들어 둔다.
    2. a, b 리스트에 번갈아가면서 작은 숫자부터 넣어준다.
    3. a, b 리스트에서 맨 앞에 넣을때는 0이 아닌 수중에 가장 작은 숫자를 넣어주어야 한다.
    4. 리스트에 채우는 작업이 종료되면, 두 리스트를 정수화하여 더해주면 된다.
  3. 더해준 값을 출력한다.

 소스 코드

import sys
from collections import deque, defaultdict

input = lambda: sys.stdin.readline().rstrip()
while True:
    p = list(map(int, input().split()))
    numbers = defaultdict(lambda: 0)
    if p[0] == 0:
        break
    
    for n in p[1:]:
        numbers[n] += 1
    
    a = []
    b = []
    flag = True
    for i in range(p[0]):
        target = None
        if flag:
            target = a
        else:
            target = b
        for j in range(10):
            if len(target) == 0 and j == 0:
                continue
            if numbers[j] > 0:
                numbers[j] -= 1
                target.append(j)
                break
        flag = not flag

    print(int("".join(map(str, a))) + int("".join(map(str, b))))

'알고리즘[Python] > 백준 알고리즘' 카테고리의 다른 글

[ 16918 ] [ 구현 ] 봄버맨  (0) 2022.01.04
[ 17352 ] [ Union-Find ] 여러분의 다리가 되어 드리겠습니다  (0) 2022.01.03
[ 17951 ] [ 이분 탐색 ] 흩날리는 시험지 속에서 내 평점이 느껴진거야  (0) 2021.12.30
[ 23843 ] [ Greedy ] 콘센트  (0) 2021.12.29
[ 21276 ] [ 위상 정렬 ] 계보 복원가 호석  (0) 2021.12.28

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

 

17951번: 흩날리는 시험지 속에서 내 평점이 느껴진거야

시험지를 12, 7, 19, 20과 17, 14, 9, 10 으로 나누면 맞은 문제 개수의 합의 최소는 50이다.

www.acmicpc.net

 

풀이 과정

  1. 그룹의 맞은 문제의 합의 최솟값을 기준으로 이분탐색을 진행한다.
  2. 초기 left를 1, right를 10**5 * 20 + 1로 둔다. 이유는 최소 점수는 1점이고 최대 점수는 그룹이 1개이면서 시험지의 개수가 10**5개이며 각 시험지에서 맞은 문제가 모두 20개일 수 있기 때문이다.
  3. 중간값((left + right) // 2)에 대해서 몇개의 그룹이 나오는지 확인한다.
    • 맞은 개수를 더해가면서 중간값보다 커진다면 그룹의 개수를 하나 늘려주고 맞은 개수 초기화
  4. 전체 그룹의 개수가 K개보다 많다면 해당 점수로 나눌 수 있는 것이므로 따로 저장 후 오른쪽 구간 진행
  5. 전체 그룹의 개수가 K개보다 적다면 해당 점수로 나눌 수 없는 것이므로 왼쪽 구간 진행
  6. 따로 저장해둔 정답을 출력시켜 준다. 

소스 코드

import sys

input = lambda: sys.stdin.readline().rstrip()
N, K = map(int, input().split())
paper = list(map(int, input().split()))

left = 1
right = (10 ** 5 * 20) + 1

answer = 0
while left <= right:
    mid = (left + right) // 2
    group_count = 0
    score = 0
    for p in paper:
        score += p
        if score >= mid:
            group_count += 1
            score = 0

    if group_count < K:
        right = mid - 1
    else:
        answer = mid
        left = mid + 1

print(answer)

'알고리즘[Python] > 백준 알고리즘' 카테고리의 다른 글

[ 17352 ] [ Union-Find ] 여러분의 다리가 되어 드리겠습니다  (0) 2022.01.03
[ 9440 ] [ Greedy ] 숫자 더하기  (0) 2022.01.01
[ 23843 ] [ Greedy ] 콘센트  (0) 2021.12.29
[ 21276 ] [ 위상 정렬 ] 계보 복원가 호석  (0) 2021.12.28
[ 1766 ] [ 위상 정렬 ] 문제집  (0) 2021.12.27

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

 

23843번: 콘센트

광재는 전자기기 대여사업을 시작했다. 퇴근하기 전에 다음날 손님들에게 빌려줄 N개의 전자기기를 충전하려 한다. 사용 가능한 콘센트는 M개가 있고, 성능은 모두 동일하다. 전자기기들은 한

www.acmicpc.net

 

풀이 과정

  1. 시간이 오래 걸리는 전자 기기부터 충전시키는 방식으로 진행
  2. 시간을 계산하기 위해서는 최소 히프를 사용해 준다.
    1. 히프에 현재 충전중인 전자 기기가 걸리는 시간을 넣어 준다.
    2. 히프가 가득 차지 않은 경우에는 충전기 자리가 남아있는 것이므로 전자기기의 충전 시간을 그대로 넣어준다.
    3. 히프가 가득 찬 경우는 충전기가 꽉 찬 경우이므로 기기를 하나 빼준 다음에 넣어주어야 한다. 따라서 히프에서요소 하나를 빼준 후, 해당 요소의 값에 현재 전자기기의 충전 시간을 더해서 다시 히프에 넣어준다.
  3. 히프 내의 최댓값을 구해서 출력시켜 준다. 
    • 히프 내의 최댓값이 의미하는 것은 마지막으로 충전이 완료되는 시간이다.

소스 코드

import sys
import heapq

N, M = map(int, input().split())
elec = list(map(int, input().split()))
elec.sort(reverse=True)
heap = []

for e in elec:
    if len(heap) < M:
        heapq.heappush(heap, e)
    else:
        outcome = heapq.heappop(heap)
        heapq.heappush(heap, outcome + e)

print(max(heap))

'알고리즘[Python] > 백준 알고리즘' 카테고리의 다른 글

[ 9440 ] [ Greedy ] 숫자 더하기  (0) 2022.01.01
[ 17951 ] [ 이분 탐색 ] 흩날리는 시험지 속에서 내 평점이 느껴진거야  (0) 2021.12.30
[ 21276 ] [ 위상 정렬 ] 계보 복원가 호석  (0) 2021.12.28
[ 1766 ] [ 위상 정렬 ] 문제집  (0) 2021.12.27
[ 2533 ] [ Tree + DP ] 사회망 서비스(SNS)  (0) 2021.12.24

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

 

21276번: 계보 복원가 호석

석호촌에는 N 명의 사람이 살고 있다. 굉장히 활발한 성격인 석호촌 사람들은 옆 집 상도 아버님, 뒷집 하은 할머님 , 강 건너 유리 어머님 등 모두가 한 가족처럼 살아가고 있다. 그러던 어느 날

www.acmicpc.net

 

풀이 과정

  1. 이름과 연결된 자식들의 정보를 저장해 둔다.
    • 자식-(부모 or 조상)이 연결되어 있다면, 자식의 진입차수를 1 증가시켜 준다.
    • 단, 여기서 부모가 조상일수도 있음.
  2. 초기 큐에는 각 가문의 시조들을 저장해 둔다.
    • 진입차수가 0인 이름들이 각 가문의 시조들이다.
  3. 큐에서 한명씩 빼주면서 연결된 자식들의 진입차수를 1씩 감소시킨다.
    1. 진입차수가 0이 된다면, 해당 자식은 직전에 큐에서 빼준 인원의 자식이기 때문에 따로 저장해 두고, 해당 자식은 큐에 삽입하여 준다.
  4. 출력 형식에 맞추어서 출력시켜주면 된다.

소스 코드

import sys
from collections import deque

input = lambda: sys.stdin.readline().rstrip()
N = int(input())
people = set(input().split())
child = {person:[] for person in people}
edge = {person:[] for person in people}
indegree = {person:0 for person in people}
father = []

M = int(input())
for _ in range(M):
    a, b = input().split()
    indegree[a] += 1
    edge[b].append(a)
    
queue = deque()
for person in people:
    if indegree[person] == 0:
        queue.append(person)
        father.append(person)
        
while queue:
    node = queue.popleft()
    for next_node in edge[node]:
        indegree[next_node] -= 1
        if indegree[next_node] == 0:
            queue.append(next_node)
            child[node].append(next_node)

print(len(father))
print(*sorted(father))
for name in sorted(list(people)):
    print_str = name + " " + str(len(child[name]))
    if len(child[name]) != 0:
        print_str += (" " + " ".join(sorted(child[name])))
    print(print_str)

 

'알고리즘[Python] > 백준 알고리즘' 카테고리의 다른 글

[ 17951 ] [ 이분 탐색 ] 흩날리는 시험지 속에서 내 평점이 느껴진거야  (0) 2021.12.30
[ 23843 ] [ Greedy ] 콘센트  (0) 2021.12.29
[ 1766 ] [ 위상 정렬 ] 문제집  (0) 2021.12.27
[ 2533 ] [ Tree + DP ] 사회망 서비스(SNS)  (0) 2021.12.24
[ 20955 ] [ Union-Find ] 민서의 응급 수술  (0) 2021.12.23

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

 

1766번: 문제집

첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주

www.acmicpc.net

풀이 과정

  1. 문제를 푸는 순서가 있으므로 위상정렬 방식으로 풀이하는것이 좋음. 단, 문제 난이도가 낮은 것(번호가 작은 것)부터 풀어야 하므로 최소 히프를 사용하여서 구현함.
  2. 문제들의 연결 정보와 각 문제의 진입 차수를 따로 저장한다.
  3. 초기에 진입 차수가 0인 문제들을 히프에 넣는다.
  4. 히프에서 문제 하나를 꺼내고, 문제에 연결된 다른 문제들(해당 문제를 푼 다음에 풀 문제들)의 진입차수를 하나 낮추어 준다.
    1. 이 때, 진입차수가 0이 된다면 해당 문제 번호를 히프에 넣어준다.
    2. 히프에서 문제를 꺼낼 때 따로 리스트에 문제 번호를 저장해주어야 함.(정답에서 출력)

소스 코드

import heapq
import sys

input = lambda: sys.stdin.readline().rstrip()
n, m = map(int, input().split())

graph = [[] for _ in range(n+1)]
indegree = [0] * (n+1)
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    indegree[b] += 1

solve = []
heap = []

for i in range(1, n+1):
    if indegree[i] == 0:
        heapq.heappush(heap, i)

while heap:
    problem_number = heapq.heappop(heap)
    solve.append(problem_number)
    for next_problem in graph[problem_number]:
        indegree[next_problem] -= 1
        if indegree[next_problem] == 0:
            heapq.heappush(heap, next_problem)

print(*solve)

'알고리즘[Python] > 백준 알고리즘' 카테고리의 다른 글

[ 23843 ] [ Greedy ] 콘센트  (0) 2021.12.29
[ 21276 ] [ 위상 정렬 ] 계보 복원가 호석  (0) 2021.12.28
[ 2533 ] [ Tree + DP ] 사회망 서비스(SNS)  (0) 2021.12.24
[ 20955 ] [ Union-Find ] 민서의 응급 수술  (0) 2021.12.23
[ 22856 ] [ Tree ] 트리 순회  (0) 2021.12.20

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

 

2533번: 사회망 서비스(SNS)

첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 ≤ N ≤ 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다. 두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에

www.acmicpc.net

풀이 과정

  1. 아무 점이나 루트로 잡아서 진행한다.
  2. 현재 점에 연결된 방문하지 않은 모든 점들을 방문하면서 DP테이블을 갱신한다.
    1. 초기 모든 DP테이블은 점마다 [0, 1]로 설정한다.  
    2. DP[i][0]은 루트가 i점인 부분 트리에서 i점이 얼리어답터가 아닐 때의 전체 얼리어답터 최소 개수
    3. DP[i][1]은 루트가 i점인 부분 트리에서 i점이 얼리어답터일 때의 전체 얼리어답터 최소 개수
    4. 따라서, DP[i][0]은 다음 점에서는 얼리어답터가 나와야 하므로 DP[다음 점][1]을 더해준다.
    5. DP[i][1]은 다음 점에서 얼리어답터가 나올수도 있고 나오지 않을수도 있으므로 DP[다음 점][0]과 DP[다음 점][1]의 최솟값을 더해 준다.
  3. 루트 노드에서의 DP 테이블의 최솟값을 출력시켜준다.

소스 코드

import sys

sys.setrecursionlimit(10**6)

input = lambda: sys.stdin.readline().rstrip()

n = int(input())
tree = [[] for _ in range(n+1)]

for _ in range(n-1):
    src, dest = map(int, input().split())
    tree[src].append(dest)
    tree[dest].append(src)

root = 1

dp = [[0, 1] for _ in range(n+1)]
visited = [False] * (n+1)

def solve(node):
    visited[node] = True
    for next_node in tree[node]:
        if not visited[next_node]:
            solve(next_node)
            dp[node][0] += dp[next_node][1]
            dp[node][1] += min(dp[next_node][0], dp[next_node][1])
        

solve(root)
print(min(dp[root]))

'알고리즘[Python] > 백준 알고리즘' 카테고리의 다른 글

[ 21276 ] [ 위상 정렬 ] 계보 복원가 호석  (0) 2021.12.28
[ 1766 ] [ 위상 정렬 ] 문제집  (0) 2021.12.27
[ 20955 ] [ Union-Find ] 민서의 응급 수술  (0) 2021.12.23
[ 22856 ] [ Tree ] 트리 순회  (0) 2021.12.20
[ 2602 ] [ DP ] 돌다리 건너기  (0) 2021.12.16

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

 

20955번: 민서의 응급 수술

민서는 강원대학교 컴퓨터공학과의 신임 교수이다. 그녀가 저술한 효율적인 택배 배달을 위한 최적 경로 설계에 관한 연구 논문은 아직도 널리 인용되고 있다. 오늘도 열심히 강의를 하던 민서

www.acmicpc.net

 

풀이 과정

  1. 입력된 뉴런 a와 b가 같은 집합 내에 속해있는지 검사한다.
    1. 같은 집합 내에 속해있지 않다면 Union
    2. 같은 집합 내에 속해있다면 해당 뉴런은 끊어내야 하는 뉴런이므로 연산 횟수를 하나 증가시킨다.
  2. 모든 뉴런들에 대해 같은 집합에 속해있는지 검사한다.
    1. 다른 집합에 속해있다면, 두 집합을 Union 해주고 연산 횟수를 하나 증가시킨다.
  3. 연산 횟수를 출력시켜준다.

소스 코드

import sys

sys.setrecursionlimit(10**6)

input = lambda: sys.stdin.readline().rstrip()
N, M = map(int, input().split())

parent = [i for i in range(N+1)]

def find(parent, a):
    if parent[a] != a:
        parent[a] = find(parent, parent[a])
        
    return parent[a]

def union(parent, a, b):
    p1 = find(parent, a)
    p2 = find(parent, b)
    if p1 != p2:
        parent[p1] = p2

answer = 0

for _ in range(M):
    a, b = map(int, input().split())
    if find(parent, a) != find(parent, b):
        union(parent, a, b)
    else:
        answer += 1

parent_node = find(parent, 1)
idx = 1
for i in range(2, N+1):
    if find(parent, i) != parent_node:
        union(parent, i, idx)
        parent_node = find(parent, i)
        idx = i
        answer += 1

print(answer)

'알고리즘[Python] > 백준 알고리즘' 카테고리의 다른 글

[ 1766 ] [ 위상 정렬 ] 문제집  (0) 2021.12.27
[ 2533 ] [ Tree + DP ] 사회망 서비스(SNS)  (0) 2021.12.24
[ 22856 ] [ Tree ] 트리 순회  (0) 2021.12.20
[ 2602 ] [ DP ] 돌다리 건너기  (0) 2021.12.16
[ 2482 ] [ DP ] 색상환  (0) 2021.12.15

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

 

22856번: 트리 순회

노드가 $N$개인 이진 트리가 있다. 트리를 중위 순회와 유사하게 순회하려고 한다. 이를 유사 중위 순회라고 하자. 순회의 시작은 트리의 루트이고 순회의 끝은 중위 순회할 때 마지막 노드이다.

www.acmicpc.net

풀이 과정

마지막 노드인 7번 노드를 방문하는 경로를 제외하고는 양방향으로 연결되어 있음 

  1. Tree를 먼저 중위순회 해보고 마지막에 방문하는 정점이 어디인지 파악한다.
  2. 전체 간선의 개수의 두배에서 마지막에 방문하는 정점을 방문하기 위해 지나온 간선의 개수를 빼주어서 출력

소스 코드

import sys

sys.setrecursionlimit(10**6)

input = lambda: sys.stdin.readline().rstrip()
left = dict()
right = dict()

N = int(input())
parent = [0] * (N+1)
node_count = 0
for _ in range(N):
    a, b, c = map(int, input().split())
    left[a] = b
    right[a] = c

    if b != -1:
        parent[b] = a
        node_count += 1
    if c != -1:
        parent[c] = a
        node_count += 1

# 마지막 노드 구하는 파트
last_node = 0
def traverse(node):
    global last_node
    if node == -1:
        return
    traverse(left[node])
    last_node = node
    traverse(right[node])

traverse(1)
edge_count = node_count * 2
movement = 0
# 마지막 노드까지 이동 경로의 거리 구함
while last_node != 1:
    movement += 1
    last_node = parent[last_node]
print(edge_count - movement)

'알고리즘[Python] > 백준 알고리즘' 카테고리의 다른 글

[ 2533 ] [ Tree + DP ] 사회망 서비스(SNS)  (0) 2021.12.24
[ 20955 ] [ Union-Find ] 민서의 응급 수술  (0) 2021.12.23
[ 2602 ] [ DP ] 돌다리 건너기  (0) 2021.12.16
[ 2482 ] [ DP ] 색상환  (0) 2021.12.15
[ 9376 ] [ BFS ] 탈옥  (0) 2021.12.13

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

 

2602번: 돌다리 건너기

첫째 줄에는 마법의 두루마리에 적힌 문자열(R, I, N, G, S 로만 구성된)이 주어진다. 이 문자열의 길이는 최소 1, 최대 20 이다. 그 다음 줄에는 각각 <악마의 돌다리>와 <천사의 돌다리>를 나타내는

www.acmicpc.net

 

풀이 과정

  1. 경우의 수가 너무 많아질 수 있으므로 탐색으로 구하는 문제는 아닌것 같아 DP로 풀이
  2. DP로 풀이하기 위해 점화식을 도출한다.
    1. DP[i][j][0] = sum(DP[v][j-1][1] , 0<= v < i)
    2. DP[i][j][1] = sum(DP[v][j-1][0] , 0<= v < i)
    3. 여기서, DP[i][j][k]에서 i가 의미하는것은 현재 위치, j가 의미하는것은 현재 문자열이 두루마리의 몇번째에 적힌 문자열인지, k가 의미하는 것은 0일땐 악마의 돌다리, 1일땐 천사의 돌다리이다.
  3. 점화식을 이용하여 전체 경우의 수를 구한 전체 DP테이블에서 두루마리의 마지막 문자까지 간 경우의 수들만 더해주면 된다.

소스 코드

import sys

input = lambda: sys.stdin.readline().rstrip()
target = input()
s1 = input()
s2 = input()

dp = [[[0] * 2 for _ in range(len(target))] for _ in range(len(s1))]

for i in range(len(s1)):
    if s1[i] == target[0]:
        dp[i][0][0] = 1
    if s2[i] == target[0]:
        dp[i][0][1] = 1

for i in range(len(s1)):
    for j in range(1, len(target)):
        if s1[i] == target[j]:
            for k in range(i):
                dp[i][j][0] += dp[k][j-1][1]

        if s2[i] == target[j]:
            for k in range(i):
                dp[i][j][1] += dp[k][j-1][0]

answer = 0
for i in range(len(s1)):
    answer += (dp[i][len(target)-1][0] + dp[i][len(target)-1][1])

print(answer)

'알고리즘[Python] > 백준 알고리즘' 카테고리의 다른 글

[ 20955 ] [ Union-Find ] 민서의 응급 수술  (0) 2021.12.23
[ 22856 ] [ Tree ] 트리 순회  (0) 2021.12.20
[ 2482 ] [ DP ] 색상환  (0) 2021.12.15
[ 9376 ] [ BFS ] 탈옥  (0) 2021.12.13
[ 9465 ] [ DP ] 스티커  (0) 2021.12.11

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

 

2482번: 색상환

첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다.

www.acmicpc.net

 

풀이 과정

  1. 전체적인 점화식은 다음과 같다. 
    • dp[i][j] = dp[i-1][j] + dp[i-2][j-1]
    • dp[i][j]는 j번 칠했을 때 i번 위치에서의 경우의 수이다.
    • 설명하자면, dp[i-1][j]->dp[i][j]는 i에서 칠하지 않는 경우의 수이고 dp[i-2][j-1]은 i에서 칠하는 경우의 수이다.
  2. DP를 두번 진행한다. 한번은 맨 첫번째 색상환을 칠하는 경우, 다른 한번은 첫번째 색상환을 칠하지 않는 경우이다. 이 때 주의해야 할 점은 첫번째 색상환을 칠하는 여부에 따라 dp 테이블 초기화 방식이 다르다는 점이다. 이 점 때문에 시간 많이 잡아먹음..ㅋㅋ
  3. 맨 첫번째 색상환을 칠하는 경우에는 마지막 색상환을 칠해선 안되므로 dp[N-1][K]
  4. 맨 첫번째 색상환을 칠하지 않는 경우는 마지막 색상환을 칠할 수 있으므로 dp[N][K]
  5. 두 합을 구해서 출력시켜준다.

소스 코드

 

import sys

input = lambda: sys.stdin.readline().rstrip()

N = int(input())
K = int(input())

answer = 0
selected = True

div = 1000000003
for i in range(2):
    dp = [[0] * (K+1) for _ in range(N+1)]
    for i in range(1, N+1):
        if not selected:
            dp[i][1] = i-1
            dp[i][0] = 1
        else:
            dp[i][1] = 1
            dp[i][0] = 0

    for i in range(2, N+1):
        for j in range(2, K+1):
            dp[i][j] += dp[i-1][j]
            if i >= 2 and j >= 1:
                dp[i][j] += dp[i-2][j-1]

            dp[i][j] %= div

    if selected:
        answer += dp[N-1][K]
    else:
        answer += dp[N][K]
        
    answer %= div
    selected = not selected
    
print(answer)

'알고리즘[Python] > 백준 알고리즘' 카테고리의 다른 글

[ 22856 ] [ Tree ] 트리 순회  (0) 2021.12.20
[ 2602 ] [ DP ] 돌다리 건너기  (0) 2021.12.16
[ 9376 ] [ BFS ] 탈옥  (0) 2021.12.13
[ 9465 ] [ DP ] 스티커  (0) 2021.12.11
[ 21609 ] [ 구현 ] 상어 중학교  (0) 2021.12.10

+ Recent posts

티스토리툴바