본문 바로가기

분류 전체보기74

[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.

Kruskal / Prim Algorithm (크루스칼 / 프림 알고리즘) https://www.youtube.com/watch?v=LQ3JHknGy8c : MST 개념과 크루스칼 알고리즘 설명 (유투버 동빈나) https://www.youtube.com/watch?v=AMByrd53PHM : 크루스칼에 사용되는 union-find 알고리즘 설명 (유투버 동빈나) https://www.youtube.com/watch?v=71UQH7Pr9kU : 크루스칼 2분짜리 영상 https://www.youtube.com/watch?v=cplfcGZmX7I : 프림 2분짜리 영상 https://stackoverflow.com/questions/1195872/when-should-i-use-kruskal-as-opposed-to-prim-and-vice-versa When should I u.. 2020. 6. 2.

이전 1 ··· 6 7 8 9 10 11 12 ··· 19 다음

티스토리툴바