일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
- class_template
- 13305
- 구현
- 총정리
- 문법
- Pair
- data_structure
- sort
- connected_component
- c++
- template
- 예제
- red-black tree
- Critical_Path_Analysis
- 백준
- STL
- Heap
- qsort
- Biconnected_Component
- Articulation_Point
- '0'
- singly Linked List
- deletion
- 자료구조
- Algorithm
- function_template
- 알고리즘
- sstream
- list
- 5397
- Today
- Total
- Today
- Total
- 방명록
목록전체 글 (85)
어제의 나보다 성장한 오늘의 나
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/1Axly/btrDgO82WGA/PsYsI11KReDVIDzgZZKD8k/img.png)
오늘은 Radix sort 에 대해서 알아보려고 한다. Radix sort란? 낮은 자리 수부터 정렬하여 숫자들을 빠르게 정렬할 수 있는 sort 방식이다. 장점 ◎ Stable sort ◎ θ(n) 까지 가능 ◎ LSD sort 배경 지식 LSD , MSD LSD : Least Significant Digit 의 약자로 낮은 자릿수를 뜻한다. MSD : Most Significant Digit 의 약자로 높은 자릿수를 뜻한다. 52,314 를 예로 들면 가장 중요한 숫자는 10,000의 자리에 있는 5 이다. 그리고 가장 덜 중요한 숫자는 1의 자리에 있는 4이다. 즉 , LSD sort는 낮은 자리 부터 정렬을 하겠다는 것이고, MSD sort는 높은 자리 부터 정렬을 하겠다는 것이다. Radix s..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/0y15o/btrDcsGpWrS/zK4yKGWbl63LFbsm2pF9G0/img.jpg)
오늘은 counting sort( 계수 정렬 )에 대해서 알아보려고 한다. Counting sort는 다른 sort들에 비해 조건들이 추가적으로 더 있다. 그럼에도 불구하고 사용하는 이유는 조건들을 충족시키면 무려 θ(n)까지 가능 하다. 특징 ◎ Stable sort ◎ Not Sort-In-Place ※ stable sort : 중복된 값을 가지는 원소들끼리의 순서가 sort 전/후로 바뀌지 않는 sorting ※ Sort-In-Place : 추가적인 메모리(추가 array) 없이 원소들이 담겨 있는 array에서 sorting 이 일어남 시간 복잡도 θ( n + k ) n : 원소의 개수 k : 원소 들의 값의 범위 ( 만약 원소의 최대 값이 6 이라면 k는 6이고 원소들은 0~6 사이의 값을 가진..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/dnMv3d/btrCv0bS4vY/D7Y2OEAeKGQxqo9anbfZx1/img.png)
오늘은 Minimum spanning tree(MST)에 대해 알아보고 Graph에서 MST를 찾아내는 알고리즘 두 가지 (kruskal's algorithm , Prim's algorithm)에 대해서 알아 보자. MST란? Minimum : edge들의 weight의 총합이 가장 작다. Spanning : 모든 vertex들을 포함 한다. Tree : Cycle 이 없고 edge의 갯수가 vertex의 갯수-1 개 인 그래프. 이 세 가지 조건을 가진 것이 MST이다. 참고로 MST는 undirected graph에서만 정의 된다. 예를 들어 위와 같은 그래프가 있다고 했을 때 이 것의 MST는 아래와 같다. 확인해보자 edge들의 weight 총 합이 가장 작고, 모든 vertex들을 포함 하고, ..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/oltOW/btrCcDHxQSx/XUgoybqLTFSgJc8B5Cb5J0/img.png)
이번 포스팅에서는 자료 구조 Graph를 이용 하여 Shortest Path를 찾는 방법에 대해서 알아 보려고 한다. Shortest Path 의 특성들 ◎ shorest path는 shorest subpaths 들로 구성되어 있다. (optimal substructure) ◎ cycle을 포함 하지 않는다. 크게 Single-source shortest path 와 All-pairs shortest-paths 로 나누었다. single-source shortest path : 주어진 source vertex에서 Graph 내의 모든 vertex 까지의 가장 가까운 거리 All-pairs shortest-paths : 모든 vertex u에 대하여 u 에서 v로 가는 shortest path Single..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/DLk5s/btrB6jv6Dnc/NTF0uabwrs5M3NYZf3Lu80/img.png)
오늘은 DFS의 응용 사례들에 대해서 알아보자 그 전에 DFS에 대해서 잘 모른다면 아래 포스터를 참고하면 DFS에 대해 배울 수 있다. 2022.05.15 - [Algorithm_Analysis] - [Algorithm] BFS 와 DFS [Algorithm] BFS 와 DFS BFS 와 DFS 용어 Discover : Vertex를 처음 방문했을 때 vertex를 discover 했다고 함 Explore : edge를 처음 방문했을 때 Finish : 자신의 노드 뿐만 아니라 연결된 노드들 모두 discovered 되었을 때 그 노드는.. 8156217.tistory.com DFS의 응용 사례 ◎ Topological sort ◎ Finding connected component(undirected)..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/bwzLzK/btrB8W2bveM/al9nGJp4v1ypozkVWNHy41/img.png)
BFS 와 DFS 용어 Discover : Vertex를 처음 방문했을 때 vertex를 discover 했다고 함 Explore : edge를 처음 방문했을 때 Finish : 자신의 노드 뿐만 아니라 연결된 노드들 모두 discovered 되었을 때 그 노드는 Finish 되었다고 함 discover time : discover 한 시간 finish time : finish한 시간 discover 되기 이전의 vertex 색깔 - 흰색 discover 되었지만 연결 되어있는 vertex 중에 discover가 안된 vertex가 있는 경우 - 회색. discover 되었고 finish 되었을 경우 – 검정색 위의 색깔로 discover or finish 되었는지 나타내어 과정을 가시화 한다. BFS ..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/crl0Tb/btrCcFkxCdy/bkPmiSUaJqKUDvnD9Kt5o0/img.png)
Graph 란 ◎ vertex와 edge로 구성된 한정된 자료구조를 의미 용어 정리 Value를 가지는 동그라미 부분 : Vertex or Node vertex들을 이어 주는 부분 : Edge Degeree of a vertex : 특정 vertex와 연결 되어 있는 vertex의 개수 Directed graph : edge에 방향이 있는 그래프. Undirected graph : edge에 방향이 없는 그래프 Weighted graph : edge에 weight가 주어진 그래프 Not Weighted graph : edge에 weight가 주어지지 않은 그래프 Directed 에서 시작하는 부분 : head Directed 에서 타겟이 되는 부분 : tail Symmetric digraph Symmet..
◎ 리눅스 명령어는 여기저기 정말 많이 사용되기 때문에 잘 알아두어야 한다. ◎ 많이 사용되는 명령어 위주로 정리해 보았다. ① pwd : 현재 작업중인 디렉토리를 출력한다. $ pwd /home/inhyuk13/바탕화면 ② cd : 작업중인 디렉토리 이동 $ cd .. // 상위 디렉토리로 이동 $ pwd /home/inhyuk13 $ cd - // 이전 디렉토리로 이동. $ pwd /home/inhyuk13/바탕화면 $ cd test/test2 // 여러 디렉토리 이동. '/' 사용 $ pwd /home/inhyuk13/바탕화면/test/test2 $ cd ~ or $ cd // home 디렉토리로 이동. $pwd /home/inhyuk13 ③ ls : 디렉토리 목록 확인 $ ls// 현재 디렉토리 ..