Day 9: 백준 [8단계] 기본 수학 1 - 설탕 배달

[결과]

으음... 하하...

 

[코드]

규칙이 있을거라 생각하고 무작정 돌려봤음 >> 땡~~~ 예외가 너무 많음.

1, 2, 4, 7 등이 나왔을 때 -1을 출력하게 하려고 하다, break가 걸렸을 때에도 출력하게 됨

대충 처리하려고 했으나 7 같은 숫자를 처리하지 못함을 발견

이렇게 하기 싫었는데 결국 flag 둠... flag를 두는 건 좋은 습관일까.....

[과정]

1. 규칙이 있을거라 생각하여 무작정 구현하기로 결심

>> 예외가 많았다고 생각. 다 잡을 수 없을거라 생각하여 내가 좋아하는 무작정.. 구현

2. q가 0 미만일 때 -1을 출력

3. 플래그 뒀음..

 

[공부]

1. 문제의 알고리즘 분류 => 다이나믹 프로그래밍, 그리디 알고리즘

 

다이나믹 프로그래밍이란?

큰 문제를 작은 문제로 나누어푸는 문제를 일컫는 말

분할정복과의 차이점은 큰 문제를 작은 문제로 나누어 푸는 방법이지만 작은 문제에서 반복이 일어나지 않음.

다이나믹 프로그래밍(=동적 프로그래밍)은 작은 부분 문제들이 반복되는 것!

메모이제이션(컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술 ref: 위키백과)을 활용함!

ex) '피보나치수열' 에서 반복되는 계산을 메모이제이션 활용하여 계산을 줄임과 동시에 속도차원에서도 좋음!

방식에는 Bottom-up과 Top-down이 있다.

Bottom-up의 장점: 풀기가 쉬움 (작은 문제부터 차근차근 해결)

Top-down의 장점: 가독성이 좋음 (큰 문제를 풀 때 풀리지 않으면 작은 문제부터 해결)

(ref: galid1.tistory.com/507)

 

그리디 알고리즘이란?

문제를 해결하는 과정에서 그 순간순간마다 최적이라고 생각되는 결정을 하는 방식으로 진행하여 최종 해답에 도달하는 문제 해결 방식

ref: https://velog.io/@cyranocoding/%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming%EA%B3%BC-%ED%83%90%EC%9A%95%EB%B2%95Greedy-Algorithm-3yjyoohia5#:~:text=com%2Fgreedy.php-,Greedy%20Algorithms(%ED%83%90%EC%9A%95%EB%B2%95%2C%20%ED%83%90%EC%9A%95%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98),%ED%95%98%EB%8A%94%20%EB%AC%B8%EC%A0%9C%20%ED%95%B4%EA%B2%B0%20%EB%B0%A9%EC%8B%9D%EC%9D%B4%EB%8B%A4.

 

[문제]

www.acmicpc.net/problem/2839

2839번: 설탕 배달

 

[선배 개발자들의 코드 분석]

대부분이 비슷했다. 조금의 차이가 있었을 뿐! 다행이당ㅎㅎㅎ

근데 시간은 52ms라고 되어 있던데 나랑 어떤 부분에서 차이나는걸까? divmod 함수 때문인가?

>> 아닌데, 더 오래 걸리는데??? if else를 매번 체크해서 그런 것 같기도 하다.

>> if else도 최소한으로 쓰는 게 보기에 더 깔끔할 수도 있을 것 같다.

이 분은 나눠서 하지 않고 반대로 N에서 줄여나갔다! 이런 방식으로 하시는 분들 보면 신기함. 어떻게 반대로 구현할 생각을 할까?

 

[느낀 점]

동적프로그래밍은 모든 경우의 수를 돌아보며 최적의 경로를 찾는 것이고(시간은 오래 걸리지만 '최적'의 경로를 찾을 수 있음) 그리디 알고리즘은 모두 다 돌지 않지만 최적의 선택을 계속 내리며 최적의 경로를 찾는 것이다. (시간은 오래 걸리지 않지만 '최적'의 경로라고 확신할 수 없음)

 

동적프로그래밍과 그리디 알고리즘의 개념 및 예제를 알지 못한채로 문제를 풀었다.

결국 내가 구현했던 방법은 동적프로그래밍을 구현할거라 생각했지만(무슨 일을 하던 꼼수(?)보다는 기본이 중요하다고 생각하기에 확실한 방법인 시간이 오래 걸리는 게 낫다고 생각한다.) 나는 그리디 알고리즘을 사용했다. 내 성향이 여기서 이렇게 드러날 줄이야....

 

(알고리즘 종류를 모르는데도 이미 알았던 것 처럼 틀에 박히지 않고 구현할 수 있지 않을까? 라는 막연한 나에 대한 믿음 때문에 알고리즘을 따로 공부하지 않았었다. 사실 이 순간은 기쁘지만 알았더라면 더 좋았을 것 같다. 역시 나는 고집이 쎄다. 경험해봐야 인정하는 듯..ㅎㅎ)

 

오늘 문제 너무 재밌었다!