투 포인터, 슬라이딩 윈도우, 누적합
“이것을 위해", 즉 “특별한 목적을 위해서”라는 뜻을 가진 라틴어라고 합니다.
정형화된 알고리즘 없이, 문제를 보고 패턴을 분석하여 나만의 알고리즘을 설계해야 합니다.
애드혹 문제들을 쉽게 잘 푸는 사람이 있다면, 머리가 진짜 좋다고 생각하시면 됩니다. ㅎㅎ
boj.kr/21553 : 스페셜 저지 문제들은 코드 수행 결과로 출력된 값을 검증하는 방식으로 채점합니다.boj.kr/1813 : 1분 안에 이 문제를 푼다면 당신은 진정한 고수boj.kr/4307 : 이제는 너무나도 유명한 개미문제현재 상태에서 다음을 생각하지 않고, 가장 최선인 선택을 하는 알고리즘입니다.
보통 구현은 쉽지만 증명이 매우 어려우며, 찍어서 맞추는 경우도 의외로 많습니다. (농담으로 proof by AC 라고도 합니다)
코테에서는 대부분 어려운 그리디가 안나오기 때문에 간단한 문제들만 짚고 넘어가겠습니다.
간단한 예시로 boj.kr/5585 문제를 보겠습니다.
거스름돈을 줄 때 동전을 가장 적게 사용해야하는 문제입니다.