알고리즘90 Algorithm - 위상정렬(그래프 정렬) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [위상정렬(그래프 정렬)] 위상정렬은 어떤 일을 하는 순서를 찾는 알고리즘이다. 각각의 일의 선후관계가 복잡하게 얽혀있을 때, 각각 일의 선후관계를 유지하면서 전체 일의 순서를 짜는 알고리즘이다. 만약, 아래와 같은 일의 순서를 지키면서 전체 일의 순서를 정한다면 전체 일의 순서는 1, 6, 2, 5, 4, 3과 같이 정할 수 있다. 전체 일의 순서는 여러 가지가 있으며 위의 예시는 그 중 하나이다. *입력 설명 첫 번째 줄에 전체 일의 개수 N과 일의 순서 정보의 개수 M이 주어진다. 두 번째 줄부터 M개의 정보가 주어진다. *출력 설명 전체 일의 순서를 출력한.. 2022. 2. 13. Algorithm - 회장뽑기(플로이드-와샬 응용) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [회장뽑기(플로이드-와샬 응용)] 월드컵축구의 응원을 위한 모임에서 회장을 선출하려고 한다. 이 모임은 만들어진지 얼마 되지 않았기 때문에 회원사이에 서로 모르는 사람도 있지만, 몇 사람을 통하면 서로 모두 알 수 있다. 각 회원은 다른 회원들과 가까운 정도에 따라 점수를 받게된다. 예를 들어, 어느 회원이 다른 모든 회원과 친구이면, 이 회원의 점수는 1점이다. 어느 회원의 점수가 2점이면, 다른 모든 회원이 친구이거나, 친구의 친구임을 말한다. 또한, 어느 회원의 점수가 3점이면, 다른 모든 회원이 친구이거나, 친구의 친구이거나, 친구의 친구의 친구임을 말한다.. 2022. 2. 12. Algorithm - 그래프 최단거리(플로이드-와샬) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [그래프 최단거리(플로이드-와샬 : 냅색 알고리즘)] N개의 도시가 주어지고, 각 도시들을 연결하는 도로와 해당 도로를 통행하는 비용이 주어질 때 모든 도시에서 모든 도시로 이동하는데 드는 비용의 최소값을 구하는 프로그램을 작성하시오. *입력 설명 첫 번째 줄에는 도시의 수 N(1 ≤ N ≤ 100)과 도로 수 M(1 ≤ M ≤ 200)이 주어진다. 그 다음 줄부터 M줄에 걸쳐 도로정보와 비용(20 이하의 자연수)이 주어진다. 만약, 1번 도시와 2번 도시가 연결되고 그 비용이 13이면 "1, 2, 13"으로 정보가 주어진다. *출력 설명 모든 도시에서 모든 도시.. 2022. 2. 6. Algorithm - 최대점수 구하기(냅색 알고리즘) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [최대점수 구하기(냅색 알고리즘)] 이번 올림피아드대회에서 좋은 성적을 내기 위해서 현수는 선생님이 주신 N개의 문제를 풀고자 한다. 각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어진다. 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야한다. 단, 해당 문제는 주어진 시간이 지나면 풀리는 것으로 간주하며 동일 유형의 문제는 중복해서 풀 수 없다. 위의 조건을 모두 충족시키며 최대점수를 출력하는 프로그램을 작성하시오. *입력 설명 첫 번째줄에 문제의 개수 N(1 ≤ N ≤ 100)과 제한 시간 M(10 ≤ M ≤ 1000)이 주어진.. 2022. 2. 6. Algorithm - 동전교환(냅색 알고리즘) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [동전교환(냅색 알고리즘)] 여러 단위의 동전들이 주어져 있을 때, 거스름돈을 가장 적은 수의 동전으로 교환해주는 프로그램을 작성하시오. 단, 각 단위의 동전은 무한정 사용할 수 있다. *입력 설명 첫 번째 줄에 동전의 종류 개수인 N(1 ≤ N ≤ 12)이 주어진다. 두 번째 줄에는 N개의 동전 종류가 주어진다. 세 번째 줄에는 거슬러 줄 금액 M(1 ≤ M ≤ 500)이 주어진다. 단, 각 동전의 종류는 100원을 넘지 않는다. *출력 설명 첫 번째 줄에 거슬러 줄 동전의 최소개수를 출력한다. 풀이(Python) 답안 import sys sys.stdin = .. 2022. 2. 5. Algorithm - 가방문제(냅색 알고리즘) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [가방문제(냅색 알고리즘)] 최고 17kg의 무게를 저장할 수 있는 가방이 있다. 그리고 3kg, 4kg, 7kg, 8kg, 9kg의 무게를 가진 5종류의 보석이 있다. 이 보석들의 가치는 각각 4, 5, 10, 11, 13이다. 이 보석을 가방에 담는데 17kg를 넘지 않으면서 최대의 가치가 되도록 만드는 프로그램을 작성하시오. 단, 각 종류별 보석의 개수는 무한정 존재하며 한 종류의 보석을 여러 번 가방에 담을 수 있다. *입력 설명 첫 번째 줄에 보석 종류의 개수와 가방에 담을 수 있는 무게의 한계값이 주어진다. 두 번째 줄부터 각 보석의 무게와 가치가 주어.. 2022. 2. 5. 이전 1 2 3 4 ··· 15 다음
