본문 바로가기

코딩테스트

 (111)
[동적계획법] 난이도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 _..
[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..
[BFS] 백준 14502번 '연구소' (Python) https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 1. 가벽 3개를 세울 수 있는 모든 조합을 구한다. 2. 조합 순서대로 가벽을 세우고 바이러스가 퍼진 후의 안전영역을 구한다. 3. 안전영역을 비교하여 제일 큰 안전영역을 구한다. #220328 n,m = map(int,input().split()) graph = [] zero = [] for i in range(n): graph.append(list(map(int,input().split()))) for ..
[구현] 백준 15686번 '치킨 배달' (Python) https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 1. 일반 집과 치킨집 좌표 구하기 2. 모든 치킨집 중에서 m개의 치킨집을 뽑는 조합 구하기 3. 조합 하나씩 꺼내서 집마다 가장 가까운 치킨집 거리 구하고 다 더하기 4. 다 더한 치킨집 거리에서 최소 값 구하기 n,m = map(int,input().split()) city = [] chicken = [] home = [] for i in range(n): city.ap..
[구현] 백준 3190번 '뱀' (Python) https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 1. 사과 있는 곳은 1로 표시 2. 방향 지정 함수 만들기 3. q를 사용하여 뱀의 위치 저장. 사과가 없을 때 가장 왼쪽 좌표 제거하면 도미 4. 벽이나 뱀의 몸통과 부딪혔다면 종료 n = int(input()) k = int(input()) data = [[0]*(n+1) for _ in range(n+1)] info = [] for _ in range(k): a,b = map(int,input()..
LIST

티스토리툴바