알고리즘90 Algorithm - 휴가(DFS) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [휴가(DFS)] 카운셀러로 일하고 있는 현수는 오늘부터 N+1일째 되는 날 휴가를 가기 위해서, 남은 N일 동안 최대한 많은 상담을 해서 휴가비를 넉넉히 만들고자 한다. 현수가 다니는 회사에는 하루에 하나씩 서로 다른 사람의 상담이 예약되어 있다. 참고로, 각각의 상담은 상담을 완료하는데 걸리는 날수 T와 상담을 했을 때 받을 수 있는 금액 P로 이루어져 있다. 만약 N = 7이고, 아래와 같이 예약이 잡혔다면 1일에 잡혀있는 상담은 총 4일이 걸리며 상담을 했을 때 받을 수 있는 금액은 20이다. 또한, 1일에 예약된 상담을 하면 4일까지는 상담을 할 수 없다.. 2022. 1. 2. Algorithm - 최대점수 구하기(DFS) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [최대점수 구하기(DFS)] 현수는 선생님이 주신 N개의 문제를 풀려고 한다. 각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어져있다. 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 하는 프로그램을 작성하시오. (단, 해당문제는 해당시간이 걸리면 풀리는 것으로 간주하며 한 유형당 한 개의 문제만 풀 수 있음) *입력 설명 첫 번째 줄에 문제의 개수 N(1 ≤ N ≤ 20)과 제한시간 M(10 ≤ M ≤ 300)이 주어진다. 두 번째 줄부터 N줄에 걸쳐 문제를 풀었을 때의 점수와 푸는데 걸리는 시간이 주어진다. *출력 설명 첫 번째 줄.. 2022. 1. 2. Algorithm - 경로 탐색(그래프 DFS) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [경로 탐색(그래프 DFS)] 방향 그래프가 주어지면 1번 노드에서 N번 노드로 가는 모든 경우의 수를 출력하는 프로그램을 작성하시오. 예를 들면, 아래 방향 그래프의 1번 노드에서 5번 노드로 가는 모든 경우의 수는 6가지이다. *입력 설명 첫 번째 줄에는 노드의 수 N(2 ≤ N ≤ 20)과 간선의 수 M이 주어진다. 그 다음부터 M줄에 걸쳐 노드 간의 연결 정보가 주어진다. *출력 설명 첫 번째 줄부터 모든 경우의 수의 경로를 출력한다. 마지막 줄에는 모든 경우의 수를 출력한다. 풀이(Python) 답안 import sys sys.stdin = open('A.. 2021. 12. 30. Algorithm - 인접 행렬(가중치 방향그래프) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [인접 행렬(가중치 방향그래프)] 아래 그림과 같은 가중치 방향그래프를 인접 행렬로 표현하는 프로그램을 작성하시오. *입력 설명 첫 번째 줄에는 노드의 수 N(2 ≤ N ≤ 20)과 간선의 수 M이 주어진다. 그 다음줄 부터 M줄에 걸쳐 연결정보와 거리비용이 주어진다. *출력 설명 가중치 방향그래프를 표현한 인접 행렬을 출력한다. 풀이(Python) 답안 import sys sys.stdin = open('AA/input_54.txt', 'rt') n, m = map(int, input().split()) g = [[0] * (n+1) for _ in range(.. 2021. 12. 30. Algorithm - 수들의 조합(DFS) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [수들의 조합(DFS)] N개의 정수가 주어지면 그 숫자들 중 K개를 뽑는 조합의 합이 임의의 정수 M의 배수가 되는 경우의 수를 출력하는 프로그램을 작성하시오. 예를 들어 5개의 숫자 2, 4, 5, 8, 12가 주어지고 3개를 뽑은 조합의 합이 6의 배수인 조합을 찾으면, {4, 8, 12}와 {2, 4, 12}로 경우의 수는 총 두 가지가 된다. *입력 설명 첫 번째 줄에 정수의 개수 N(3 ≤ N ≤ 20)과 임의의 정수 K(2 ≤ K ≤ N)가 주어진다. 두 번째 줄에 N개의 정수가 주어진다. 세 번째 줄에 M이 주어진다. *출력 설명 조건에 맞는 전체 .. 2021. 12. 29. Algorithm - 조합 구하기(DFS) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [조합 구하기(DFS)] 1부터 N까지 번호가 적힌 구슬이 있다. N개의 구슬 중 M개의 구슬을 뽑는 경우의 수를 출력하는 프로그램을 작성하시오. *입력 설명 첫 번째 줄에 자연수 N(3 ≤ N ≤ 10)과 M(2 ≤ M ≤ N)이 주어진다. *출력 설명 첫 번째 줄부터 차례대로 결과 값을 출력한다. 맨 마지막 줄에는 총 경우의 수를 출력한다. 단, 출력순서는 사전순으로 오름차순으로 출력한다. 풀이(Python) 답안 import sys sys.stdin = open('AA/input_52.txt', 'rt') def DFS(L, s): global cnt if .. 2021. 12. 28. 이전 1 ··· 3 4 5 6 7 8 9 ··· 15 다음
