[Algorithm] 접근 방법 정리

알고리즘 풀이 접근 방법 정리

🧢난이도에 대한 생각

1. 결국 풀어보면 논리적으로 어려운 문제는 없다.
2. 풀이가 생각이 나는가, 나지 않는가의 문제로 귀결된다.

🧢시간 초과에 대한 생각

1. 시간 초과가 발생했다면, 기존 방법에서 "미세한 튜닝"을 하지 말고 ✨과감하게 방향 전환✨하라.

   • "미세한 튜닝"에 접어들게 되면 출제자의 의도에 벗어난 경우가 대부분이고, 문제 풀이의 복잡도만 높아진다.
   • 기존에 작성한 코드는 메모장에 적어둬라.(종종, 다시 시험해 보고 싶은 아이디어가 생각나더라.)

2. ✨구조적인 관점에서 loop를 줄이는 방향✨으로 접근한다.

   • 3중 반복문 -> 2중 반복문, 2중 반복문 -> 1중 반복문

3. loop을 다 줄였다면, ✨같은 작업은 낮은 복잡도로 해결✨할 수 있는 방법에 대해서 고민하자.

   • len(set(list))
   • len(Counter(list))
   • len(defaultdict(list))

🧢특정 아이디어에 대한 매몰

• 문제를 풀다보면 종종 "지금 떠올리고 있는 아이디어"에 매몰되어 있는 모습을 보인다. 에너지가 소모됨을 느낀다면 무조건 ✨리프레쉬(산책, 멍때리기)✨ 하자.
  • 산책을 하면 아이디어가 떠오른다.
  • 뇌가 효율적으로 작업하고 있지 않다는 신호이다.

🧢문제 접근 방식

• 문제에 적시된 정답에 매몰되어 접근 방식도 정답에 의존하는 상황을 경계하라. 다양한 접근 방식으로 정답을 얻을 수 있다.
• 예를 들어 "보석 쇼핑"문제에서 정답이 "가장 짧은 구간" 이라고해서 문제를 "짧은 구간 순서대로 접근"할 필요는 없다. 이 문제에서는 위와 같이 접근하면 3중 반복문으로 시간 초과가 발생함.

🌊자료 구조

• 🎇stack

  • LIFO 구조일 때 사용하자. list로 사용.
  • 조건 확인과 반복이 메모리의 마지막 값에서 수행될 때 stack 사용. (stack.pop())
  • DFS문제는 stack을 사용.

• 🎇queue

  • from collections import deque
  • FIFO 구조일 때 사용.
  • 조건 확인과 반복이 메모리의 첫번 째 값에서 수행될 때 queue 사용. (quque.popleft())
  • BFS문제는 queue를 사용.

• 🎇dictionary

  • key-value mapping할 때 사용.
  • key2idx, idx2key 이렇게 두개 만들면 자유롭게 이동 가능.

• 🎇default dictionary

  • from collections import defaultdict
  • key값에 해당하는 정보가 몇번 들어왔는지 value값에 숫자를 카운팅할 때 사용.
  • dfdict = defaultdict(lambda : 0) key값이 새로운 값이라면 자동으로 0으로 인식.

• 🎇array list

  • {'key1' : [1, 2, 3, 4], 'key2' : [1, 2, 4, 6]} 이런걸 key1 = 0, key2 = 1 이렇게 암묵적으로 생각하여 생성
  • 반복문 돌기 수월.

  dict = {'key1' : [1, 2, 3, 4], 'key2' : [1, 2, 4, 6]} 
  
  arraylist = [[1, 2, 3, 4],
               [1, 2, 4, 5]]

• 🎇priority queue

  • import heapq
    • heapq.heappush(list, value)
    • heapq.heappop(list)
  • 우선 순위 큐 기능을 제공. (최소 힙만 제공, 최대 힙을 구현하려면 value에 음수를 넣는 트릭 사용.)
  • Dijkstra 알고리즘, priority queue 기능을 구현할 때 사용.

• 🎇set

  • 합집합 set1 | set2
  • 교집합 set1 & set2
  • 차집합 set1 - set2

🧢시간 복잡도

자료형	작업	시간 복잡도	추가 설명
list	append	$O(1)$
list	sort	$O(NlogN)$
list	reverse	$O(N)$
list	insert	$O(N)$
list	count	$O(N)$
list	remove	$O(N)$
set	add	$O(1)$
set	update	$O(1)$
set	remove	$O(1)$
dict	in	$O(1)$	존재 여부 확인
heapq	push	$O(NlogN)$
heapq	pop	$O(NlogN)$

🎇list와 deque 비교

작업	리스트	deque
가장 앞에 원소 추가	$O(N)$	$O(1)$
가장 뒤에 원소 추가	$O(1)$	$O(1)$
가장 앞에 원소 제거	$O(N)$	$O(1)$
가장 뒤에 원소 제거	$O(1)$	$O(1)$