백준 1991 : 트리 순회

문제

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

예를 들어 위와 같은 이진 트리가 입력되면,

• 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
• 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
• 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

가 된다.

입력

출력

예제 입력 1 

7
A B C
B D .
C E F
E . .
F . G
D . .
G . .

ABDCEFG
DBAECFG
DBEGFCA

풀이

백준 11052 : 붕어빵 판매하기

문제

강남역에서 붕어빵 장사를 하고 있는 해빈이는 지금 붕어빵이 N개 남았다.

해빈이는 적절히 붕어빵 세트 메뉴를 구성해서 붕어빵을 팔아서 얻을 수 있는 수익을 최대로 만드려고 한다. 붕어빵 세트 메뉴는 붕어빵을 묶어서 파는 것을 의미하고, 세트 메뉴의 가격은 이미 정해져 있다.

붕어빵 i개로 이루어진 세트 메뉴의 가격은 Pi 원이다.

붕어빵이 4개 남아 있고, 1개 팔 때의 가격이 1, 2개는 5, 3개는 6, 4개는 7인 경우에 해빈이가 얻을 수 있는 최대 수익은 10원이다. 2개, 2개로 붕어빵을 팔면 되기 때문이다.

1개 팔 때의 가격이 5, 2개는 2, 3개는 8, 4개는 10 인 경우에는 20이 된다. 1개, 1개, 1개, 1개로 붕어빵을 팔면 되기 때문이다.

마지막으로, 1개 팔 때의 가격이 3, 2개는 5, 3개는 15, 4개는 16인 경우에는 정답은 18이다. 붕어빵을 3개, 1개로 팔면 되기 때문이다.

세트 메뉴의 가격이 주어졌을 때, 해빈이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 해빈이가 가지고 있는 붕어빵의 개수 N이 주어진다. (1 ≤ N ≤ 1,000)

둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)

출력

해빈이가 얻을 수 있는 최대 출력

4
1 5 6 7

10

풀이

bottom-up 방식

cost[i] 에 기존 계산했던 값들을 저장해 놓고 cost[i] 와 비교 -> 메모제이션?

CodeUp 1411 : 빠진 카드

풀이

1부터 N까지의 카드가 순서대로 있고 이를 찾았으면 TRUE(1), 아니면 찾지 못한 것으로 놓고

for 문으로 찾은 카드들을 입력받고 다시 for문으로 전체 카드들을 찾았는지 검사했다.

더 좋은 방법 => N을 입력할 때 1~N까지의 값들을 모두 더하고, 찾은 카드 입력받을 때 마다 빼주면 맨 마지막 남는 값이 정답이다.

Baekjoon 9372 : (BFS) 상근이의 여행

입력

첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고,

각 테스트 케이스마다 다음과 같은 정보가 주어진다.

• 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 주어진다.
• 이후 M개의 줄에 a와 b 쌍들이 입력된다. (a와 b를 왕복하는 비행기가 있다는 것을 의미한다)
• 주어지는 비행 스케줄은 항상 연결 그래프(Connected Graph)를 이룬다.

(1<=n<=200)

출력

테스트 케이스마다 한 줄을 출력한다.

• 상근이가 모든 도시를 여행하기 위해 타야 하는 비행기 종류의 최소 개수를 출력한다.

Baekjoon 11057 : (DP) 오르막 수

DP(Dynamic Programming) 란??

CodeUp 1901 : (재귀 함수) 1부터 n까지 출력하기

문제

1 부터 정수 n 까지 출력하는 재귀함수를 설계하시오.

n$n$까지 출력하는 재귀함수를 설계하시오.

이 문제는 반복문 for, while 등을 이용하여 풀수 없습니다.

입력

정수 n이 입력된다(1<=n<=200)

출력

1부터 n까지 한 줄에 하나씩 출력한다.

재귀함수란??