정의

• 어떤 것을 결정해야 하는 순간, 가장 좋다고 생각하는 것을 선택하면서 답 찾는 알고리즘

Dynamic Programming과 비교

• DP : 어떤 상황에서 할수 있는 상황 모두 살펴보고 거기서 가장 좋은것 선택

• Greedy : 할수 있는 선택 중에 제일 좋다고 생각되는 것 하나 선택해서 정답 찾아감

단점

• 그 때 그 때는 최적일 수 있지만, 최종적으로는 최적이 아니 수도

1
2
3
4
5
6
7
8
9
10
11

ex)  12원을 1, 4, 5원으로 거슬러 줄 때, 

5원 2개, 1원 2개 --> 총 4개가 필요

but, 정답은 4원 3개!!!

DP로 풀어야해.

D[n] = n원을 거슬러 주는 동전의 최소 개수

min(D[n-1], D[n-4], D[n-5]) + 1 

그럼 언제 쓰나

• 지금 이 순간 가장 좋은 경우 선택하는 것이 최적일 때.

• 왜 그게 최적인지 증명해야함

• 그래서 가장 어려워

• 그래서 시험이나 대회에 나오면 가장 나중에 풀어

예제

문제

자연수 N이 주어지면,
N의 각 자릿수의 합을 구해서 return 하는 solution 함수를 만들어 주세요.

예를들어 N = 123이면 1 + 2 + 3 = 6을 return 하면 됩니다.

제한사항

* N의 범위 : 100,000,000 이하의 자연수 <br>

<입출력 예>

N — answer

123 — 6

987 — 24

입출력 예 설명


입출력 예 #1

문제의 예시와 같습니다.

입출력 예 #2

9 + 8 + 7 = 24이므로 24를 return 하면 됩니다.

풀이

1. 정수형으로 입력 받음

2. 입력 받음 정수형을 문자열형으로 변환 ( 자릿수 구하기 용이하기 때문 )

3. chatAt(i) 번째 - ‘ 0 ‘ 을 하면 그 자릿수가 나옴

4. 각각 더하면 결과값 나옴

개념

1. 987이 입력되면

2. ‘9’ - ‘0’ = 57 - 48 = 9

https://www.acmicpc.net/problem/1260

풀이

• 어레이리스트 생성
  • ArrayList[] a = (ArrayList[]) new ArrayList[n+1];
• DFS
  • dfs(x) : x를 방문
  • 한 정점에 연결된 정점들 중에
    • 방문하지 않았으면 방문
• BFS
  • 아직 방문 하지 않았고 현 위치에서 갈 수 있는 정점들을 모두 큐에 넣어
  • 큐에 넣을 때 방문했다고 체크

결과

https://www.acmicpc.net/problem/10845

DFS 풀이

1. head, tail 을 둔다

2. push
   • head는 초기 추가된 노드를 계속 가르킴
   • tail이 가르키느 노드는, 새로 추가된 노드를 가르킴
   • tail은, 새로 추가된 노드를 가르킴
3. pop
   • head가 가르키는 노드가 가르키는 노드를 head가 가르킴

https://programmers.co.kr/learn/challenge_codes/144

풀이

1. 소문자이면

   • 현재 문자에서 ‘a’ 기준으로 얼만큼 떨어져 있는지 + n
   • 알파뱃 수 만큼 %
   • • a

2. 대문자이면

   • 소문자와 같은 방식

3. 공백

   • pass