贪心：过了样例不等于对
唯一一类跑过样例仍然可能彻底错的算法。
프롬프트를 복사한 뒤 한 곳을 고르세요. 답을 늘어놓는 대신 면접관이 되어 장면마다 캐묻습니다.
앱이 설치된 휴대폰이면 시스템이 바로 앱을 엽니다. 위챗 안에서는 외부 앱을 열 수 없으니 먼저 브라우저로 여세요.
복사한 글 끝에는 채점용 정답이 붙어 있습니다. 먼저 읽지 마세요 —— 스스로 끌어내 봤는지가 핵심입니다.
贪心的正确性从来不是显然的：要么证明，要么被反例推翻，没有第三种状态。而贪心的反例往往需要三个以上元素、数值有意设计 —— 随手举的例子几乎必然通过，这就是它危险的地方。
这一份练两个工具：交换论证（假设有更好的解，把它第一处不同换成贪心的选择，证明不会变差）和构造反例。一说「我试了几个例子都对」就会被打断。
中间会拿两道长得几乎一样的题对照：活动选择贪心是对的，0/1 背包贪心是错的 —— 差在哪。
이 편이 단련하는 것
이 본문을 저장소에서 보기 (그 파일 끝이 정답 패입니다. 열면 보입니다)
이 문제 해봤나
로그인하면 이 문제를 해봤다고 기록할 수 있습니다. 다음에 오면 언제 했는지 보입니다.
해본 사람들의 기록
사용법
이 묶음은 학습형입니다: 말문이 막힐 때까지 몰아붙이지 않고 이끕니다. 막히면 먼저 「어느 층에서 막혔는지」를 묻습니다(들어본 적 없음 / 알지만 왜인지 모름 / 알지만 못 씀). 같은 지점에서 두 번 이끌어도 안 되면 그때 답을 말하고, 그다음 당신의 말로 다시 설명하게 합니다.
시작하는 법
- 하나 골라서 열고, 프롬프트를 복사합니다.
- 새 빈 대화에 붙여 넣고, 아무 말도 하지 말고 첫 질문을 기다립니다.
- 코드보다 손으로 따라가기가 먼저 —— 도중에 끊어 줍니다. 길이 2인 배열에서 한 단계씩 따라가는 편이 템플릿을 열 번 쓰는 것보다 낫습니다.
도중에 언제든 외칠 수 있는 네 가지 명령
跳过바로 다음 장면으로换个说法이 부분을 다른 각도로 다시 설명直说吧답을 전부 말하고, 그다음 내가 다시 설명하게复盘바로 마무리로 넘어가 회고 카드 출력
세 가지 함정
- 끝에 있는 정답 카드를 먼저 읽지 마세요 —— 그 「흔히 잘못 아는 것」 항목이 곧 모든 질문의 답입니다.
- 코드부터 쓰지 마세요. 알고리즘에서는 코드를 쓰는 행위가 「사실은 이해하지 못했다」를 가장 잘 가려 줍니다.
- 칭찬하기 시작하면 「칭찬하지 말라」는 철칙을 상기시키세요. 이끄는 것과 달래는 것은 다릅니다.
풀이가 안 떠오르면 「상태 정의」부터. 경계를 자꾸 틀리면 「이분 탐색」과 「누적 합」. 문제의 형태를 못 알아보면 「단조 스택」과 「슬라이딩 윈도」. 「복잡도」 편은 여러 편의 토대이니 일찍 하세요.
로그인 후에 기록을 남길 수 있습니다.