본문 바로가기
반응형

알고리즘

 (199)
[백준 알고리즘 자바] 15654 : N과 M (5) https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 문제 N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 입력 첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다. 출력 한 줄에 하나씩 문제..
[백준 알고리즘 자바] 2292 : 벌집 https://www.acmicpc.net/problem/2292 2292번: 벌집 위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌 www.acmicpc.net 문제 위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌을 때, 벌집의 중앙 1에서 N번 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나가는지(시작과 끝을 포함하여)를 계산하는 프로그램을 작성하시오. 예를 들면, 13까지는 3개, 58까지는 5개를 지난다. ..
섹션 10. dynamic programming(동적계획법) 6. 최대점수 구하기(냅색 알고리즘) 문제 이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다. 각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩니다. 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다. (해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.) 입력 첫 번째 줄에 문제의 개수N(1
섹션 10. dynamic programming(동적계획법) 5. 동전교환(냅색 알고리즘) 문제 다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다. 입력 첫 번째 줄에는 동전의 종류개수 N(1
섹션 10. dynamic programming(동적계획법) 4. 가장 높은 탑 쌓기 문제 밑면이 정사각형인 직육면체 벽돌들을 사용하여 탑을 쌓고자 한다. 탑은 벽돌을 한 개씩 아래에서 위로 쌓으면서 만들어 간다. 아래의 조건을 만족하면서 가장 높은 탑을 쌓을 수 있는 프로그램을 작성하시오. (조건1) 벽돌은 회전시킬 수 없다. 즉, 옆면을 밑면으로 사용할 수 없다. (조건2) 밑면의 넓이가 같은 벽돌은 없으며, 또한 무게가 같은 벽돌도 없다. (조건3) 벽돌들의 높이는 같을 수도 있다. (조건4) 탑을 쌓을 때 밑면이 좁은 벽돌 위에 밑면이 넓은 벽돌은 놓을 수 없다. (조건5) 무게가 무거운 벽돌을 무게가 가벼운 벽돌 위에 놓을 수 없다. 입력 입력 파일의 첫째 줄에는 입력될 벽돌의 수가 주어진다. 입력으로 주어지는 벽돌의 수는 최대 100개이다. 둘째 줄부터는 각 줄에 한 개의 벽돌..
섹션 10. dynamic programming(동적계획법) 3. 최대 부분 증가수열(LIS) 문제 N개의 자연수로 이루어진 수열이 주어졌을 때, 그 중에서 가장 길게 증가하는(작은 수에서 큰 수로) 원소들의 집합을 찾는 프로그램을 작성하라. 예를 들어, 원소가 2, 7, 5, 8, 6, 4, 7, 12, 3 이면 가장 길게 증가하도록 원소들을 차례대로 뽑아내면 2, 5, 6, 7, 12를 뽑아내어 길이가 5인 최대 부분 증가수열을 만들 수 있다. 입력 첫째 줄은 입력되는 데이터의 수 N(3≤N≤1,000, 자연수)를 의미하고, 둘째 줄은 N개의 입력데이터들이 주어진다. 출력 첫 번째 줄에 부분증가수열의 최대 길이를 출력한다. 입출력 예제 풀이방식 이번 문제는 동적 계획법(dynamic programming)에 대한 문제이다. 동적 계획법 이란 시간 복잡도가 큰 문제를 직관적으로 작게 나눈다. 이..
섹션 10. dynamic programming(동적계획법) 2. 돌다리 건너기 문제 철수는 학교에 가는데 개울을 만났습니다. 개울은 N개의 돌로 다리를 만들어 놓았습니다. 철수는 돌 다리를 건널 때 한 번에 한 칸 또는 두 칸씩 건너뛰면서 돌다리를 건널 수 있습니다. 철수가 개울을 건너는 방법은 몇 가지일까요? 입력 첫째 줄은 돌의 개수인 자연수 N(3≤N≤35)이 주어집니다. 출력 첫 번째 줄에 개울을 건너는 방법의 수를 출력합니다. 입출력 예제 풀이방식 이번 문제는 동적 계획법(dynamic programming)에 대한 문제이다. 동적 계획법 이란 시간 복잡도가 큰 문제를 직관적으로 작게 나눈다. 이렇게 나누어진 작은 문제들을 메모이제이션을 사용해서 최종적으로 본래 문제의 해결방안을 찾는 것을 말한다. 설계과정 1. 1번째, 2번째는 각각 방식이 1개와 2개 뿐이므로 그대로 ..
섹션 10. dynamic programming(동적계획법) 1. 계단오르기 문제 철수는 계단을 오를 때 한 번에 한 계단 또는 두 계단씩 올라간다. 만약 총 4계단을 오른다면 그 방법의 수는 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2 로 5가지이다. 그렇다면 총 N계단일 때 철수가 올라갈 수 있는 방법의 수는 몇 가지인가? 입력 첫째 줄은 계단의 개수인 자연수 N(3≤N≤35)이 주어집니다. 출력 첫 번째 줄에 올라가는 방법의 수를 출력합니다. 입출력 예제 풀이방식 이번 문제는 동적 계획법(dynamic programming)에 대한 문제이다. 동적 계획법 이란 시간 복잡도가 큰 문제를 직관적으로 작게 나눈다. 이렇게 나누어진 작은 문제들을 메모이제이션을 사용해서 최종적으로 본래 문제의 해결방안을 찾는 것을 말한다. 설계과정 1. 1번째, 2번째는 각각 방식이..

티스토리툴바