Coding Test/Search

알파코드(DFS)

분석 풀이 """ 알파벳 A에는 1로, B에는 2로 이렇게 해서 Z에는 26을 할당 "BEAN"을 암호화하면 25114 알파벳으로 바꾸면 BEAAD, YAAD, YAN, YKD, BEKD, BEAN ... 암호화된 코드가 주어지면 그것을 알파벳으로 복원하는데 얼마나 많은 방법인 있는지 입력된 코드를 알파벳으로 복원하는데 몇 가지의 방법이 있는지 각 경우를 출력, 그 가지 수도 출력 단어의 출력은 사전순으로 출력 """ code=list(map(int, input())) n=len(code) # 종착점 code.insert(n,-1) # 마지막값

동전 분배하기 (DFS)

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

동전 바꿔주기 (DFS)

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

[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..