본문 바로가기

알고리즘90

Algorithm - 수열 추측하기(순열, 파스칼 삼각형 활용) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [수열 추측하기(순열, 파스칼 삼각형 활용)] 가장 첫 번째 줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다. 그리고 두 번째 줄부터 차례대로 파스칼의 삼각형의 원리로 위의 두 개를 더한 값이 저장되어 진행된다. 예를 들어, N이 4이고 가장 윗 줄에 3 1 2 4가 있다고 했을 때 다음과 같은 삼각형이 그려진다. N과 가장 밑에 있는 숫자가 주어져 있을 때 가장 윗줄에 있는 수열을 구하는 프로그램을 작성하시오. 단, 답이 여러 개 나오는 경우에는 사전 순으로 가장 앞에 오는 답을 출력하시오. *입력 설명 첫 번째 줄에 두 개의 정수 N(1 ≤ N ≤ 10)과 F.. 2021. 12. 28.
Algorithm - 순열 구하기(DFS) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [순열 구하기(DFS)] 1부터 N까지 번호가 적힌 구슬이 있다. 이 구슬 중 M개를 뽑아 일렬로 나열하는 방법을 모두 출력하는 프로그램을 작성하시오. (단, 구슬의 중복을 허용하지 않음) *입력 설명 첫 번째 줄에 자연수 N(3 ≤ N ≤ 10)과 M(2 ≤ M ≤ N)이 주어진다. *출력 설명 첫 번째 줄부터 결과 값을 출력한다. 마지막 줄에는 총 경우의 수를 출력한다. 단, 출력순서는 사전순서 및 오름차순으로 출력한다. 풀이(Python) 답안 import sys sys.stdin = open('AA/input_50.txt', 'rt') def DFS(L):.. 2021. 12. 21.
Algorithm - 동전 교환(DFS) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [동전 교환(DFS)] 다음과 같이 여러 단위의 동전들이 주어져 있을 때, 거스름돈을 가장 적은 수의 동전으로 교환해주는 프로그램을 작성하시오. (단, 각 단위의 동전은 무한정 사용할 수 있음) *입력 설명 첫 번째 줄에는 동전 종류의 개수 N(1 ≤ N ≤ 12)이 주어진다. 두 번째 줄에는 N개의 동전 종류가 주어진다. 세 번째 줄에는 거슬러 줄 금액 M(1 ≤ M ≤ 500)이 주어진다. *출력 설명 첫 번째 줄에 거슬러 줄 동전의 최소개수를 출력한다. 풀이(Python) 답안 import sys sys.stdin = open('AA/input_49.txt'.. 2021. 12. 21.
Algorithm - 중복순열 구하기(DFS) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [중복순열 구하기(DFS)] 1부터 N까지 번호가 적힌 구슬이 있다. 이 구슬 중에서 중복을 허락하여 M번을 뽑아 일렬로 나열하는 방법을 모두 출력하는 프로그램을 작성하시오. *입력 설명 첫 번째 줄에 자연수 N(3 ≤ N ≤ 10)과 M(2 ≤ M ≤ N)이 주어진다. *출력 설명 첫 번째 줄에 결과를 출력한다. 맨 마지막에는 총 경우의 수를 출력한다. 출력순서는 오름차순 및 사전순으로 출력한다. 풀이(Python) 답안 import sys sys.stdin = open('AA/input_48.txt', 'rt') def DFS(L): global cnt if .. 2021. 12. 19.
Algorithm - 바둑이 승차(DFS) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [바둑이 승차(DFS)] 철수는 바둑이들을 데리고 시장에 가려고 한다. 그런데 그의 트럭은 C킬로그램을 넘게 태울 수가 없다. 철수는 C킬로그램을 넘지 않으면서도 그의 바둑이들을 가장 무겁게 태우고 싶어한다. N마리의 바둑이와 각 바둑이의 무게 W가 주어지면, 철수가 트럭에 태울 수 있는 가장 무거운 무게를 구하는 프로그램을 작성하시오. *입력 설명 첫 번째 줄에 자연수 C(1 ≤ C ≤ 100,000,000)와 N(1 ≤ N ≤ 30)이 주어진다. 두 번째 줄부터 N마리의 바둑이의 무게가 주어진다. *출력 설명 첫 번째 줄에 가장 무거운 무게를 출력한다. 풀이(.. 2021. 12. 17.
Algorithm - 합이 같은 부분집합(DFS) 알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다. 문제 [합이 같은 부분집합(DFS)] N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나눈다. 이 때, 두 부분집합의 원소를 모두 더한 값이 서로 같으면 "YES"를 출력하고 그렇지 않으면 "NO"를 출력하는 프로그램을 작성하시오. 참고로, 둘로 나뉘는 두 부분집합은 서로소 집합이며 두 부분집합을 합하면 입력으로 주어지는 원래의 집합이 되어야 한다. 예를 들면, {1, 3, 5, 6, 7, 10}의 집합이 입력되면 {1, 3, 5, 7} = {6, 10}으로 두 부분집합의 합이 모두 16인 경우가 존재한다. *입력 설명 첫 번째 줄에 자연.. 2021. 12. 16.

티스토리툴바