리트코드
-
[알고리즘] BFS 정리개발 공부/Algorithm 2020. 12. 31. 14:52
리트코드 - leetcode.com/problems/serialize-and-deserialize-binary-tree/ 구글 인터뷰 문제 TOP10 중 2 위인 BFS 알고리즘 BFS 는 트리 구조의 Data를 너비 먼저 탐색하는 (Breath First Search) 알고리즘이다. 꼭 binary tree 가 아니여도 된다. BFS DFS ▪ 깊이가 얕고 노드가 적을 때 유리 ▪ DFS 보다 메모리를 더 많이 쓸 수 있다. 탐색할 모든 노드를 큐에 저장 ▪ 큐 (Queue) ▪ 답이 되는 경로가 최단경로 보장 ▪ 깊이가 깊고 노드가 많을 때 유리 ▪ BFS 보다 메모리를 더 적게 쓴다. 백트래킹을 해야하는 노드만 저장 ▪ 스택 (Stack), 재귀 (Recursive) ▪ 끝까지 찾아봐야 최단경로를 ..
-
[알고리즘] 2 Sum 찾기 - Hash Table 이용한 알고리즘 문제개발 공부/Algorithm 2020. 12. 16. 08:23
leetcode.com/problems/two-sum/ Two Sum - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 리트 코드 알고리즘, 1번 문제. 쉬운 문제이고 다양한 방법으로 풀 수 있지만 Hash Table의 원리를 이용하면 시간복잡도가 더 최적화된 방법으로 풀 수 있다. Approach Hash Table이 적용된 HashMap 을 이용한다. HashMap의 search (get이나 containsKey method) 는 key 기준이므로 value..
-
[알고리즘] Hash Table 구현하기개발 공부/Algorithm 2020. 12. 16. 04:57
leetcode.com/problems/design-hashmap/ Design HashMap - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com Hash Table은 검색에 O(1) 의 시간복잡도를 가져서 다른 Search 문제에도 많이 쓰이는 Data Structure 이다. Hash Table을 이용한 Hash Set, Hash Map의 Big O 참고 Hash Table이 Solution 으로 쓰인 문제 예시 더보기 leetcode.com/problems/..
-
[알고리즘] 스도쿠 2 - 스도쿠 풀이 (백트래킹, DFS)개발 공부/Algorithm 2020. 12. 11. 07:38
leetcode.com/problems/sudoku-solver/ Sudoku Solver - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 백트래킹이란, 맞는 답을 먼저 찾는 대신 일단 후보를 입력하고 답인것 처럼 진행하다가 조건이 안맞는 경우가 생기면 다시 되돌아와서 다른 후보값을 입력하는 방식으로 답을 찾는 알고리즘이다. 가지치기 (pruning) 처럼 답이 아닌 것들을 후보에서 제거하여 경우의 수를 줄여나가 답을 찾는 접근 recursive 를 사용하는 ..