본문 바로가기

알고리즘 문제풀이 입문: 코딩테스트 대비/섹션 8. DFS, BFS 활용14

순열 추측하기 설명가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다. 그리고 둘째 줄부터 차례대로 파스칼의 삼각형처럼 위의 두개를 더한 값이 저장되게 된다.예를 들어 N이 4 이고 가장 윗 줄에 3 1 2 4 가 있다고 했을 때, 다음과 같은 삼각형이 그려진다.N과 가장 밑에 있는 숫자가 주어져 있을 때 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성하시오.단, 답이 여러가지가 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력하여야 한다. 입력첫째 줄에 두개의 정수 N(1≤N≤10)과 F가 주어진다.N은 가장 윗줄에 있는 숫자의 개수를 의미하며 F는 가장 밑에 줄에 있는 수로 1,000,000 이하이다. 출력첫째 줄에 삼각형에서 가장 위에 들어갈 N개의 숫자를 빈 칸을 사이에 두고 출력한다.답이 존재하지 않는.. 2024. 5. 15.
조합수 (메모이제이션) 설명로 계산합니다.하지만 여러분은 이 공식을 쓰지않고 다음 공식을 사용하여 재귀를 이용해 조합수를 구해주는 프로그램을 작성하세요. 입력첫째 줄에 자연수 n(3 출력첫째 줄에 조합수를 출력합니다. 예시 입력 1 5 3 예시 출력 110 예시 입력 2 33 19 예시 출력 2818809200  문제 해결 조합을 계산하는 문제이다.조합에서 C(n,r)=1인 경우는n==r 또는 r==0인 경우이고, 그 외의 경우에는 조합의  C(n−1,r−1)과 C(n−1,r)의 합을 반환해 재귀를 이용하며 ㅣ용해주면 된다.   최종 코드 import java.util.Scanner;public class P07_조합수_메모이제이션 { static int n, r; public static void main(Stri.. 2024. 5. 11.
순열 구하기 설명10이하의 N개의 자연수가 주어지면 이 중 M개를 뽑아 일렬로 나열하는 방법을 모두 출력합니다. 입력첫 번째 줄에 자연수 N(3두 번째 줄에 N개의 자연수가 오름차순으로 주어집니다. 출력첫 번째 줄에 결과를 출력합니다.출력 순서는 사전순으로 오름차순으로 출력합니다. 예시 입력 1 3 23 6 9 예시 출력 13 63 96 36 99 39 6  문제 해결 static int N, M;static int[] arr;static int[] selected;static boolean[] visited;static String result = "";숫자의 개수 N, 순열을 만들 때 선택할 숫자의 수 M입력으로 주어지는 자연수를 저장하는 arr 배열선택된 숫자를 저장하는 데 사용하는 selected 배열해당 숫.. 2024. 5. 11.
동전교환 설명다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 되는가?각 단위의 동전은 무한정 쓸 수 있다. 입력첫 번째 줄에는 동전의 종류개수 N(1그 다음줄에 거슬러 줄 금액 M(1 출력첫 번째 줄에 거슬러 줄 동전의 최소개수를 출력한다. 예시 입력 1 31 2 515 예시 출력 13 힌트출력 설명 : 5 5 5 동전 3개로 거슬러 줄 수 있다.  문제 해결 이 문제는 동전의 종류와 각각의 동전을 무한히 사용할 수 있을 때, 주어진 금액을 만들기 위해 필요한 최소 동전 수를 계산하는 문제이다. static int N, M;static int[] money;static int[] minCoins; // M원을 만드는 데 필요한 최소 동전 수 배열stat.. 2024. 5. 11.
중복순열 구하기 설명1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 중복을 허락해 M번을 뽑아 일렬로 나열하는 방법을 모두 출력합니다. 입력첫 번째 줄에 자연수 N(3 출력첫 번째 줄에 결과를 출력합니다.출력순서는 사전순으로 오름차순으로 출력합니다. 예시 입력 1 3 2 예시 출력 11 11 21 32 12 22 33 13 2 3 3 문제 해결 이 문제는 N과 M에 대해 중복 순열을 만들어 출력하는 문제이다. 중복 순열은 각 요소가 한 번 이상 선택될 수 있는 순열을 을 말한다. 예를 들어 N이 3이고 M이 2라면, (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)와 같이 각 번호가 여러 번 선택될 수 있는 것이다. static int N,.. 2024. 5. 11.
최대점수 구하기(DFS) 설명 이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다.각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩니다.제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다.(해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.)입력첫 번째 줄에 문제의 개수N(1두 번째 줄부터 N줄에 걸쳐 문제를 풀었을 때의 점수와 푸는데 걸리는 시간이 주어집니다. 출력첫 번째 줄에 제한 시간안에 얻을 수 있는 최대 점수를 출력합니다. 예시 입력 1 5 2010 525 1215 86 37 4 예시 출력 141 문제 해결 제한된 시간 내에 가능한 최대 점수를 얻기 위해 주어진 문제들 중에서 선택하는 방법이기.. 2024. 5. 11.
반응형

티스토리툴바