본문 바로가기

두두의 알고리즘/문제

 (124)
[서로소 집합] 난이도2, 핵심 유형 '팀 결성' (Python) 학교에서 학생들에게 0번부터 N번까지의 번호를 부여했다. 처음에는 모든 학생이 서로 다른 팀으로 구분되어, 총 N+1개의 팀이 존재한다. 이때 선생님은 '팀 합치기' 연산과 '같은 팀 여부 확인' 연산을 사용할 수 있다. 1. '팀 합치기' 연산은 두 팀을 합치는 연산이다. 2. '같은 팀 여부 확인' 연산은 특정한 두 학생이 같은 팀에 속하는지를 확인하는 연산이다. 선생님이 M개의 연산을 수행할 수 있을 때, '같은 팀 여부 확인' 연산에 대한 연산 결과를 출력하는 프로그램을 작성하시오. 첫째 줄에 N,M이 주어진다. M은 입력으로 주어지는 연산의 개수이다. (1
[다익스트라] 난이도2, ACM-ICPC '화성 탐사' (Python) 당신은 화성 탐사 기계를 개발하는 프로그래머입니다. 그런데 화성은 에너지 공급원을 찾기가 힘듭니다. 그래서 에너지를 효율적으로 사용하고자 화성 탐사 기계가 출발 지점에서 목표 지점까지 이동할 때 항상 최적의 경로를 찾도록 개발해야 합니다. 화성 탐사 기계가 존재하는 공간은 N X N 크기의 2차원 공간이며, 각각의 칸 을 지나기 위한 비용(에너지 소모량)이 존재합니다. 가장 왼쪽 위 칸인 [0][0] 위치에서 가장 오른쪽 아래 칸인 [N-1][N-1] 위치로 이동하는 최소 비용을 출력하는 프로그램을 작성하세요. 화성 탐사 기계는 특정한 위치에서 상하좌우 인접한 곳으로 1칸씩 이동할 수 있습니다. 첫째 줄에 테스트 케이스의 수 T(1
[플로이드워셜] 난이도2, K 대회 '정확한 순위' (Python) 선생님은 시험을 본 학생 N명의 성적을 분실하고, 성적을 비교한 결과의 일부만 가지고 있다. 학생 N명의 성적은 모두 다른데, 다음은 6명의 학생에 대해 6번만 성적을 비교한 결과입니다. 1번 성적 < 5번 성적 3번 성적 < 4번 성적 4번 성적 < 2번 성적 4번 성적 < 6번 성적 5번 성적 < 2번 성적 5번 성적 < 4번 성적 A번 학생의 성적이 B번 학생보다 낮다면 화살표가 A에서 B를 가리키도록 할 때 위의 성적 결과를 다음 그림처럼 표현할 수 있습니다. 이 그림으로 유추해서 순위를 정확히 알 수 있는 학생도 있고, 알 수 없는 학생도 있습니다. 예를 들어 1번 학생은 5번 학생보다 성적이 낮고, 5번 학생은 4번 학생보다 성적이 낮으므로 1번 학생은 4번 학생보다 성적이 낮습니다. 따라서 ..
[동적계획법] 백준 14501번 '퇴사' (Python) https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 1. 리스트 뒤에서부터 거꾸로 확인 #이취코 답 n = int(input()) t = [] p = [] dp = [0] * (n+1) max_value = 0 for i in range(n): a,b = map(int,input().split()) t.append(a) p.append(b) for i in range(n-1, -1, -1): time = t[i]+i if time
[동적계획법] 난이도2, 이취코 226p '효율적인 화폐 구성' (Python) N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다. 이때 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다. 예를 들어 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수이다. 첫째 줄에는 N, M이 주어진다. (1
[이분탐색] 백준 2110번 '공유기 설치' (Python) https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 1. 처음 최소 거리는 항상 1, 최대 거리는 max-min 2. mid 거리만큼 차례대로 공유기를 설치함. (집이 1,4,8,9이고, mid가 4일 때, 1,8에 공유기 설치 가능) 3. 2개밖에 설치 못하므로 거리-1, 그 반대면 +1 #이취코 답 n,c = list(map(int,input().split())) array = [] for _..
[정렬] 백준 1715번 '카드 정렬하기' (Python) https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 1. 항상 가장 작은 크기의 두 카드 묶음을 합치는 알고리즘 계산 2. heapq 사용 3. 결과 값은 두 개 더한 값을 다 더한 값 #이취코 답 import heapq n = int(input()) heap = [] for i in range(n): data = int(input()) heapq.heappush(heap, data) result = 0 while len(heap) ..
[BFS/DFS] 백준 16234번 '인구 이동' (Python) https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 0. 해당 나라를 q에 추가하고 union = 연합번호로 변경. 0. 현재 연합 인구수랑 연합 국가 수 변수도 추가 0. q가 빌 때까지 상하좌우 나라 확인. 옆의 나라와 인구차이가 조건에 맞으면 연합에 추가 0. q가 다 끝나면 연합 국가끼리 인구 분배 1. visited 처럼 해당 나라가 아직 처리되지 않았다면(union==-1) process 함수 적용.. 후 연합 번호 증가 ..
LIST

티스토리툴바