profile
내가 짱이다 😎 매일 조금씩 성장하기🌱
post-thumbnail

10-5) 최대점수 구하기(냅색 알고리즘)

이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다. 각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩 니다. 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다. (해당문제

2021년 9월 8일
·
2개의 댓글
·
post-thumbnail

10-4) 동전교환(냅색 알고리즘)

다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환 해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다.입력설명첫 번째 줄에는 동전의 종류개수 N(1<=N<=12)이 주어진다. 두 번째 줄에는 N개의 동전

2021년 9월 8일
·
2개의 댓글
·
post-thumbnail

10-3) 최대 부분 증가수열

N개의 자연수로 이루어진 수열이 주어졌을 때, 그 중에서 가장 길게 증가하는(작은 수에서 큰 수로) 원소들의 집합을 찾는 프로그램을 작성하라. 예를 들어, 원소가 2, 7, 5, 8, 6, 4, 7, 12, 3 이면 가장 길게 증가하도록 원소들을 차례대로 뽑아내면 2,

2021년 9월 8일
·
2개의 댓글
·
post-thumbnail

10-2) 돌다리 건너기

철수는 학교에 가는데 개울을 만났습니다. 개울은 N개의 돌로 다리를 만들어 놓았습니다. 철수는 돌 다리를 건널 때 한 번에 한 칸 또는 두 칸씩 건너뛰면서 돌다리를 건널 수 있습니다. 철수가 개울을 건너는 방법은 몇 가지일까요?입력설명첫째 줄은 돌의 개수인 자연수 N(

2021년 9월 8일
·
2개의 댓글
·
post-thumbnail

10-1) 계단오르기

10장은 Dynamic Programming(동적계획법)에 대한 문제들이다.철수는 계단을 오를 때 한 번에 한 계단 또는 두 계단씩 올라간다. 만약 총 4계단을 오른다면 그 방법의 수는1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2 로 5가지이다.그렇다면

2021년 9월 8일
·
2개의 댓글
·