본문 바로가기

algorithm/problem solving

 (7)
[리트코드 94, 144, 145] 이진 트리 순회(binary tree traversal) 3개의 문제지만 모두 이진 트리 순회에 대한 문제이다. 이전 포스트에서 설명했던 트리 자료구조의 중위 순회(inorder), 전위 순회(preorder), 후위 순회(postorder) 에 대한 개념만 알고 있으면 풀기 쉬운 간단한 문제이다. 간단하게 다시 설명해보자면 중위 순회는 나 자신이 가운데 즉, left -> root -> right 순으로 노드를 출력한다. 전위 순회는 나 자신을 시작으로 즉, root -> left -> right 순으로 출력된다.(root 를 가장 처음으로 방문하게 된다.) 마지막으로 후위 순회는 전위 순회랑 반대로 root를 가장 마지막으로 방문하게 되며, left -> right -> root 순으로 출력한다. Example 이진 트리인 root 가 주어졌을때, 순회 방..
[리트코드 46] DFS를 활용한 순열 문제풀이 잠시 고등학교 수학시간에 배운 내용을 되새겨보면.. 순열(permutation)이란? 서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 선택하는 혹은 나열하는 것. 순열의 수 수식은 nPr = n!/(n-r)! 으로 여기서 팩토리얼(!)이란 서로 다른 n개를 나열하는 경의 수를 의미한다. 기호로는 n! 으로 쓰고 계산은 n부터 1씩 줄여나가면서 1이 될때까지의 모든 수의 곱이다. (n! = n(n-1)(n-2)(n-3)...1) 46. 순열(Permutation) Example 주어진 서로 다른 정수의 배열로 가능한 모든 수열을 출력하라. (순서는 상관 없음) Constraints - 1 < nums.length
[리트코드 17] DFS 탐색 문제풀이2 DFS 탐색(깊이 우선 탐색) 알고리즘은 대표적인 그래프 탐색 방법 중 하나로 모든 노드를 방문(전체 탐색)해야하는 경우 BFS(너비 우선 탐색)에 비해 간단하게 풀이가 가능하여 선호되는 방식이다. 아래 문제의 경우도 모든 번호의 조합을 찾아야 함으로 DFS 방법으로 풀이할 예정이다. 17. 전화 번호 문자 조합 (Letter Combinations of a Phone Number) Example 주어진 2~9 사이의 숫자를 포함하는 문자열의 숫자가 나타낼 수 있는 가능한 모든 문자 조합을 출력하라. (단, 1은 어떤 문자도 매핑되어있지 않다.) 예를 들어 "23" 의 입력값이 주어졌을 때 2는 abc 의 문자 출력이 가능하고 3은 def 문자 출력이 가능하므로 각각 한 문자씩 조합을 해보면 총 9개의 ..
[리트코드 200] DFS 탐색 문제풀이1 *DFS란? Depth-first search의 약자로 깊이 우선 탐색하는 그래프 탐색 방법 중 하나이다. 자세한 내용은 [자료구조] 그래프(Graph) 참고. 200. 섬의 개수 (Number of Islands) Example - 주어진 2D 그리드 맵(m*n)에서 '1' 은 땅을 '0'은 물로 표현했을 때 섬의 개수를 출력하라. Constraints - m == grid.length - n == grid[i].length - 1 = m or j = n or grid[i][j] != '1': return # 탐색 여부 마킹 gri..
[리트코드 15] 투 포인터(Two Pointers) 를 활용한 문제풀이3 *투 포인터에 대해 모른다면, [리트코드 334] 투 포인터(Two Pointers) 를 활용한 문제풀이1 참고. 투 포인터를 활용하면 브루트 포스로 풀이하였을 때보다 시간복잡도(O)를 줄일 수 있다. 이번 문제도 브루트 포스로 풀이가 가능하나 시간복잡도O(n^3) 로 타임 아웃이 발생할 것이다. 그럼으로 투 포인터를 활용해 시간복잡도를 줄일 필요가 있다. 15. 세 수의 합 Example - 주어진 숫자 배열(nums) 중 합하여 0이 되는 세 개의 수를 구하라. (단, 정답에 동일한 세트가 있으면 안됨) 예) [[-1, -1, 2], [-1, 0, 1]] (o) [[-1, -1, 2], [2, -1, -1]] (x) Constraints - 0 List[List[int]]: answer = set()..
[리트코드 42] 투 포인터(Two Pointers) 를 활용한 문제풀이2 *투 포인터에 대해 모른다면 [리트코드 334] 투 포인터(Two Pointers) 를 활용한 문제풀이1 참고. 난이도가 높은 문제로 여러 가지 방법으로 풀 수 있지만 투 포인터를 이용하면 가장 높은 막대에서 좌우 포인터가 만나므로 시간복잡도 O(n) 로 풀이가 가능하다. (python, kotlin 두 언어로 풀이) 42. 빗물 트래핑 Example - 각 막대의 너비가 1인 고도를 나타내는 음이 아닌 정수 n개가 주어지면 비가 내린 후 얼마나 많은 물을 가둘 수 있는지를 계산한다. Constraints - n은 height의 길이이다. - 1
[리트코드 334] 투 포인터(Two Pointers) 를 활용한 문제풀이1 *투 포인터란? 시작점과 끝점 또는 왼쪽 포인터와 오른쪽 포인터 두 지점을 기준으로 하는 문제 풀이 전략으로 슬라이딩 윈도우(Sliding Window) 와 비슷한 점이 많아 여러 알고리즘 풀이와 관련해 실전적인 풀이 기법이다. (기본적으로 Call by Reference에 대한 이해도가 필요하다.) 334. 문자열 뒤집기(Reverse String) Example - 문자열을 뒤집는 함수를 작성하라. 입력값은 문자 배열이다. Constraints - 리턴 없이 리스트 내부를 직접 조작 할 것, 시간복잡도 O(1) Solution - 리스트 내부를 수정해야함으로 리스트(s)의 내부를 swap 하는 형태로 문자열을 뒤집는다. 코드 샘플 # python class Solution: def reverseStr..

티스토리툴바