본문 바로가기

전체 글219

Algorithm - 동전 바꿔주기(DFS) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [동전 바꿔주기(DFS)] 명보네 동네 가게의 현금 출납기에는 k가지의 동전이 각각 n(1), n(2), ... , n(k)개씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔주려고 한다. 이 때, 동전 교환방법은 여러가지가 있을 수 있다. 예를 들어, 10원 짜리, 5원 짜리, 1원 짜리 동전이 각각 2개, 3개, 5개씩 있으면 20원 짜리 지폐를 다음과 같이 4가지 방법으로 교환할 수 있다. 입력으로 지폐의 금액(T), 동전의 가지수(k), 각 동전 하나의 금액(p)와 개수(n)이 주어질 때, 지폐를 동전으로 교환하는 방법의 수를 출력하는 프로그램.. 2022. 1. 3.
Algorithm - 양팔저울(DFS) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [양팔저울(DFS)] 무게가 서로 다른 K개의 추와 빈 그릇이 있다. 모든 추의 무게는 정수이고, 그릇의 무게는 0이다. 양팔저울을 한 번만 이용하여 원하는 물의 무게를 그릇에 담고자 한다. 주어진 모든 추 무게의 합을 S라 하자. 예를 들어, 추가 3개이고 각 추의 무게가 {1, 2, 6}이면 S=9이고 양팔저울을 한 번만 이용하여 1부터 S사이에 대응되는 모든 무게의 물을 다음과 같이 그릇에 담을 수 있다. 참고로, X는 그릇에 담는 물의 무게이고 □는 그릇을 나타낸다. 만약, 추의 무게가 {1, 5, 7}이면 S=13이고 그릇에 담을 수 있는 물의 무게는 {.. 2022. 1. 3.
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.

티스토리툴바