Coding Test

동전 분배하기 (DFS)

분석 풀이 """ N개의 동전을 A, B, C 세명에게 나누어 주려고 합니다. 세 명이 받은 각각의 총액을 계산해 총액이 가장 큰 사람과 가장 작은 사람의 최소차를 출력 단 세 사람의 총액은 서로 달라야 합니다. 첫째 줄에는 동전의 개수 N(3

동전 바꿔주기 (DFS)

분석 풀이 """ k가지 동전이 각각 n1, n2, ... , nk개 T원의 지폐를 동전으로 바꿔 주려고한다 입력으로 지폐의 금액 T, 동전의 가지수 k, 각 동전 하나의금액 pi와 개수 ni가 주어질 때 (i=1,2,...,k) 지폐를 동전으로 교환하는 방법의 가지 수 첫째 줄에는 지폐의 금액 T(0

[2624] 동전 바꿔주기 (DP)

2624번: 동전 바꿔주기 명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방법은 여러 가지가 있을 www.acmicpc.net 분석 dp[i][j] : i번째 동전까지 사용해서 j원을 만들 수 있는 경우의 수 dp[money] += dp[money - coin * cnt] (money는 구하기 위한 금액, coin은 현재 사용하는 동전의 금액, cnt는 사용하는 동전의 개수) 풀이 """ 입력으로 지폐의 금액 T 동전의 가지 수 k 각 동전 하나의 금액 pi와 개수 ni가 주어질 때 (i=1, 2,…, k) 지폐를 동전으로 교환하는 방법의 가지 수 """ t=int(i..

[17610] 양팔저울(DFS, 브루트포스)

17610번: 양팔저울 무게가 서로 다른 k개의 추와 빈 그릇이 있다. 모든 추의 무게는 정수이고, 그릇의 무게는 0으로 간주한다. 양팔저울을 한 번만 이용하여 원하는 무게의 물을 그릇에 담고자 한다. 주어진 모든 추 www.acmicpc.net 분석 풀이 """ 무게가 서로 다른 K개의 추, 모든 추 무게의 합 S {1, 5, 7}이면 S=13이고, 그릇에 담을 수 있는 물의 무게는 {1, 2, 3, 4, 5, 6, 7, 8, 11, 12, 13}이고, 1부터 S사이에서 무게에서 9와 10에 대응하는 무게의 물을 담을 수 없다. K(3

휴가(삼성 SW역량평가 기출문제 : DFS활용)

DP [14501번] 퇴사 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net bottom up n = int(input()) s = [list(map(int, input().split())) for i in range(n)] dp = [0 for _ in range(n+1)] for i in range(n): for j in range(i karla.tistory.com 풀이 """ N+1일째 되는 날 휴가, 남은 N일 동안 최대한 많은 상담 상담을 완료하는데 걸리는 날수 T와 상담을 했을 때 받을 수 있는 금액 P 휴가를 가기 위해 얻을 수 있는 최대 수익 첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다. 둘째 줄부터 1일부터 N일까지 순서대로 주..

최대점수 구하기(DFS)

""" N개의 문제, 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩니다. 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다. 첫 번째 줄에 문제의 개수N(1

[1167] 트리의 지름(BFS, 그래프)

1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 분석 임의의 노드에서 가장 긴 경로로 연결돼 있는 노드는 트리의 지름에 해당하는 두 노드 중 하나 그래프를 인접 리스트로 저장 BFS를 수행하고 탐색할 때 각 노드의 거리를 리스트에 저장 2에서 저장한 리스트에서 임의의 노드와 가장 먼 노드를 찾고, 그 노드부터 BFS 다시 수행 3에서 저장한 거리 리스트 값 중 가장 큰 값을 이 트리의 지름으로 출력 풀이 """ 트리를 구성하는 노드 중 두 노드 사이의 거리가 가장 긴 것 정점개수V V개의 줄에..

[2178] 미로 탐색(BFS)

2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 풀이 """ 두 정수 N, M(2 ≤ N, M ≤ 100) M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. """ import sys from collections import deque input = sys.stdin.readline n, m = map(int, input().split()) # 네 방향 탐색을 위한 상수 → ↓ ← ↑ dr=[0,1,0,-1] dc=[1,0,-1,0] visited= [[False for j in range(m)] for i in r..

[13023] ABCDE(친구관계 파악하기, DFS, 백트래킹, 그래프)

13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 분석 [1260번] DFS, BFS 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. karla.tistory.com 풀이 import sys input=sys.stdin.readline sys.setrecursionlimit(10000) n,m=map(int,input().split()) # 사람수, 친구관계수 list = [[] for _ in range(n+1)] for _ in..

[2023] 신기한 소수(DFS, 백트래킹)

2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 분석 자리수가 한 개인 소수 2,3,5,7부터 탐색 시작 자릿수가 두개인 현재수*10+a를 계산하여 소수인지 판단, 소수라면 재귀 함수로 자릿수를 하나 늘림 a가 짝수인 경우는 항상 2를 약수로 가지므로 가지치기로 a가 짝수인 경우 제외 자릿수를 n까지 확장했을 때 그 값이 소수라면 해당 값 출력 풀이 """ 소수 7331 : 733, 73, 7 소수 (왼쪽부터 1,2,3,4 자리 모두 소수) n(1~8)자리 숫자 중 신기한 소수 찾기 """ impo..