1. 알고리즘 관련 공부
이번 주는 공부했던 알고리즘 지식을 정리하려 한다.
예제) 최대점수 구하기(DFS)
이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다. 각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩 니다. 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다. (해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.)
▣ 입력설명
첫 번째 줄에 문제의 개수N(1<=N<=20)과 제한 시간 M(10<=M<=300)이 주어집니다.
두 번째 줄부터 N줄에 걸쳐 문제를 풀었을 때의 점수와 푸는데 걸리는 시간이 주어집니다.
▣ 출력설명
첫 번째 줄에 제한 시간안에 얻을 수 있는 최대 점수를 출력합니다.
▣ 입력예제 1
5 20
10 5
25 12
15 8
6 3
7 4
▣ 출력예제 1
41
해설)
어떤 문제를 고를 것인지에 대한 부분집합 문제로 생각해야한다.
문제 하나당 레벨 하나로 생각하고 1. 문제를 고르는 경우의 수, 2. 문제를 고르지 않는 경우의 수 이 두 가지 노드로 트리를 생각하자.
트리를 구성할 때 정지 조건 중 하나는 제한시간을 넘어갈 때이다.
그래서 if문의 정지 코드를 걸기 위해 DFS()의 인자에 레벨과 점수의 합, 시간의 합을 넘긴다.
또다른 정지 조건으로는 당연히 레벨이 끝에 다다랐을 때이다.
이 때 res를 글로벌 변수로 받아 만약 점수의 합이 res보다 클 때 그걸 스왑하는 코드를 적어준다.
메인 함수의 마지막에 res를 출력하면 된다.
# 내가 풀기로 한 문제들을 부분집합으로 받는다.
# {1,2,3,4,5}의 문제 중
# 점수와 시간을 비교해서 부분집합을 만들어 푼다.
# {1,2,3}을 시간 내에 풀 수 있다.
# 상태트리 -> 1번을 푼다, 풀지 않는다.
# 2번을 푼다, 풀지 않는다.
# 3번을 푼다 풀지 않는다.
def DFS(level,sum,time):
global res
# 시간은 m을 넘어서면 안 된다.
if time > m:
# 가지치기
return
# 상태 트리의 마지막 레벨에 접근했을 때
if level == n:
# 점수의 최댓값 찾기
if sum > res:
res = sum
else:
# 상태 트리 중에 문제를 푸는 노드 접근
# 레벨 하나 추가, 합에 추가, 시간 추가
DFS(level+1, sum + pv[level], time + pt[level])
# 상태 트리 중에 문제를 안 푸는 노드 접근
DFS(level+1, sum , time)
if __name__ == "__main__":
n,m = map(int, input().split(" "))
pv = list() # problem value
pt = list() # problem time
for i in range(n):
a,b = map(int, input().split())
pv.append(a)
pt.append(b)
res = 0
DFS(0,0,0) # 레벨, 총점, 시간
print(res)
예제) 휴가(삼성 SW역량평가 기출문제 : DFS활용)
카운셀러로 일하고 있는 현수는 오늘부터 N+1일째 되는 날 휴가를 가기 위해서, 남은 N일 동 안 최대한 많은 상담을 해서 휴가비를 넉넉히 만들어 휴가를 떠나려 한다.
현수가 다니는 회사에 하루에 하나씩 서로 다른 사람의 상담이 예약되어 있다.
각각의 상담은 상담을 완료하는데 걸리는 날수 T와 상담을 했을 때 받을 수 있는 금액 P로 이 루어져 있다.
만약 N = 7이고, 아래와 같이 예약이 잡혔있다면
1일에 잡혀있는 상담은 총 4일이 걸리며, 상담했을 때 받을 수 있는 금액은 20이다. 만약 1일 에 예약된 상담을 하면 4일까지는 상담을 할 수가 없다.
하나의 상담이 하루를 넘어가는 경우가 많기 때문에 현수는 예약된 모든 상담을 혼자 할 수 없어 최대 이익이 나는 상담 스케쥴을 짜기로 했다.
휴가를 떠나기 전에 할 수 있는 상담의 최대 이익은 1일, 5일, 7일에 있는 상담을 하는 것이 며, 이때의 이익은 20+30+10=60이다.
현수가 휴가를 가기 위해 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.
▣ 입력설명
첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.
둘째 줄부터 1일부터 N일까지 순서대로 주어진다. (1 ≤ T ≤ 7, 1 ≤ P ≤ 100)
▣ 출력설명
첫째 줄에 현수가 얻을 수 있는 최대 이익을 출력한다.
▣ 입력예제 1
7
4 20
2 10
3 15
3 20
2 30
2 20
1 10
▣ 출력예제 1
60
해설)
리스트 인덱스에서 현재 인덱스의 상담을 할 것인지, 안 할 것인지로 상태트리 구성이 된다.
일정을 저장하는 T 리스트와 금액을 저장하는 P 리스트를 만들어야 한다.
여기서 고려해야할 것은 상담 기간이 휴가 예정 날짜인 8일을 넘어가는지 안 넘어가는지다.
또한 날짜를 인덱스로 사용하기 위해서는 맨 처음 날짜가 0번이 아니라 1번 인덱스가 되어야 한다.
그래서 insert함수를 써서 빈 값(0,0)을 두 리스트에 넣는다.
함수 종료 조건은 레벨이 n+1과 같을 때다.
왜 n+1이냐면 7번 인덱스 또한 상담 예약의 일종으로 보아야 하기 때문에
만약 7번에 접근했다 하면 상담을 안 하더라도 한 번 DFS()를 돌아야하기 때문이다.
따라서 휴가 날짜인 8일 째에 코드를 정지 시켜야하고 이를 위해서 정지코드가 레벨 == n+1이 되는 것이다.
그래서 DFS()의 상태 노드 조건에서 n+1과 같거나 적은 일정을 가지게 된다면을 넣은 것이다.
만약 n+1보다 적거나 같다면 상담을 하고 sum에 일정에 맞는 금액을 더한다.
그게 아니면 해당 인덱스의 일정의 상담을 하지 않는다.
최대값을 찾는 것은 정지 코드 아래에 res를 이용하여 스왑을 통해 찾는다.
# 이 문제에서 레벨은 l + ti가 된다.
# 종료 지점은 n+1일이다. 중요
# 날짜, 합계
def DFS(L, sum):
global res
# 종료 지점
if L == n+1:
# res 갱신
if sum > res:
res = sum
else:
# 상담을 할 때 다음 날짜가 휴가 전 날짜여야한다.
if (L + T[L]) <= n+1:
# 상태트리 노드 -> 상담을 하고 다음 날짜를 선택할 때
# 상담을 하고 난 다음 날짜
DFS(L + T[L], sum+P[L])
# 상태트리 노드 -> 상담을 안 할 때
DFS(L+1,sum)
if __name__ == "__main__":
n = int(input())
T = list()
P = list()
for i in range(n):
a,b = map(int,input().split())
T.append(a)
P.append(b)
res = 0
# 리스트의 0번 인덱스는 값을 0을 넣어야한다. 출발점이다.
# insert를 안 해준다면 리스트의 0번부터 값이 채워지기 때문에 맞지 않다.
# 따라서 insert로 0번 인덱스에 값을 채워서 하나씩 자리를 밀어야 한다.
# 즉 인덱스 번호를 날짜로 사용하는 것이다. 이게 핵심이다
# 날짜로 값을 접근한다는 개념을 알아두자
T.insert(0,0)
P.insert(0,0)
# 날짜를 넘긴다.
DFS(1,0)
print(res)
예제) 양팔 저울(DFS)
무게가 서로 다른 K개의 추와 빈 그릇이 있다. 모든 추의 무게는 정수이고, 그릇의 무게는 0 으로 간주한다. 양팔저울을 한 번만 이용하여 원하는 물의 무게를 그릇에 담고자 한다.
주어진 모든 추 무게의 합을 S라 하자. 예를 들어, 추가 3개이고, 각 추의 무게가 {1, 2, 6}이 면, S=9이고, 양팔저울을 한 번만 이용하여 1부터 S사이에 대응되는 모든 무게의 물을 다음과 같이 그릇에 담을 수 있다. X는 그릇에 담는 물의 무게이고, ⎕은 그릇을 나타낸다.
만약 추의 무게가 {1, 5, 7}이면 S=13이고, 그릇에 담을 수 있는 물의 무게는 {1, 2, 3, 4, 5, 6, 7, 8, 11, 12, 13}이고, 1부터 S사이에서 무게에서 9와 10에 대응하는 무게의 물을 담을 수 없다.
K(3<=K<=13)개의 추 무게가 주어지면, 1부터 S사이의 정수 중 측정이 불가능한 물의 무게는 몇 가지가 있는 지 출력하는 프로그램을 작성하세요.
▣ 입력설명
첫 번째 줄에 자연수 K(3<=K<=13)이 주어집니다.
두 번째 줄에 K개의 각 추의 무게가 공백을 사이에 두고 주어집니다. 각 추의 무게는 1부터 200,000까지이다.
▣ 출력설명
첫 번째 측정이 불가능한 가지수를 출력하세요.
▣ 입력예제 1
3
1 5 7
▣ 출력예제 1
2
해설)
여기서 측정이 불가능한 가짓 수는 측정이 가능한 최대 값 - 측정이 가능한 가짓수의 식을 통해 구할 수 있다.
상태 트리는 추를 1. 왼 쪽에 놓을 지, 2. 오른 쪽에 놓을 지, 3. 안 놓을 지로 결정된다.
좀 더 생각해보자면 추를 왼 쪽에 두면 추의 무게를 sum에 더하고, 오른 쪽에 두면 sum에서 빼고, 안 놓으면 그대로 sum을 반영한다.
문제의 경우 1, 5, 7 이렇게 3개의 추가 레벨이 된다. L => (0,1,2,3) 3일 때 정지가 된다.
오른 쪽에 추를 둔다는 개념에서 -를 붙인다는 개념으로 접근하면 된다.
다만 여기서 염두해 두어야할 점은 x 무게가 나오면 이를 뒤집어서 - x가 나온다는 점이다.
왼 쪽 오른 쪽 개념으로 접근하기 때문에 결국 같은 무게로 -무게의 경우 무시해버리면 된다.
또한 중복되는 무게가 있을 수 있으니 set() 자료구조를 통해 중복을 제거한다.
측정이 가능한 최댓값은 모든 추들의 무게를 더하면 된다.
측정이 가능한 가짓수는 set()에 중복을 제거한 가지들을 모아두고 len()함수로 길이를 뽑으면 된다.
이를 통해 측정이 불가능한 가짓 수를 도출할 수 있다.
# 측정이 불가능한 가짓수 = 측정이 가능한 최댓값 - 측정 가능한 가짓수
# 상태트리 -> 1. 왼쪽에 놓을지 , 2. 오른쪽에 놓을지, 3. 안 놓을지
# 3개의 노드를 가진다.
# 여기서 추로 무게를 뺼 수 있다.
# 가령 추를 왼쪽에 두고 다른 추를 오른쪽에 두면 그 차이를 잴 수 있다.
# 문제의 경우 1 5 7인데 이 경우
# 1 5 7 기본 3개
# 오른쪽에 추를 둔다는 것을 가정하면
# 1 + 7 - 5, 7 - 5, 7 - 1 등등 생성이 된다.
# 즉 추를 왼쪽에 둘건지(더할건지), 추를 오른쪽에 둘건지(뺼건지), 추를 안 둘건지(합에 아무 영향 안 줄 건지)
# 이런 관점으로 봐야한다.
# 0에서 출발, 1그램을 더할까? -> 왼쪽에 둔다.
# 0에서 출발, 1그램을 뺼까? -> 오른쪽에 둔다.
# 0에서 출발, 1그램을 쓰지 말까? -> 안씀
# 다음 레벨, -> 레벨로 다음 추 인덱싱
# 근데 여기서 생각해야하는게
# -기호가 붙은 무게는 사실 방향을 반대로 본다면 대칭으로 +로 생각 가능하다.
# 즉 중복이 생긴다. 그래서 -기호는 체크 안 해도 된다.
def DFS(L,sum):
global res
# 레벨이 끝까지 간 경우
if L == n:
if 0<sum<=s:
# 중복이 존재한다. 노드를 거치면서 같은 값이 존재한다.
res.add(sum)
else:
# 세가지 노드, 이걸 더할 거냐, 뺼 거냐, 안 쓸 거냐
# 상태 노드 3갈래
DFS(L+1,sum+G[L])
DFS(L+1,sum-G[L])
DFS(L+1,sum)
if __name__ == '__main__':
n = int(input())
G = list(map(int,input().split()))
# 추로 잴수 있는 최댓값
s = sum(G)
# set이라는 자료구조, 중복을 제거할 수 있다.
# 같은 값이 무수히 나올 수 있으니까 세트를 쓰자
res = set()
DFS(0,0)
# 갯수를 셀 떄는len()함수를 쓰자
print(s - len(res))
예제) 동전 바꿔주기(DFS)
명보네 동네 가게의 현금 출납기에는 k가지 동전이 각각n1, n2, ... , nk개 씩 들어있다.
가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고한다. 이때, 동전 교환 방법은 여러 가지가 있을 수 있다.예를 들어, 10원 짜리, 5원 짜리, 1원 짜리 동전이 각각2개, 3개, 5개씩 있을 때, 20원 짜리 지폐를 다음과 같은4가지 방법으로 교환할 수 있다.
20 = 10×2
20 = 10×1+5×2
20 = 10×1+5×1+1×5
20 = 5×3+1×5
입력으로 지폐의 금액 T, 동전의 가지수 k, 각 동전 하나의금액 pi와 개수 ni가 주어질 때 (i=1,2,...,k)
지폐를 동전으로 교환하는 방법의 가지 수를 계산하는프로그램을 작성하시오. 방법의 수는 231 을 초과하지않는 것으로 가정한다.
▣ 입력설명
첫째 줄에는지폐의 금액 T(0<T≤10,000), 둘째 줄에는 동전의 가지 수k(0<k≤10), 셋째 줄부터 마지막 줄까지는 각 줄에 동전의금액 pi(0<pi≤T)와 개수 ni(0<ni≤10)가 주어진다. pi와 ni 사이 에는 빈 칸이 하나씩 있다.
▣ 출력설명
첫 번째 줄에 동전 교환 방법의 가지 수를 출력한다.(교환할 수 없는 경우는 존재하지 않는 다.)
▣ 입력예제 1
20
3
5 3
10 2
1 5
▣ 출력예제 1
4
해설)
처음에 주어지는 목표 금액이 존재한다. 여기 예시 문제의 경우 20이 그에 해당된다.
우리는 동전으로 만들 수 있는 수만 가지 방법 중에 20을 만들 수 있는 방법들을 카운팅하면 된다.
DFS() 상태트리 구성 문제 중에 제일 중요한 레벨은 동전의 가짓 수이다.
DFS()의 상태트리 노드 수는 부모 노드당 그 동전의 갯수 + 1이다. 왜냐면 0개 즉 안 쓰는 가지도 있기 때문이다.
여기서 리스트는 2개가 필요하다, 1. 동전의 값을 입력받을 리스트, 2. 동전의 갯수를 입력받을 리스트
인덱스를 맞춰서 넣는 것이 중요하다. 그리고 레벨이 k와 같다면(정지 조건) => 값이 주어진 목표 금액과 같은지 검사 후 카운팅한다.
여기서 최적화를 하기 위해서는 sum이 중간에 목표 금액보다 높아질 경우 정지하는 조건이 필요하다.
# 처음에 만들어야하는 금액 -> sum
# 종류를 받고 이걸 레벨로 인덱싱 n이 들어오면 L==n 정지 조건
# 상태 트리 가짓수 => 주어진 동전의 갯수 +1
# 왜 +1?? => 하나도 안 넣을 때를 생각하자
# 예를 들어 5원 짜리 세개가 들어왔다.
# => 0개를 넣을까, 1개를 넣을까, 2개를 넣을까, 3개를 넣을까
# 10원짜리 2개가 들어왔다.
# 0개를 넣을까, 1개를 넣을까, 2개를 넣을까
# 주어진 목표 금액보다 높다? => if 조건으로 자르기
def DFS(L,sum):
global cnt
if sum > T:
return
if L == k:
if sum == T:
cnt+=1
else:
for i in range(cn[L]+1):
DFS(L+1,sum+cv[L]*i)
if __name__ == '__main__':
T = int(input())
k = int(input())
cv = list()
cn = list()
for _ in range(k):
a,b = map(int,input().split())
cv.append(a)
cn.append(b)
cnt = 0
DFS(0,0)
print(cnt)
