📕Facts(한 것) 알고리즘 복습 프로그래머스 문제 풀기 수업듣기 자료구조, 알고리즘 포스팅(DP, radixsort, graph, MST) 📕Findings(배운 것) 기수정렬에서 LSD 정렬의 시간복잡도는 O(dN)이고 MSD 정렬의 경우 최선은 O(2N), 최악은 O(2dN)이다. 다익스트라는 그리디 알고리즘의 일종이지만 bellman-ford는 모든 경로를 탐색하는 알고리즘이다. 당연히 bellman-ford 알고리즘이 시간이 평균적으로 더 소요되고, 다익스트라의 시간복잡도는 이진 힙 구조로 구현하는 경우O(E * logV), 배열로 구현하는 경우 V^2이며 bellman-ford의 경우 시간복잡도는 O(E*V)이다. 크루스칼 알고리즘의 시간복잡도는 O(E logE)이고 프림 알고리즘의 시간복잡..

📕Facts(한 것) 알고리즘 복습 프로그래머스 문제 풀기 수업듣기 학교 과제 자료구조, 알고리즘 포스팅 📕Findings(배운 것) 그리디 알고리즘, huffman code, backtracking에 관해 블로그에 포스팅을 하면서 새로운 사실 몇가지를 알게 되었다. huffman code에서 트리를 구성할때 값을 Queue에서 꺼내서 트리를 구성하는데 그때의 queue는 min_heap 구조의 우선순위 큐이다. dp와 그리디의 구분은 bottom-up 과 top-down 방식으로 구분하는 것이 아니라 subproblem에 의존성이 있냐 없냐로 구분한다. 📕Feeling(느낀 점) 알고리즘 포스팅은 생각한 것 보다 시간이 많이 걸렸다. 공부를 다시 함과 동시에 정보전달을 위해서 내 생각을 글로 표현해야 ..

📕Facts(한 것) 알고리즘 복습 프로그래머스 문제 풀기 수업듣기 학교 과제 📕Findings(배운 것) huffman code관련해서 복습을 진행했다. 복습을 하던 도중 heap관련 내용이 나왔는데, 공부도 너무 지겨워서 프로그래머스 heap관련 문제를 풀었다. '더 맵게' 라는 문제인데, 우선순위큐를 이용해서 풀 수 있다. 우선순위 큐에 대해서 간략히 얘기하자면, 우선순위 큐는 힙의 성질과 큐의 성질을 합쳐놓았다고 보면 된다. 힙에는 max heap과 min heap 두 종류가 있다. max heap은 트리 가장 상단의 노드가 즉, 루트노드가 그 트리에서 가장 큰 값이고 부모 노드의 자식 노드는 부모 노드보다 작아야 한다. min heap은 정반대이다. 가장 산단의 노드가 그 트리에서 가장 작은 값..

📕Facts(한 것) 알고리즘 복습 프로그래머스 문제 풀기 수업듣기 학교 과제 📕Findings(배운 것) 그리디 알고리즘을 복습하면서 어제 풀다만 프로그래머스 문제가 생각나서 다시 시도해봤다. 큰 수 만들기라는 문제인데, 첫번째 시도는 문자열을 오름차순으로 정렬한 후 인덱스 0부터 k까지 큐에 저장한 후 원래 문자열에서 빼는 방식이었다. 이런 방식은 테스트 케이스 1, 2번은 통과하지만 3번 케이스는 통과하지 못하는데, 작은 수를 빼내어도 가장 큰 수가 되지 못했기 때문이었다. 두번째 시도는 C++ string 라이브러리 메서드인 str.erase()를 활용한 풀이방법이었다. 문자열 인덱스 i와 i+1을 비교한 후, i가 더 작다면 i를 erase()함수를 통해서 지우는 방식이다. 이러한 방식은 테스트..

📕Facts(한 것) 알고리즘 복습(DP, Floyd) 프로그래머스 문제 풀기 수업듣기 학교 과제 📕Findings(배운 것) knapsack problem(배낭문제) 을 다이나믹 프로그래밍을 통해 구현했다. 보통 knapsack problem은 그리디 알고리즘을 통해 나오는 문제들이 많지만 큰 무게가 작은 무게의 배수가 아니거나, 그 수량이 1개로 한정되어 있을때는 그리디 알고리즘 적용이 불가능하다. 그렇기 때문에 recursion + memoization 방식인 DP로 푸는게 적합하다. 이 문제를 DP로 풀 경우, 시간복잡도는 O(N*W) (w는 weight)이다. Floyd 알고리즘의 기본적인 개념을 이러하다 "If V(k)is a node on an optimal path from Vi to Vj..

📕Facts(한 것) 알고리즘 복습 프로그래머스 문제 풀기 수업듣기 📕Findings(배운 것) 실시간 수업이 있는 날이어서 알고리즘 공부에 쏟을 시간이 많지 않았다. 간단히 DP를 공부하고 프로그래머스 문제를 몇개 풀었다. 프로그래머스에서 N개의 최소공배수라는 문제를 풀면서 C++ 내장 lcm 함수를 사용했다. 다른 언어에서는 최대공약수를 반환해주는 gcd함수가 일찍이 있던걸로 알고 있다. 하지만 C++은 한발 늦게 C++17에서야 gcd, lcm 함수가 추가되었다. #include #include #include using namespace std; int solution(vector arr) { int answer = 0; answer = arr[0]; for(int i = 1; i < arr.si..