본문 바로가기

전체 글

 (11)
[자료구조] 트리(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

티스토리툴바