[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.
- 그리디 알고리즘
- Q&A
- 마치며
1. 그리디(Greedy) 알고리즘
- 그리디(Greedy) 알고리즘
: 지금 가장 최적인 답을 근시안적으로 택하는 알고리즘
: 관찰을 통해 탐색 범위를 줄이는 알고리즘
1) 그리디 알고리즘을 푸는 과정
(1) 관찰을 통해 탐색 범위를 줄이는 방법을 고안
직관적으로 보이는 풀이의 시간복잡도로, 문제에서 제시한 시간 제한 안에 들어올 수 없을 때,
시간복잡도를 더 낮출 수 있는 방법을 관찰함.
(2) 탐색 범위를 줄여도 올바른 결과를 낼 수 있음을 수학적으로 증명
(3) 구현 후 해결!
하지만, 실제 코테에서는 시간이 촉박하므로, 수학적으로 꼼꼼히 증명하기가 힘듦.
따라서, 방법을 고안하고 대충 주어진 예제에서 잘 돌아가는지 확인 후 구현함.
이런 과정에서 절망적인 풀이 흐름은,
1번에서 잘못된 방법을 고안하고, 2번에서 잘못되었음을 증명하지 못하고, 3번에서 계속 틀리는 경우임.
(잘못된 방법이라서 틀린건지, 구현이 잘못되었는지 알 수 없음.)
2) 코테 추천 전략
따라서 코테 추천 전략은!
(1) 거의 똑같은 문제를 풀었거나, 정말 간단한 문제여서, 풀이를 100% 확신할 때
답을 제출해 보고, 틀리면 빨리 손절!!!
(2) 100% 확신은 없지만, 맞는 것 같은 그리디 풀이를 찾았을 때
일단은 넘어가고, 다른 문제를 풀게 없거나 종료가 20 ~ 40분 정도 남은 시점에 코딩 시작!!!
2. Q&A
-
3. 마치며
-
[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.
아무것도 모르는 컴공 학생의 Wonder_Land