본문 바로가기

전체 글72

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

Dijkstra Algorithm (다익스트라 알고리즘) https://www.youtube.com/watch?v=_lHSawdgXpI : 직관적 이해 도와주는 3분짜리 영상 https://code.google.com/archive/p/eclipselu/downloads : algorithm.pdf의 Dijkstra algorithm 부분 (Pseudocode 출처) 아래 그림의 파란색 한글 글씨 출처는 나 Pseudocode 이 수도코드에서는 dist가 업데이트될 때마다 priority queue H에 push 해주는 것이 아니라, 처음부터 H에 모든 원소에 대한 정보를 넣어주고 dist가 업데이트되면 H에도 그를 알린다는 컨셉이다. 이미 방문한 노드는 H에서 사라지므르 unvisited 라는 셋을 사용할 필요가 없는 것이다. 하지만 실제 구현할 때 dist.. 2020. 6. 2.

범위 기반 포문 (Range-based for loop) for(auto elem: arr) // arr의 요소가 elem에 복사 for(auto& elem: arr) // arr의 요소의 참조 (값 변경 가능) [권장] for(const auto& elem: arr) // 읽기 전용 + 참조 [권장] 배열, vector, deque, list, set, map에 모두 사용 가능 https://boycoding.tistory.com/210 C++ 07.18 - 범위 기반 for 문 (range-based for statement) 범위 기반 for 문 (range-based for statement) '06.06 - for 문' 포스트에서 for 문을 사용하여 배열의 각 요소를 반복하는 예제를 봤다. #include int main.. 2020. 6. 1.

이전 1 ··· 3 4 5 6 7 8 9 ··· 12 다음

티스토리툴바