TIL(177)
-
(TIL) 20210609
📕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..
2021.06.09 -
(TIL) 20210608
📕Facts(한 것) 알고리즘 복습 운동하기 프로그래머스 문제 풀기 수업듣기 📕Findings(배운 것) 오늘은 퀵정렬과 다이나믹 프로그래밍에 대해서 복습했다. 퀵정렬의 partition과 sort 두 부분으로 나뉜다. (사실상 partition이 전부다) partition은 퀵정렬의 정수인데, 왼쪽에는 pivot보다 작은값을, 오른쪽에는 pivot보다 큰 값을 정렬해준다 그리고 pivot을 작은값과 큰 값 사이에 넣으면 완성이다. 이 partition 알고리즘을 재귀적으로 호출하면 결국 퀵정렬이 된다. 퀵정렬은 평균적으로 O(nlogn)의 시간복잡도를 보장하지만, 최악의 경우에는 O(N^2)의 시간복잡도를 가진다. 최악의 경우는 배열이 모두 같은 수로 이루어진 경우인데, 이를 보완하기 위해서 3-way..
2021.06.08 -
(TIL) 20210607
📕Facts(한 것) 알고리즘 복습 운동하기 프로그래머스 문제 풀기 수업듣기 📕Findings(배운 것) 시간복잡도를 계산하는 여러가지 방법과, 병합정렬에 관해서 공부했다. 알고리즘의 performance를 측정하는 척도는 시간인데, 이 시간을 측정하는 방법이 여러가지가 있다. 대표적으로 수학적으로 계산하며 단순 작업의 양을 나타내는 방법인 Mathematical model과 그래프로 표현하여 performance salce을 나타내는 Asymptotic analysis 방식이 있다. Matehmatical model은 sum of "cost" * "freuqency" 이다. cost 는 variable declaration ,assignment statement, less than compare, eq..
2021.06.07 -
(TIL) 20210606
📕Facts(한 것) 알고리즘 복습 운동하기 📕Findings(배운 것) 학교 알고리즘 시험이 처음부터 끝까지라 강의를 새로 들으면서 빠진 부분은 없는지 다시 보고 있다. 오늘은 선택정렬, 삽입정렬에 대해 복습을 했다. 선택정렬은 N^2/2 만큼 비교하고, N번 데이터를 교환한다.(on average) 데이터 교환 비용은 선형시간 정도라, 빠른 편이지만, 교환비용이 O(n^2)이기 때문에 배열의 길이가 1000을 넘을경우 소요시간이 기하급수적으로 늘어난다. 다만 선택정렬의 장점은 추가공간이 필요하지 않기 떄문에, 메모리에 있어 이점이 있다. 삽입정렬은 N^2/4만큼 비교하고, N^2/4 만큼의 시간이 교환하는데 필요하다. 교환하는 시간이 선택정렬 보다 훨씬 느리지만, 교환하는 데 걸리는 시간이 선택정렬보..
2021.06.06 -
(TIL) 20210605
1.Facts(한 것) 학교 과제 녹음 알고리즘 과제 제출 자료구조 트리, 그래프 포스팅 및 정리 알고리즘 복습 운동하기 2.Findings(배운 것) DFS와 BFS를 트리에서 구현했다. DFS와 BFS를 그래프에서 실행하는 것과 트리에서 실행하는 것에 가장 큰 차이점은 트리에서는 어떤 방향으로 나아갈지 설정을 해줘야하지만 그래프에서는 순서를 정해줄 필요가 없다. 그래프는 인접해 있는 모든 노드를 탐색하기 때문이다. 아래는 트리를 이용한 DFS와 BFS이다. void dfs(vector tree, bool check[]) { stack st; int start = tree[0]; st.push(start); while(!st.empty()) { int cur = st.top(); st.pop(); in..
2021.06.05 -
(TIL) 20210604
1.Facts(한 것) 학교 과제 완성 DFS 재귀, 스택으로 구현하기 다익스트라 C++로 구현하기 Bellman-Ford algorithm 공부 운동하기 2.Findings(배운 것) 다익스트라 알고리즘을 깊이 있게 공부했다. 다익스트라 알고리즘은 간선의 값을 가중해서 최단 경로를 구하는 알고리즘으로 dist[] 배열과, from[]배열을 통해서 시작점 부터 각 노드까지 필요한 비용을 알 수 있음과 동시에 각 노드가 어떤 노드를 거쳐서 왔는지까지 알 수 있다. 다익스트라 알고리즘의 시간복잡도는 O(E*V)이고 바이너리 힙으로 구현할 경우 삽입, 삭제, 키를 업데이트 하는데 비용이 평균적으로 E*logV 만큼 필요하다. DFS를 C++로 재귀적방식, 스택을 이용한 방식 두가지로 구현을 해봤다. 코드는 재..
2021.06.04