문제를 풀면서 생각의 전환이 필요하거나 새로운 접근 방법이 필요한 경우를 여기에 정리해보자.
방향 바꾸기
- 앞에서부터 생각하다가 막히면 뒤에서부터 생각해보기
- 방향이 바뀌면 계산 단계가 줄어들 수 있다.
SWEA - 백만 장자 프로젝트
두 개의 인덱스를 찾는 문제
이중 for문은 시간을 많이 소요하지만 해결책일수도, 아닐수도 있다.- 시간 초과가 난다면 여러 연산의
time complexity계산해보기 hash를 쓰는 것도 좋은 방법
문제 규모 바꿔보기
- 작은 부분의 정답이 전체의 정답이거나 오히려 범위를 넓혀서 생각할 경우 정답이 나올 수 있다.
리스트 순회 문제
- 단순히 일방향으로 계속 순회를 하면 시간초과 발생 가능
- 별도의 메모리를 사용할 수는 있지만 공간초과 발생 가능
python의 경우collections.Counter고려해보기- 규칙을 찾아서 한번에 적용하면 시간 줄이기 가능할지도?
LeetCode - Rotate Array
메모리 절약하기
- DP 문제의 경우 별도의 저장 공간을 사용하다 보면 메모리 초과 발생 가능. 이 때는 별도의 변수를 선언해 값을 계속 바꿔 가면서 일종의
tabulation처럼 사용 가능.
백준 - 01타일
스택, 큐 문제
- element들이 순서대로 들어오면서 이들의 대소를 비교해 연산하는 문제들은 스택, 큐를 활용할 수 있다.
- LIFO, FIFO의 특성을 정확히 파악할 것
- 순서 문제의 경우
for문이 막히면while문으로 생각해 볼 것 append,pop과 같이 시간 복잡도가 낮은 연산을 사용해야 한다.
힙 문제
- 문제에 최소, 최대가 언급된 경우 힙의 사용을 고려할 수 있다.
- python에서는
heapq를 사용해 힙을 사용할 수 있다. - 최대 힙을 구현하는 경우는
heapq.heappush(heap, -(num, num))을 통해 구현하고heapq.heappop(heap)[1]을 사용해pop연산을 수행할 수 있다.(우선순위 고려하지 않으므로)
그리디 알고리즘
- 문제 접근이 힘든 경우 그리디 알고리즘의 사용을 고려해볼 수 있다.
- 앞의 선택이 이후 선택에 영향을 주지 않고, 문제에 대한 최종 해결 방법이 부분 문제에 대해서도 최적의 문제 해결 방법인 경우
- 선택이 영향을 받는다면 분리할 수도 있을까?
백준 - 전구와 스위치 / 백준 - 잃어버린 괄호
탐색 (DFS, BFS)
- DFS는 스택, BFS는 큐
- 변수를 쓰는 걸 두려워하지 말자
while queue안에 queue의 길이를 변수로 받아서 하나씩 빼주는 방식으로 변형할 수 있다.
백준 - 탈출
YOU ARE BREATHTAKING