맨위에서 출발해서 아래로 내려가는데 한 루트의 합이 가장 큰 값을 출력
위 문제를 해결하기 위한 대표적인 알고리즘 세가지를 고려해 볼수 있다.
1.
모든 경우의 수를 다 해볼것인가? 브루트포스(DFS,BFS)
2.
최적의 해를 항상 그시기에 찾는다. 그리디 알고리즘
과거 선택에대한 고려가 전혀 없고 미래를 선택하는 부분도 전혀 고려를 하지 않고 현재기준으로 최적의 값만 선택한다.
3.
DP 이전단계에서 구했던 최적의 값과, 현재상황에서 구한 값을 비교하여 더 최적의 값을 찾는 알고리즘이다.
또 다른 예로 앞서 풀어봤던 문제중에 거스름돈 문제가 있다.
1260원을 만드는 경우 이것 또한 그리디 알고리즘의 하나로 볼수 있다.
3,4,5원의 동전을 가지고 15원을 만들어본다고 가정해보자.
int n = 15; //거스름돈
int change[4] = { 3, 4, 5 }; //거스름돈 종류
int count[4] = {}; //거스름돈 개수
for (int i = 0; i < 4; i++)
{
count[i] += n / change[i];
n %= change[i];
}
return 0;
Python
복사
위문제를 DP로 풀어보자
전형적이고 대표적인 기본 DP 문제이다. dp 테이블을 만들어서 문제를 해결하면 된다.
만들어야할 테이블의 크기를 정해준다. 금액보다 +1 한개 크게 만들어주면 된다.
3원의 동전만 가지고 15원의 거스름돈을 거슬러 줄수 있는 경우의수 테이블을 만들어보자
이번에는 3,4원의 동전을 가지고 만들수 잇는 경우의 수를 생각해보자
거스름돈이 4원이 만들어질때까지는 3원까지의 조합과 동일하다.
4원부터는 달라진다.
5원의 경우에는 3,4원으로 만들수 있는 경우의수가 없다.
그렇다면 3,4원으로 5원을 거슬러 줄 경우에는 4원을 내주고 1원을 거슬러줄 조합이 있을까 볼수있다.
노란색이 현재 동전을 추가하기전 해당 돈을 거슬러 줄 수 있는 경우의 수이고 초록색이 가지고있는 가장 큰 동전을 하나 먼저 거슬러주고 남은 돈을 거슬러 줄 수 있는지에 대한 정보다. 0+0은 0이기 때문에 (3, 4) 조합으론 5원을 거슬러줄 수 없다
6원의 경우 (현재 동전이 추가되기전 거슬러줄 수 있는 경우의수 1) + (4원 거슬러주고 남은 2 원 거슬러줄 수 있는 경우의수 0) = 1이 된다.
7원의 경우 (현재 동전이 추가되기전 거슬러줄 수 있는 경우의수 0) + (4원 거슬러주고 남은 3 원 거슬러줄 수 있는 경우의수 1) = 1이 된다.
결과적으로 이것들은 패턴이 보이기 시작한다.
7원의 경우 (현재 동전이 추가되기전 거슬러줄 수 있는 경우의수 0) + (4원 거슬러주고 남은 3 원 거슬러줄 수 있는 경우의수 1) = 1이 된다.
dp[index] += dp[index - 현재 동전]
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
int main()
{
// 동전 집합과 목표 금액
vector<int> coins = {3,4,5};
int amount = 15;
// DP 테이블 초기화
vector<int> dp(amount + 1, 0);
dp[0] = 1;
for (int coin : coins)
{
for (int i = coin; i <= amount; i++)
{
dp[i] += dp[i - coin];
}
}
// 결과 출력
if (dp[amount] == 0)
{
cout << "해당 금액을 만들 수 없습니다." << endl;
}
else
{
cout << amount << "원을 만들기 위한 최소 동전 개수: " << dp[amount] << endl;
}
return 0;
}
Python
복사
연습문제
문제 1번
링크드리스트 복습입니다.
Memory Pool 을 사용하여 위와 같이 링크드리스트를 만들어 보세요.
아래 코드를 완벽히 이해한 후, 소스코드를 베끼지 않고, 직접 코딩해서 이 문제를 풀어보세요!
[출력]
For문으로 A ~ E 까지 출력해주세요.
struct Node
{
char ch;
Node* next;
};
Node buf[100];
int bufCnt;
Node* head;
Node* myAlloc(int ch, Node * next)
{
buf[bufCnt].ch = ch;
buf[bufCnt].next = next;
return &buf[bufCnt++];
}
void addNode(char ch, Node * next)
{
head = myAlloc(ch, head);
}
int main()
{
return 0;
}
Python
복사
출력 결과
A B C D E
문제 2번
입력 받은 글자를 링크드리스크에 저장하고 출력 해주세요.
글자들을 역순으로 링크드리스트에 저장하고 for문을 돌려 두 칸씩 뛰어넘으면서 출력하세요.
[예시]
입력 받은 C O D I N G 를 역순으로 저장하면 아래처럼 링크드리스트를 구성이 됩니다.
이제 맨 앞부터 밟을 수 있는 징검다리인 돌 들을 두 칸씩 뛰어넘으면서 출력하면 됩니다.
이때 출력결과는 GIONM 입니다.
[입력]
총 9글자를 입력 받으세요.
[출력]
입력 받은 글자를 링크드리스트에 한 글자씩 역순으로 저장하고, 맨 앞부터 두 칸씩 건너뛰어 출력하세요.
입력 예제
C O D I N G
출력 결과
GIO
문제 3번
음계를 입력 받고 링크드리스트에 저장 후, 출력 해주세요.
Memory Pool 이용하여 링크드리스트를 만들고, 음계 정보를 순차적으로 저장 하세요.
그리고 링크드리스트를 그대로 출력 해주세요.
•
정방향으로 링크드리스트가 만들어 진다는 것을 유의하세요.
[입력]
음계의 개수 N을 입력 받으세요.
그 다음 줄의 각 음계의 값을 입력 받으세요.
[출력]
저장된 링크드리스트를 출력 해주세요.
입력 예제
6
5 3 4 1 2 7
출력 결과
5 3 4 1 2 7
문제 4번
8 마리의 공룡 화석이 발견되었고, 이름과 나이는 아래와 같습니다.
공룡들의 나이들을 DB에 저장하고 공룡들을 찾을 수 있는 시스템을 만드려고 합니다.
DB 사용자들이 공룡의 나이를 입력하면 DB에서 해당 나이에 맞는 공룡의 이름을 검색 합니다.
•
공룡들 나이 중 같은 나이는 없습니다.
[입력]
공룡의 나이를 입력 받습니다.
[출력]
나이에 해당하는 공룡의 이름을 출력합니다.
[힌트1]
공룡들의 나이가 1억이 넘기에 배열에 바로 담을 수 없습니다.
Hash Function을 써서 bucket에 값을 담고, 바로 찾으면 됩니다.
[힌트2]
입력 예제
1000000005
출력 결과
Sour
문제 5번
ID/PASSWORD를 입력받으면 암호화를 해서 Server에 전송하곤합니다.
Hash 함수를 이용하여 입력받은 ID를 암호화 후 출력 해 주세요.
•
HashFunction : hornor's method 이용
계산은 아스키코드 번호를 그대로 사용하면됩니다.
[예시]
A : 65
B : 66
C : 67
...
[입력]
대문자로 문자를 입력 받으세요.
[출력]
암호화 결과 값을 출력하세요.
입력 예제
JASON
출력 결과
35016904
문제 6번
공룡의 화석 8개가 발견되었습니다.
이 화석으로 공룡의 나이 조사 결과, 대부분 10억살 이상이었고 정확한 나이는 다음과 같습니다.
숫자를 입력 받고, 이 숫자와 같은 나이를 가진 공룡이 총 몇마리인지 출력 해주세요.
[힌트1]
숫자가 너무 커서 이 값을 배열의 index로 쓸 수 없기 때문에 Hash Function이 필요합니다.
그런데 Hash Function을 거치면 다른 값들이 같은 index에 들어갈 수 있기 때문에, Chaining이 필요합니다.
[힌트2]
HashTable(Bucket)에 담고, 내가 찾는 target값이 몇 개인지만 세면 됩니다.
[입력]
찾을 숫자를 입력 받으세요.
[출력]
몇마리가 해당 나이와 같은지 마리수를 출력 해주세요.
입력 예제
1000000005
출력 결과
2마리
문제 7번
A ~ E 그룹사에서 신입사원들이 모였습니다.
그룹사별 신입사원들의 정보를 Memory Pool + Chaining 을 사용하여 저장해주세요.
그룹사의 이름을 입력 받고 해당 그룹사의 신입사원 ID 들을 모두 출력 해주세요.
•
Hash Function 은 사용하지 않아도 됩니다.
[입력]
출력할 그룹사의 이름을 입력하세요.
[출력]
해당 그룹사의 출력할 ID 는 위 배열의 왼쪽부터 오른쪽 순서대로 출력 해주세요.
입력 예제
A
출력 결과
21 15 3
문제 8번
첩보원 코드 번호를 입력하면, 몇 명을 암살했는지 출력해주는 프로그램을 만들어야합니다.
한글자로 된 첩보원 코드번호와 그들이 암살에 성공한 적들의 수가 아래 처럼 저장되어 있습니다.
첩보원이 적에게 당하지 않도록, Hash를 써서 빠르고 정확한 프로그램을 만들어주어야 합니다.
B를 입력하면 10이 출력되고, Z가 입력되면 16이 출력되는 프로그램을 작성 해 주세요.
[입력]
첩보코드를 입력 하세요.
[출력]
첩보원의 암살 성공횟수를 출력하세요.
[힌트1]
struct Node { char code; int killCount; Node *next; }
C++
입력 예제
B
출력 결과
10
문제 1번
화장실이 하나이기 때문에 화장실을 사용하려면 대기를 해야합니다.
기다리는 사람들이 모두 화장실을 사용한다고 할때, 총 대기시간이 적은 사용 순서를 정해주세요.
예를들어 총 네 명, A ~ D 사람이 화장실을 사용하는 시간이 다음과 같습니다.
한 사람이 화장실을 이용할 때 다른 사람들은 그 사람이 나오길 기다립니다.
사람들의 전체 대기시간이 최소가 되도록 사용순서를 정하고, 최소 대기시간을 출력해주세요.
[입력]
네 사람의 대기 시간을 입력 하세요.
[출력]
화장실을 모든 사람들이 사용완료 했을때 모든 사람이 대기해야하는 총 대기시간 들중, 최소 대기 시간을 출력하세요.
[예시]
정답은 아니지만, A -> B -> C -> D 순서로 화장실에 들어간다고 할 경우
네 사람의 총 대기시간은 155분입니다.
처음 A가 화장실 사용시 : 15 X 3
이후, B가 화장실 사용시 : 30 X 2
이후, C가 화장실 사용시 : 50
마지막으로, D가 화장실을 사용하면 네 명의 각각 대기시간을 합치면 155 입니다.
만약 D > A > B > C 순서대로 화장실을 이용한다면, 총 대기시간은 90분으로 최소 대기시간이 됩니다.
입력 예제
15 30 50 10
출력 결과
90
문제 2번
10원, 50원, 100원, 500원 이렇게 네 종류의 동전이 있습니다.
교환할 동전 금액을 입력받고, 최소의 동전 숫자로 거슬러주려 합니다.
이 문제를 Greedy로 풀어주세요.
만약에 660원을 입력 받았다면,
500원 짜리 1개
100원 짜리 1개
50원 짜리 1개
10원짜리 1개
거슬러 줄 수 있는 최소 동전의 수는 4개 입니다.
[HINT]
10, 50, 100, 500 인 경우는 동전이 서로 배수이기 때문에 Greedy가 성립 됨.
만약 10, 70, 100 인 것처럼 동전이 서로 배수가 아닌 경우 Greedy가 성립 안됨.
입력 예제
660
출력 결과
4
문제 3번
회의실이 하나인 회사가 있습니다.
예약스케쥴을 입력받고, 최대 몇번의 회의가 가능한지 출력하세요
만약 6번의 회의가 있고, 아래와 같이 스케쥴을 입력받았다면
•
-> 최대 3번의 회의가 가능합니다.
첫번째 입력숫자는 회의의 횟수입니다.
그 다음 입력 숫자들은 스케쥴 시작시간과 종료시간 입니다.
가능한 최대 회의 횟수를 출력하세요
[힌트]
가장 일찍 끝나는 회의 먼저 선택하기
입력 예제
6
1 6
3 8
8 9
2 4
4 6
7 9
출력 결과
3
문제 4번
막대 블럭들을 넣을 수 있는 100 cm 크기의 길다란 홈이 있습니다.
n개의 막대 블럭이 있을때 일부 막대블럭을 선택하여
최대 몇개를 넣을 수 있을지 출력하세요
예로 들어,
20cm, 57cm, 13cm, 40cm, 33cm, 8cm 막대 블럭이 있을때 최대 4개를 넣을 수 있습니다.
[세부 조건]
최대 입력값은 1 <= n <= 10 입니다.
입력 예제
6
20 57 13 40 33 8
출력 결과
4
문제 5번
지게차는 4 x 4 맵에서 (0, 0) 에 있습니다.
그리고 도착지점(3, 3)까지 최단거리로 이동하려고 합니다.
바닥상태가 좋지 않아 땅을 밟을 때 마다, 지게차는 써있는 숫자만큼 손상 되곤 합니다.
최단거리로 도착지점까지 가려고 할 때, 최소 데미지를 받는 경로를 출력 해 주세요.
만약 아래와 같이 MAP을 입력받는다면
출력결과는 다음과 같습니다.
0,0
1,0
1,1
1,2
1,3
2,3
3,3
[세부 조건]
1.
맵 사이즈는 4 x 4로 고정입니다.
2.
시작지점(0, 0)과 도착지점(3, 3)의 값은 항상 0 입니다.
입력 예제
0 3 5 1
1 1 1 5
1 50 20 10
1 50 5 0
출력 결과
0,0
1,0
1,1
1,2
1,3
2,3
3,3
문제 6번
1x2 사이즈의 나무토막이 있습니다.
3단까지 나무를 쌓는 방법은 아래와 같이 총 세가지 입니다.
4단까지 나무를 쌓는 방법은 총 다섯가지 입니다.
n단까지 나무를 쌓으려고 할때 가능한 방법수를 출력해주세요.
(Dynamic Programming 문제 입니다.)
[HINT]
[1]단
•
> [0]단에서 가로 1개 쌓기
•
> 경우의 수 : 1
[2]단
•
> [1]단에서 1개 더 올리기
+ [0]단에서 세로로 쌓기
•
> 경우의 수 : 2
[3]단
•
> [2]단에서 1개 더 올리기
•
> [1]단에서 세로로 쌓기
•
> 경우의수 : 3
[4]단
•
> [3]단에서 1개 더 올리기
•
> [2]단에서 세로로 쌓기
•
> 경우의수 : 5
[5]단
•
> [4]단에서 1개 더 올리기
•
> [3]단에서 세로로 쌓기
•
> 경우의 수 : 8
입력 예제
4
출력 결과
5
문제 7번
7x3 맵을 입력 받으세요.
(0,0) 좌표에 있는 개구리는 ↓로 한 칸 점프 할 수 있습니다. (벽으로 이동 불가)
↓로 한 칸 점프 할 수 있습니다. (벽으로 이동 불가)숫자가 써있는 곳을 밟으면, 그 숫자만큼 점수를 얻습니다.
개구리가 맨 밑까지 내려올, 때 개구리가 받을 수 있는 최대 점수는 몇일까요?
(숫자 0은 벽 입니다. DP로 풀어주세요.)
입력 예제
1 0 0
1 2 2
0 3 0
3 -10 -5
15 -10 50
15 -10 10
0 6 4
출력 결과
67
문제 8번
총 12칸으로 된 맵이 있습니다. ( 0번 index값은 항상 0 입니다. )
블루마을에 사는 부르스 윌리스는 0번에서 시작해서,
(2칸) 또는 (3칸) 또는 (현재 index * 2칸) 으로 점프 할 수 있습니다.
12번 index 이상 지역에 도착 할 때 얻을 수 있는 최대점수를 출력 하세요.
입력 예제
0 2 4 -5 -7 6 20 7 -10 -8 4 -1
출력 결과
21
문제 9번
두문장을 입력받으세요.(최대15글자)
그리고 가장 긴 같은 단어를 찾아주세요.
•
매우 어렵습니다*
입력 예제
ABABCGKABABC
BTBCKABABCT
출력 결과
KABABC
