발전생

정확도 테스트에서는 맞는데 효율성 테스트에서 실패한다면 시간 복잡도를 줄여야 합니다. 트리나 그래프의 문제를 제외하면 대부분의 문제는 시간 복잡도 O(N^2)으로 풀 것입니다. 하지만 효율성이 좋지 못하다는 것은 O(N) 알고리즘이 존재할 가능성이 있다는 것입니다. O(N^2) => O(N) 바꾸는 알고리즘 스택 해시 그리디 투 포인터 모든 문제에 이 알고리즘들이 적용되지는 않겠지만 배열을 사용하는 문제라면 이 세 알고리즘들로 시간 복잡도를 줄일 수 있을 지도 모릅니다.

반복되는 부분 문제를 가진 경우 시간 복잡도를 줄일 수 있는 방법에는 재귀에서 memoization dp 테이블 만들기 두 가지 방법이 있다. 재귀는 예외 케이스만 잘 처리해주고 이미 계산된 값이면 리턴해주면 된다. 재귀의 관점은 어느 정도 익숙해졌지만 항상 재귀로 풀다 보니 dp 테이블 만드는 방식이 감이 안 왔다. DP 테이블 만들 때 유용한 사고 전략 몇 가지를 생각해봤다. 문제들을 풀어보며 확인한 패턴이다. 보통 dp 테이블을 만들 때는 처음 인덱스부터 하나씩만 훑으면서 테이블을 갱신해간다. 1. 해당 인덱스를 포함하거나 포함하지 않거나 어찌 보면 2번과 같은 맥락으로 생각할 수 있지만 직관적으로 1번 표현이 좀 더 자연스러울 때가 있다. 2. 해당 인덱스부터 / 해당 인덱스까지 '해당 인덱스부터..

이진 탐색은 쉬운듯 하면서도 어려운 알고리즘이다. 경계를 잘못 설정하면 while 문을 빠져나오지 못 하게 된다. 그렇다고 여러 테스트 케이스를 매번 고려하면서 짜기에는 시간이 너무 오래 걸린다. 어느 조건에 =을 넣어줘야 하며 left, right 갱신 시 mid로 할지 mid -1 혹은 mid + 1로 할지 고민하는 건 꽤나 골치 아픈 일이다. 그래서 나름의 템플릿이 있으면 빠르게 이진 탐색 코드를 짤 수 있겠다는 생각이 들어서 정리하는 중이다. 가장 기본 형태 left, right = 0, len(arr) - 1 while left < right: mid = left + (right - left) // 2 if arr[mid] < target: left = mid + 1 else: right = m..