DP 완전 정복

1. 배경 이분 탐색 다음으로 정리할 알고리즘으로 DP를 택한 것은 이분 탐색과 완전히 대척점이 되는 점에서 어렵게 느껴졌기 때문이다. 이분 탐색의 경우 구현 자체는 쉽지만 문제 접근을 이분 탐색으로 해야된다는 것을 깨닫는 것이 어렵다면 DP는 뭔가 딱 봐도 DP로 구현해야될 것 같은데 실제 코드로 구현하는 것이 어렵기 때문이다. 따라서 이분 탐색에서 접근 방법 위주로 글을 썼다면 이번엔 구현을 어떻게 해야 하는지 위주로 글을 쓰고자 한다. 2. DP란? 부분 반복 문제과 최적 부분 구조를 가지는 알고리즘을 메모제이션을 통해 더 빠르게 해결하는 방법을 말한다. 정의가 어렵지 않고 피보나치의 유명한 예시 덕분에 많은 사람들이 정의를 어려워할 것이라 생각하지는 않는다. 핵심적인 개념을 짚고 넘어가자면 "부분..

• format_list_bulleted algorithm
• · 2023. 8. 24.
• textsms

이분탐색 완전 정복

1. 배경 ps 문제를 풀면서 해결 알고리즘을 떠올리지 못하는 유형이 공통적인 것을 깨달았는데 바로 이분 탐색 문제였다. 대체로 고난이도 레벨(4 이상)에 배정되어 있으면서 구현 후 효율성 검사에 번번이 실패하는 것으로 보아 한번 정확하게 짚고 넘어가야겠다는 생각을 했다. 사실 이분탐색 알고리즘 자체를 이해하지 못하는 경우는 거의 없을 것이다. 하지만 실전 문제에서 이걸 이분 탐색으로 풀어야 되었다니..!!! 하면서 온갖 삽질을 했던 기억이 있기 때문에 문제와 함께 실전적으로 파악하고자 한다. 2. 이분 탐색이란? 이분 탐색이란 검색 범위를 줄여 나가면서 원하는 데이터를 검색하는 알고리즘이다. 어떻게? 찾으려는 데이터 값을 정렬된 데이터에서 중간점의 위치와 반복 비교하여 위치를 찾는다. 시간 복잡도 : ..

• format_list_bulleted algorithm
• · 2023. 8. 23.
• textsms