[알고리즘] 문제 해결 전략

김학재·2020년 10월 14일
0

알고리즘

목록 보기
4/10
post-thumbnail

문제를 풀면서 생각의 전환이 필요하거나 새로운 접근 방법이 필요한 경우를 여기에 정리해보자.


방향 바꾸기

  • 앞에서부터 생각하다가 막히면 뒤에서부터 생각해보기
  • 방향이 바뀌면 계산 단계가 줄어들 수 있다.
    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의 길이를 변수로 받아서 하나씩 빼주는 방식으로 변형할 수 있다.
    백준 - 탈출
profile
YOU ARE BREATHTAKING

0개의 댓글