본문 바로가기

두두의 알고리즘

 (145)
[플로이드워셜] 난이도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 함수 적용.. 후 연합 번호 증가 ..
[BFS/DFS] 백준 14888번 '연산자 끼워넣기' (Python) https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 1. 연산을 할 함수를 만든다. 2. 입력값 수만큼 각 연산으로 바꾸고 조합을 만든다. 3. 1번에서 만든 함수를 반복하여 최댓값, 최솟값을 찾는다. #220328 from itertools import permutations def op(a,b,opp): if opp=='+': return a+b elif opp=='-': return a-..
[BFS] 백준 18405번 '경쟁적 전염' (Python) https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 1. 차례대로 바이러스를 퍼트려야 하므로 deque 사용 2. 바이러스 종류, 시간(s), x, y 값을 q에 담음 3. q가 있을 때, 시간이 지날 때까지 반복 4. q 순서대로 상하좌우 바이러스 증식 #220328 실패 n,k = map(int,input().split()) graph = [] for i in range(n): graph.append(list(ma..
LIST

티스토리툴바