Google 태그 관리자 아이콘

알고리즘 풀이

.review(알고리즘 문제풀이 접근)

silvergoni 2022. 4. 11. 08:05
반응형

Leetcode 문제를 풀어가면서 느끼고 문제를 풀기전에 먼저 생각해봤으면 좋았을 내용을 하나씩 더해간다. 물론 없어지기도 하고 관련 있는 내용은 합치기도 한다.

 

알고리즘을 풀면서 기억하기  

  1. divide and conquer(quick sort, merge sort)
    1. 원리 이해하기
      1. https://silvergoni.tistory.com/entry/leetcode-347-Top-K-Frequent-Element 
      2. https://silvergoni.tistory.com/entry/leetcode-148-Sort-List
  2. Heap, PriorityQueue
    1. while문에서 pq.size()를 꼭 확인하자.
      1. https://silvergoni.tistory.com/entry/programmersH-Index
    2. 우선순위 큐를 이용해보자
      1. https://silvergoni.tistory.com/entry/programmers%EC%9D%B4%EC%A4%91%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84%ED%81%90 
      2. https://silvergoni.tistory.com/entry/programmers%EB%94%94%EC%8A%A4%ED%81%AC-%EC%BB%A8%ED%8A%B8%EB%A1%A4%EB%9F%AC 
      3. https://silvergoni.tistory.com/entry/programmers%EB%8D%94-%EB%A7%B5%EA%B2%8C 
      4. https://silvergoni.tistory.com/entry/programmers%EC%A3%BC%EC%8B%9D%EA%B0%80%EA%B2%A9 
      5. https://silvergoni.tistory.com/entry/leetcode-347-Top-K-Frequent-Element
  3.  Map
    1. value기준으로 순서정렬하는거 익혀두자.
      1. https://silvergoni.tistory.com/entry/programmers%EB%B2%A0%EC%8A%A4%ED%8A%B8%EC%95%A8%EB%B2%94
  4.  배열
    1. 중복제거 하기
      1. https://silvergoni.tistory.com/entry/leetcode414-Third-Maximum-Number
    2. swap으로 처리하기
      1. https://silvergoni.tistory.com/entry/leetcode905-Sort-Array-By-Parity
      2. https://silvergoni.tistory.com/entry/leetcode-283-Move-Zeroes
    3. 뒤에서부터 읽으면 어떻게 처리될지 생각해보자.
      1. https://silvergoni.tistory.com/entry/leetcode1299-Replace-Elements-with-Greatest-Element-on-Right-Side
    4. edge케이스 처리를 신경쓰자
      1. https://silvergoni.tistory.com/entry/leetcode487-Max-Consecutive-Ones-II 
      2. https://silvergoni.tistory.com/entry/leetcode941-Valid-Mountain-Array 
      3. https://silvergoni.tistory.com/entry/leetcode1346-Check-If-N-and-Its-Double-Exist
    5. 인덱스 위치 기억하기
      1. https://silvergoni.tistory.com/entry/leetcode-283-Move-Zeroes 
      2. https://silvergoni.tistory.com/entry/leetcode80-Remove-Duplicates-from-Sorted-Array-II 
      3. https://silvergoni.tistory.com/entry/leetcode26-Remove-Duplicates-from-Sorted-Array 
      4. https://silvergoni.tistory.com/entry/leetcode27-Remove-Element
    6.  머지하기
      1. https://silvergoni.tistory.com/entry/leetcode88-Merge-Sorted-Array
    7. 요소를 이동해야한다면 쉬프트 말고 다른 방식이 있을지 고민해보자.
      1. https://silvergoni.tistory.com/entry/leetcode1089-Duplicate-Zeros
    8. String.compareTo를 잘 이용해보자.
      1. https://silvergoni.tistory.com/entry/programmers%EA%B0%80%EC%9E%A5-%ED%81%B0-%EC%88%98
    9.  Arrays.copyOfRange()
      1. https://silvergoni.tistory.com/entry/programmersK%EB%B2%88%EC%A7%B8%EC%88%98
    10. left,right로 접근하기
      1. https://silvergoni.tistory.com/entry/leetcode977-Squares-of-a-Sorted-Array 
      2. https://silvergoni.tistory.com/entry/leetcode905-Sort-Array-By-Parity 
      3. https://silvergoni.tistory.com/entry/leetcode852-Peak-Index-in-a-Mountain-Array 
      4. https://silvergoni.tistory.com/entry/leetcode344-Reverse-String
    11. 떄론 정렬을 미리 해두고 풀면 좋다. int[]라면 reverseOrder보다는 인덱스를 뒤에서 접근하는 방식으로 풀어보자.
      1. https://silvergoni.tistory.com/entry/leetcode414-Third-Maximum-Number 
      2. https://silvergoni.tistory.com/entry/leetcode1051-Height-Checker 
      3. https://silvergoni.tistory.com/entry/leetcode16-3Sum-Closest
    12. 길이가 고정이라면 전역변수로 row, col 길이를 선언해두면 편리하다.
      1. https://silvergoni.tistory.com/entry/leetcode-200-Number-of-Islands
    13. 정렬된 array라면 포인터 사용도 염두해보자
      1. https://silvergoni.tistory.com/entry/leetcode977-Squares-of-a-Sorted-Array 
      2. https://silvergoni.tistory.com/entry/leetcode167-Two-Sum-II-Input-Array-Is-Sorted 
  5. dfs
    1. visited를 설정해서 풀어본다.
      1. https://silvergoni.tistory.com/entry/leetcode547-Number-of-Provinces
  6. bfs
    1. visited를 설정해서 풀어본다.
      1. https://silvergoni.tistory.com/entry/leetcode547-Number-of-Provinces
    2. 방향이 있다면 미리 static하게 선언해주면 코딩이 깔끔해진다.
      1. https://silvergoni.tistory.com/entry/leetcode-200-Number-of-Islands
  7. 재귀함수
    1. 재귀함수는 본 솔류션을 메소드로 이용하기보단 서브메소드를 하나 만들어서 확인해보는게 더 빠르다.그 뒤에 가능하다면 본 메소드를 이용하여 재귀를 리팩토링하는 과정을 거친다.
      1. https://silvergoni.tistory.com/entry/leetcode-206-Reverse-Linked-List
  8. 구현
    1. 시간복잡도가 뚜렷하다면 일단 생각나는 방식이 조금은 노가다성일지라도 바로 구현해보면 좋다. 최적시간복잡도가 아니어도 기준시간이상(임의로 시간을 정해서, 내기준 10분) 구상이 안된 상황에서 brute  force방법이라도 생각난다면 일단 구현해보자.
      1. https://silvergoni.tistory.com/entry/leetcode118-Pascals-Triangle
      2. https://silvergoni.tistory.com/entry/leetcode-206-Reverse-Linked-List
      3. https://silvergoni.tistory.com/entry/leetCode-1-Two-Sum
 

.leetcode(547. Number of Provinces)

https://leetcode.com/problems/number-of-provinces/ 1. 2022/04/10 시도 소요시간: 38분 class Solution { private int[] rootArray; private int[] rank; public int findCircleNum(int[][] isConnected) { roo..

silvergoni.tistory.com

 

.leetcode(662. Maximum Width of Binary Tree)

https://leetcode.com/problems/maximum-width-of-binary-tree/ 1. 2022.03.01 시도 소요시간: 37분(4분 구상, 20분까지 코딩, 13분 재코딩, bfs), 11분(dfs) // bfs class Solution { public int widthOfBinaryTr..

silvergoni.tistory.com

 

누적사용 설명서

  1. 제한값이 있는지 확인한다.
  2. 최대 시간복잡도나 최대 경우의 수를 유추해본다.
  3. 기본으로 주어지는 메소드에서 해결이 가능한지 생각해본다. > 메소드를 만들어 사용한다. > 전역변수를 과감히 도입한다.
  4. recursion(Brute Force, Back Tracking)으로 가능할지 먼저 생각해본다. 이 후에 iterative하게 풀 수 있을지도 생각해본다. iteratvie하게 풀때는 stack을 이용해본다. 경우의 따라 queue를 사용해볼 수 있다.
  5. recursion일 경우, 종료조건을 먼저 만들고 로직을 만든다.
  6. 주어진 Input데이터를 더렵힐 수도 있다고 생각해본다. 덮어쓰기한다던지, 더해서 합값으로 치환한다던지 말이다.
  7. TreeNode는 left,right,val으로 구성해볼 수 있고 ListNode는 val,next로 구성해볼 수 있다.
  8. ListNode문제가 나오면 꼭 그림으로 next관계를 이해해보자. 그리고 기존의 데이터를 이용해서 이어잘라붙이기에 대한 시도도 꼭 해보자.
  9. 배열에서 갯수를 센다고 하면 Brute force, HashMap, Sorting방법을 생각해보자.
  10. 만약에 대다수를 구하는 문제라면 Boyer–Moore majority vote algorithm를 생각해보자.
  11. Arrays 디버깅할때 Arrays.stream(nums).boxed().forEach(System.out::println);하면 결과를 볼수 있다.
  12. 순서, 부호를 이용해서 공간을 절약할 수 있는지 생각해본다.
  13. 간단한것 부터 생각해본다. 배열이 있다면 인덱스를 양방향으로 사용하기보다는 한방향으로 사용해보고 정안되면 양방향으로 생각을 바꿔보자. 간단하게 생각하고 간단하게 문제를 만들줄 알아야한다.
  14. 값을 원하는지 요소를 원하는지 확인해라. 일반적으로 값을 구하는게 더 간단하게 풀 수 있다.
  15. dp라고 생각되면 꼭 캐쉬를 염두해두자. dp로 풀때는 큰문제를 작은문제로 쪼갤 수 있다는 것이고 그런게 보이면 조건, 초기화, 공식에 대해 한번 확인해보자.
  16. divide and conquer 방법도 가능한지 생각해보자. https://silvergoni.tistory.com/entry/leetcode-53-Maximum-Subarray
  17. 자료형이 LinkedList일때 순환의 3가지 풀이법에는 HashSet, Arrays.sort, Floyd tortoise and hare 방법이 있다.
    https://silvergoni.tistory.com/entry/leetcode-141-Linked-List-Cycle
  18. linkedList문제가 나오면 17번도 기억하고 공간의 사용없이 순서를 변경할 수 있다는 것도 기억하자. silvergoni.tistory.com/entry/leetcode-234-Palindrome-Linked-List
  19. 쌍으로 짝을 맞추는게 있다면 stack을 한번 사용해보라. https://silvergoni.tistory.com/entry/leetcode-20-Valid-Parentheses
  20. Greedy풀이 방법으로의 접근 https://silvergoni.tistory.com/entry/leetcode-53-Maximum-Subarray
  21. 구간의 확장 문제도 Greedy로 풀 수 있다. https://silvergoni.tistory.com/entry/leetcode-763-Partition-Labels
  22. 이진법 문제가 나오면 비트 연산을 생각하고 쉬프트연산도 생각해서 풀어보자. https://silvergoni.tistory.com/entry/leetcode-338-Counting-Bits
  23. 트리에서 Inorder traverse가 필요하다면 morris방법을 기억해두자. https://silvergoni.tistory.com/entry/leetcode-94-Binary-Tree-Inorder-Traversal https://silvergoni.tistory.com/entry/leetcode-230-Kth-Smallest-Element-in-a-BST
  24. bitmask를 모두 찍어낼 수 있는 방법을 꼭 기억하자. https://silvergoni.tistory.com/entry/leetcode-78-Subsets
  25. 문제의 조건을 유심히 보고 특히 종료 조건이 있다면 거기서부터 풀이를 생각해보자. https://silvergoni.tistory.com/entry/leetcode-739-Daily-Temperatures
  26. bst면 그 특성을 이용하라. https://silvergoni.tistory.com/entry/leetcode-230-Kth-Smallest-Element-in-a-BST
  27. 양퍼버젼으로 풀기 palindromic https://silvergoni.tistory.com/entry/leetcode-647-Palindromic-Substrings
  28. k-th를 푸는법은 priorityQueue, array라면 quicksort를 이용해본다. https://silvergoni.tistory.com/entry/leetcode-215-Kth-Largest-Element-in-an-Array https://silvergoni.tistory.com/entry/leetcode-347-Top-K-Frequent-Element
  29. dp스럽다고 생각되는 문제가 나오면 결국 얻고자하는 요소를 결정하는 요소들의 비교를 어떻게 해야하는지 확인해보고 그걸 유한하게 만들려면 어디서부터 출발해야할지 결정할 수 있다. https://silvergoni.tistory.com/entry/leetcode-64-Minimum-Path-Sum
  30. 재귀로 넘어가는데 재귀당 다음 재귀로의 방법을 recursive, iterative하게 할 수 있는데 이는 다시 말해서 bfs와 dfs로 풀 수 있기도 한 것이다. https://silvergoni.tistory.com/entry/leetcode-200-Number-of-Islands
  31. 트리에서 부모를 찾는 문제라고 생각되면 사실 그건 recursion으로 어떤 값을 리턴할지 그리고 그 리턴값의 판단은 무엇으로 할지의 문제로 해석해보는게 좋다. https://silvergoni.tistory.com/entry/leetcode-236-Lowest-Common-Ancestor-of-a-Binary-Tree
  32. 자료형을 파악 -> 배열이면 앞,뒤 접근 선택 -> dp라면 상태값을 파악 -> 상태값에 영향주는 요소를 파악 -> 식으로 구성 https://silvergoni.tistory.com/entry/leetcode-309-Best-Time-to-Buy-and-Sell-Stock-with-Cooldown
  33. 합 문제는 되도록 합을 파라미터로 이용하자. 게다가 그 합에 갯수를 구하는 문제라면 합별 개수를 카운트 한걸 map에 저장해보도록 하자. https://silvergoni.tistory.com/entry/leetcode-437-Path-Sum-III
  34. 링크드리스트에 소팅은 merge sort로 해보자 https://silvergoni.tistory.com/entry/leetcode-148-Sort-List
  35. anagram같이 여러 요소로 구성된 부분집하을 찾을때 키를 만들어 풀어보자 https://silvergoni.tistory.com/entry/leetcode-49-Group-Anagrams https://silvergoni.tistory.com/entry/leetcode-39-Combination-Sum https://silvergoni.tistory.com/entry/leetcode-438-Find-All-Anagrams-in-a-String
  36. 합의 문제에서 제한적인 합이라면 dp로 접근해서 풀어보자. https://silvergoni.tistory.com/entry/leetcode-416-Partition-Equal-Subset-Sum https://silvergoni.tistory.com/entry/leetcode-494-Target-Sum
저작자표시 비영리

'알고리즘 풀이' 카테고리의 다른 글

.leetcode(261. Graph Valid Tree)  (0) 2022.04.12
.leetcode(547. Number of Provinces)  (0) 2022.04.11
.programmers(조이스틱)  (0) 2022.04.09
.programmers(체육복)  (0) 2022.04.09
.programmers(카펫)  (0) 2022.04.09

'알고리즘 풀이'의 다른글

  • 현재글.review(알고리즘 문제풀이 접근)

관련글

댓글

티스토리툴바