본문 바로가기

Problem Solving/Algorithm, Tips9

Trie (Prefix tree) 개념 n-ary tree의 변종으로 각 노드에 문자를 저장하는 자료구조이다. 트리를 아래쪽으로 순회하면 단어 하나가 나온다. * 노드 * 노드는 널 노드라고도 불리며 단어의 끝을 나타낸다. TrieNode를 상속한 TerminatingTrieNode로 표현할 수도 있고 * 노드의 부모 노드 안에 boolean flag를 새로 정의해 단어의 끝을 표현할 수도 있다. 자식 노드 개수 * 노드로 단어의 끝을 표현하면 각 노드는 1개 ~ (ALPHABET_SIZE + 1)개까지 자식을 갖고 있을 수 있다. 단 * 노드 대신 boolean flag로 표현했다면 0개 ~ ALPHABET_SIZE개까지. 활용 접두사를 빠르게 찾아보기 위해 모든 문자열을 트라이에 저장해놓을 수 있다. 해시테이블을 이용하면 주어진 문자.. 2020. 6. 29.

[Leetcode] Min Stack 155. Min Stack 문제 요약: push(), pop(), top(), getMin()을 지원하는 스택을 디자인하라. getMin()은 스택 내 최소 원소를 반환하며 상수 시간에 완료되어야 한다. 생각 1: getMin()을 상수 시간에 하는 것이 포인트. push() 할 때마다 min을 업데이트 하는 것은 어렵지 않지만, min이 pop() 될 경우 직전의 min 값으로 roll back 해야한다. 하지만 직전의 min 값을 다 저장해둘 수가 없으므로 (벡터를 이용해 저장해둘 수는 있겠지만 의미가 없다고 생각했음) 그냥 벡터 하나와 셋 하나를 이용해 해결해야겠다고 생각했다. 생각 2: 벡터 하나와 셋 하나를 모두 쓰는 게 비효율적이라는 생각이 들어서 아래와 같은 struct Node를 만들고 s.. 2020. 6. 28.

다이나믹 프로그래밍 다이나믹 프로그래밍은 1) 큰 문제를 작은 문제로 나눌 수 있고 2) 작은 문제의 답이 큰 문제에서도 동일할 때 하나의 문제는 한 번만 풀도록 Memoization 하는 알고리즘이다. 가령 피보나치 수열을 구할 때 fib(15)를 구하려면 fib(14) + fib(13)을 구해야 하는데, 위 그림처럼 동일한 계산을 매우 여러 번 해야 함을 알 수 있다. 따라서 한 번 계산한 값을 배열에 memo 해 두고, 배열에 memo 해 둔 값이 있다면 그것을 반환하고 값이 없다면 (처음 계산하는 것이므로) 계산하고 memo 하면 된다. 출처는 사진 아래 링크 2020. 6. 24.

최대 연속 부분 수열의 합 (아래 쪽에 update 있음) 왜 이 문제는 볼 때마다 새로운걸까? 이 영상만 네 다섯 번은 본 것 같다. 컨셉은: "수의 합을 반복적으로 구하는데, 합이 음수면 0으로 초기화하고 다음 수부터 다시 시작한다." 합이 음수일 때 0으로 초기화하는 것은, 전체 배열 중 양수 최소 하나 이상 있다고 가정하기 때문이다. 양수가 최소 하나 이상 있다면 그 양수 하나만 가지는 게 (음수 합보다) 이득이다. 그래서 또 이 알고리즘에 빈틈이 생기는데, 배열의 모든 수가 음수인 경우에 0을 반환하게 된다는 것이다. 그래서 이 경우는 배열에 있는 수 중 가장 큰 (음)수를 반환한다. 물론 0을 반환할 때 항상 배열의 모든 수가 음수인 것은 아니다. 배열의 모든 수가 0일 때, 혹은 0과 음수로만 이루어진 경우에도 0을 .. 2020. 6. 23.

이전 1 2 3 다음

티스토리툴바