어제의 나보다 성장한 오늘의 나

Peterson’s Solution 두 개 이상의 프로세스의 동기화(Synchronization) 문제를 해결하는 방법 중 하나 ※ Critical-section problem 의 예전 버전 해결 방법이다. 예전 버전이므로 현대 버전에 적용되는 것이 보장 되지 않지만 알고리즘 자체가 동기화 문제 해결 방법 들의 기반이 된다. Peterson’s Solution Code variables int turn; boolean flag[2]; Turn 은 critical section에 들어갈 수 있는 프로세스를 나타내는 변수 Flag 는 critical section에 들어갈 준비 상태를 나타내는 변수 Algorithm // P_i 프로세스 의 알고리즘 while (true) { flag[i] = true; t..

오늘은 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..

오늘은 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 사이의 값을 가진..

오늘은 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들을 포함 하고, ..

이번 포스팅에서는 자료 구조 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..

오늘은 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)..

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

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