목록Data Structures, Algorithm/종만북 (23)
KoreanFoodie's Study
[종만북 요약] 4~5. 알고리즘 분석 (P-NP, 알고리즘 정당성 증명)
프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)을 읽으며 유용한 내용을 정리해 보도록 하겠습니다. 모든 내용을 요약하는 것은 아니며, 대회에 포커싱을 맞춘 부분은 다루지 않을 수도 있습니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다! 핵심 : 1. 수행 시간 어림짐작은 유용하지만, 엄밀하지는 않으니 최적화 시에는 여러 인자들을 함께 고려해 보자. 2. 알고리즘의 정당성 증명은 해당 알고리즘의 통찰을 이해함에 있어 중요하다. 3. 알고리즘의 정당성 증명 방법은 귀납법, 반복문 불변식, 귀류법, 비둘기집의 원리, 구성적 증명 등이 있다. *챕터 2 에서는 한 번 되짚어 볼 만한 내용을 일부 발췌해 정리해 보겠습니다. 수행 시간 어림짐작하기 일반적으로 우리는 Time..
[종만북 문제] 록 페스티벌 (난이도: 하, 문제 ID : FESTIVAL)
프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)에서 소개된 문제를 풀이합니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다! 핵심 : 1. 기본적으로는 이중 for-loop 으로 풀 수 있으나, DP 를 사용하면 시간을 조금 단축할 수 있다. 2. 소수점 오차에 유의하자. 록 페스티벌 (난이도: 하, 문제 ID : FESTIVAL) 사실 2중 for-loop 만 돌리면 쉽게 풀 수 있는 문제이긴 하다. 따라서 따로 설명을 길게 적지는 않고, 코드에 주석을 조금 달아 두었다! 😄 #include #include "stdlib.h" using namespace std; int N, L; int days[1000]; int dp[1000]; double ans; doub..
[종만북 요약] 1~3. 문제 해결 시작하기 (PS 문제 해결 단계와 좋은 코드를 위한 조언)
프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)을 읽으며 유용한 내용을 정리해 보도록 하겠습니다. 모든 내용을 요약하는 것은 아니며, 대회에 포커싱을 맞춘 부분은 다루지 않을 수도 있습니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다! 핵심 : 1. 프로그래밍은 문제 해결이다. 2. 간결하고 모듈화된 코드를 짜라. 이는 버그를 줄여주고 디버깅 효율을 높여준다. 3. 자주 범하는 실수에 대한 유형을 알아두자. 프로그래밍은 문제 해결이다. 1장에서는 알고리즘에 대한 코딩에 대한 저자의 철학과, 앞으로 다룰 주제에 대한 간략한 맛보기(?)가 제공된다. 거기에 배운 지 오래되어 기억의 저편에 묻혀 있거나, 생각해보면 좋은 꿀팁들에 대해서도 조언을 아끼지 않는다. 이번 글..