*문제 본문은 강의 내용과 관련되어 있어 자세하게 적지 않았습니다. 문제 N개의 정수가 주어지면 그 숫자들 중 K개를 뽑는 조합의 합이 임의의 정수 M의 배수인 개수는 몇 개가 있는지 출력하는 프로그램을 작성하세요. 풀이 • 내 풀이 import sys input = sys.stdin.readline def DFS(index, start): global cnt if index == K: if sum(res)%M == 0: cnt += 1 else: for i in range(start, len(numbers)): res[index] = numbers[i] DFS(index+1, i+1) N, K = map(int, input().split()) numbers = list(map(int, input().s..

*문제 본문은 강의 내용과 관련되어 있어 자세하게 적지 않았습니다. 문제 1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 M개를 뽑는 방법의 수를 출력하는 프로그램을 작성하세요. 풀이 • 답안 : Python import sys input = sys.stdin.readline def DFS(index, start): global count, delete_num if index == M: for i in range(M): print(c[i], end=' ') count += 1 print() else: for i in range(start, N+1): c[index] = i DFS(index+1, i+1) N, M = map(int, input().split()) c = [0] * (N+1) count..

*문제 본문은 강의 내용과 관련되어 있어 자세하게 적지 않았습니다. 문제 가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다. 그리고 둘째 줄부터 차례대로 파스칼의 삼각형처럼 위의 두 개를 더한 값이 저장되게 된다. N과 가장 밑에 있는 숫자가 주어져 있을 때 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성하시오. (단, 답이 여러가지가 나오는 경우에는 사전 순으로 가장 앞에 오는 것을 출력하여야 한다.) 풀이 • 답안 : Python import sys input = sys.stdin.readline def DFS(index, sum): if index == N and sum == F: for i in p: print(i, end=' ') sys.exit(0) # 만족하는 것이 여러가지 있지만 그 ..

*문제 본문은 강의 내용과 관련되어 있어 자세하게 적지 않았습니다. 문제 1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 M개를 뽑아 일렬로 나열하는 방법을 모두 출력합니다. 풀이 • 답안 : Python import sys input = sys.stdin.readline def DFS(index): global count if index == M: for i in range(M): print(res[i], end=' ') print() count += 1 return else: for i in range(1, N+1): if visited[i] != 1: res[index] = i visited[i] = 1 DFS(index+1) visited[i] = 0 N, M = map(int, input()..

문제 다음과 같이 여러 단위의 동전들이 주어져 있을 때 거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다. 풀이 • 답안 : Python import sys input = sys.stdin.readline def DFS(L, sum): global res # CUT EDGE if L > res: return if sum > m: return if sum == m: if L < res: res = L else: for i in range(n): DFS(L+1, sum+a[i]) n = int(input()) a = list(map(int, input().split())) a.sort(reverse=True) m = int(input()) res = ..

*문제 본문은 강의 내용과 관련되어 있어 자세하게 적지 않았습니다. 문제 1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 중복을 허락하여 M번을 뽑아 일렬로 나열하는 방법을 모두 출력합니다. 풀이 • 답안 : Python import sys input = sys.stdin.readline # 상태트리가 여러 가지로 뻗어있는 문제 def DFS(index): global count if index == M: for j in range(M): print(res[j], end=' ') print() count += 1 else: for i in range(1, N+1): res[index] = i DFS(index+1) N, M = map(int, input().split()) res = [0] * M c..

*문제 본문은 강의 내용과 관련되어 있어 자세하게 적지 않았습니다. 문제 철수는 그의 바둑이들을 데리고 시장에 가려고 한다. 그런데 그의 트럭은 C킬로그램 넘게 태울 수가 없다. 철수는 C를 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶다. N마리의 바둑이와 각 바둑이의 무게 W가 주어지면, 철수가 트럭에 태울 수 있는 가장 무거운 무게를 구하는 프로그램을 작성하세요. 풀이 • 답안 : Python import sys input = sys.stdin.readline def DFS(index, sum, tsum): global result if sum+(total-tsum) C: return # C보다 작은 경우만 따짐 if index == N: # 최..

*문제 본문은 강의 내용과 관련되어 있어 자세하게 적지 않았습니다. 문제 N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 'YES'를 출력하고, 그렇지 않으면 'NO'를 출력하는 프로그램을 작성하세요. 둘로 나뉘는 두 부분집합은 서로소 집합이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어야 합니다. 풀이 • 답안 : Python import sys input = sys.stdin.readline def DFS(index, sum): # total 절반을 넘으면 의미가 없음 (시간복잡도 단축) if sum > (total//2): return # 종료 지점 if index == N: # total..

*문제 본문은 강의 내용과 관련되어 있어 자세하게 적지 않았습니다. 문제 자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램을 작성하세요. 풀이 • 답안 : Python import sys input = sys.stdin.readline def DFS(v): # 종료지점 if v == (N+1): for i in range(1, N+1): if checked[i] == 1: print(i, end='') print() else: checked[v] = 1 # 부분집합으로 사용하겠다. DFS(v+1) checked[v] = 0 # 부분집합으로 사용하지 않겠다. DFS(v+1) N = int(input()) checked = [0] * (N+1) # 방문 여부 체크 D..

*문제 본문은 강의 내용과 관련되어 있어 자세하게 적지 않았습니다. 문제 아래 그림과 같은 이진트리를 전위순회와 후위순회를 연습해보세요. 1) 전위순회 출력 : 1 2 4 5 3 6 7 2) 중위순회 출력 : 4 2 5 1 6 3 7 3) 후위순회 출력 : 4 5 2 6 7 3 1 cf.) 전위 / 중위 / 후위 가 결정되는 기준 : Root 노드에 방문을 하는 시점 (제일 먼저 / 중간에 / 나중에) 풀이 • 내 풀이 - 전위순회 import sys input = sys.stdin.readline def DFS(num): if num > 7: return else: print(num, end=" ") DFS(num*2) DFS(num*2+1) DFS(1) • 내 풀이 - 중위순회 import sys i..

*문제 본문은 강의 내용과 관련되어 있어 자세하게 적지 않았습니다. 문제 10진수 N이 입력되면 2진수로 변환하여 출력하는 프로그램을 작성하세요. 단 재귀함수를 이용해서 출력해야 합니다. 풀이 • 내 풀이 import sys input = sys.stdin.readline def DFS(num): if num > 0: DFS(num//2) print(num%2, end='') N = int(input()) DFS(N) • 답안 : Python import sys input = sys.stdin.readline def DFS(N): if N == 0: return else: DFS(N//2) print(N%2, end='') #스택을 사용하기 때문에 출력 아래 -> 위 N = int(input()) DFS..

*문제 본문은 강의 내용과 관련되어 있어 자세하게 적지 않았습니다. 문제 후위연산식이 주어지면 연산한 결과를 출력하는 프로그램을 작성하세요. 풀이 • 내 풀이 import sys input = sys.stdin.readline e = input().rstrip() stack = list() for i in e: if i.isdecimal(): stack.append(int(i)) else: b = stack.pop() a = stack.pop() if i=='+': value = a+b elif i=='-': value = a-b elif i=='*': value = a*b else: value = a/b stack.append(value) print(stack[0]) • 답안 : Python impor..