본문 바로가기

분류 전체보기

 (11)
[리트코드 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
[Elasticsearch] Docker를 이용한 엘라스틱서치 설치 Docker 가 설치되어있지 않다면 우선 도커 홈페이지를 통해 다운로드를 받고 설치하면 된다. Elasticsearch 에 대해 간단히 얘기하자면 검색 엔진으로 java 로 개발되어 jvm 위에서 돌아간다. 그래서 도커가 아닌 로컬에 설치하는 경우 jre 또는 필요에 의해 jdk를 먼저 설치해줘야한다. 도커말고도 MacOS를 사용하는 사용자라면 Homebrew를 통해서도 쉽게 설치가 가능하다. 여기선 손쉽게 설치, 삭제가 가능한 Docekr를 이용해서 Elasitcsearch를 설치하는 방법만 다룰 예정이다. 1. 이미지 다운로드 `docker pull` 명령어로 쉽게 도커 레지스트리에서 엘라스틱서치 이미지를 다운로드 가능하다. 나중에 Spring Data Elasticsearch 4.3 를 통해 실습도..
[리트코드 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..
[자료구조] 그래프(Graph) 이전 포스트의 트리(Tree) 자료 구조는 그래프의 한 종류이다. 하지만 모든 그래프가 트리는 아니다. 그래프(Graph) - 노드와 그 노드를 연결하는 간선(edge)를 하나로 모아 놓은 것이다. - 사이클(cycle)이 존재할 수도 있고 존재하지 않을 수도 있다. 사이클이 없는 그래프를 비순환 그래프(acyclic graph) 라고 부른다. - 방향성이 있을 수도 있고 없을 수도 있다. 그래프 표현 방법 1. 인접 리스트(Adjacency list) - 그래프를 표현할 때 사용되는 가장 일반적인 방법이다. - 아래 그래프를 인접 리스트로 표현하면 다음과 같다. adj[0]: 1 adj[1]: 2 adj[2]: 0, 3 adj[3]: 2 2. 인접 행렬(Adjacency matrix) - N*N boo..
[자료구조] 트리(Tree) 트리와 그래프는 대표적인 *비선형 자료구조 이다. (선형 구조에는 배열, 연결리스트, 스택, 큐 등이 있다.) 트리(Tree) - 노드로 이루어진 자료구조이다. - 사이클(cycle) 이 존재할 수 없다. - 하나의 루트 노드를 가진다. 루트 노드(root node)는 0개 이상의 자식 노드(child node)를 가진다. (반복) - 자식이 없는 노드는 '말단'(= leaf node)이라고 부른다. 트리의 종류 이진 트리(Binary tree) - 각 노드가 최대 2개의 자식을 갖는 트리 이진 탐색 트리(Binary search tree) - 모든 노드가 특정 순서를 가진 이진 트리 (특정 순서 속성은 모든 노드에 대해 반드시 참이여야 한다.) 예) 아래 1번 트리는 '왼쪽 자식 노드
[리트코드 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..

티스토리툴바