본문 바로가기

ComputerScience

 (48)
function procedure Terminology $ra Register Memory 중에 $ra라는 것이 있는데, 이는 return address의 약자로, 특정 함수가 끝나고 이동할 메모리 주소를 저장해 둔다. PC (Program Counter) 현재 실행하고 있는 명령어의 메모리 주소를 가지고 있는 메모리 주소를 의미한다. Leaf Procedure 함수 내에서다른 함수를 호출하지 않는 경우를Leaf Procedure라고 한다. 이제 함수의 실행 순서를 알아보자. 컴퓨터가 함수를 실행하는 과정은 아래와 같다. (엄청 길다 ㅠㅠ) Proceudre caller place argument in register where callee can access : $a0-$a3 Caller가 전달 인자를 Register에 넣는다 PC를 ..
[Stack] 계산기구현 중위표기법 : 수식 내에 연산의 순서에 대한 정보가 없음. 따라서 소괄호와 연산자의 우선순위를 정하여 이를 기반으로 연산 순서 명시 후위표기법이 컴퓨터 입장에서 처리하기 더 쉽다. 따라서 중위표기법을 후위 표기법으로 바꾸는 예제를 생각해보자. 이 때 몇가지 규칙들을 알아보자, 피연산자는 바로 출력한다. 연산자의 우선순위는곱하기,나누기 > 덧셈, 뺄셈 > '(' 이다. 연산자는 스택에 넣는다. 스택의 마지막 원소가 현재 push 하려는 원소보다 우선순위가 높거나 낮다면 Pop한다 ')' 를 만났을 경우 스택에서 '(' 를 Pop 할 때까지 계속 Pop한다. 다음은 C언어로 윤성우 님의 열혈 자료구조를 참고해서 만든 계산기 코드이다. #include #include "Stack.h" #include #inc..
Huffman Coding 문자를 인코딩할 때, 고정된 길이로 압축하는 것보다 가변길이를 선택하는 것이 좋다. 많이 등장하는 문자는 짧게, 적게 등장하는 문자는 길게 인코딩하면 압축률이 좋아질 것이다. 하지만 가변길이를 선택할 경우, 디코딩 할 때, 문제가 없도록 인코딩 규칙을 짜야된다. 즉, 어떤 인코딩된 코드도 다른 인코딩된 코드의 prefix가 되면 안된다. 1. Huffman Encoding huffman coding은 가장 작은 frequency의 문자들을 합쳐가면서 이진트리를 만드는 방식이다. huffman coding 방식에 따르면 가장 압축률이 좋은 인코딩 방식을 얻을 수 있다. 수학적 귀납법에 의해 증명이 가능하다. Proof) 2. Run Length Encoding AAABBAA => 3A2B2A 로 인코딩된다..
floyd-warshall algorithm Floyd-Warshall 알고리즘은 all-to-all 알고리즘이다. 이전의 djikstra 알고리즘 같은 경우 one-to-one인 알고리즘이다. Notation d_k[i,j] : i 에서 j까지 {1,2,...,k}까지의 노드들만 지나서 가는 경로 d_0[i,j] = 0 if w[i,j] doesn't exist d_n[i,j] = 최단경로 ( 중간에 어떤 노드를 지나도 상관 없으므로) d_k[i,j] = min(d_k-1[i,j],d_k-1[i,k]+d_k-1[k,j])
dijkstra 알고리즘 최단경로를 찾는 알고리즘이다. 가정 1. 음수 가중치가 존재하지 않는다 2. 시작점 s로부터 최단 경로를 알아낸 노드들의 집합을 S 3. S에 속하지 않는 노드들 u에 대해, d[u]는 S의 노드들을 거쳐 u까지 오는 경로 중 최단 경로이다. Theorem. U에 속하는 모든 노드들 중 d[u]가 노드 u에 대해, d[u]는 s에서 u까지의 최단 경로이다. Proof) s에서 u까지 다른 최단 경로가 존재한다고 하자. 이 때, 가정 3에 의해, S에 속하지 않는 점 v를 지나게되는데, d[u] = d[v] + u(v,w)가 된다. 하지만 d[u]
최단경로 알고리즘 A . 최단경로 알고리즘의 특성을 정리해보면 1. 최단경로의 부분 경로는 부분경로에 해당하는 노드 간의 최단경로가 된다. 2. 최단 경로의 경우, 사이클이 존재하지 않는다. B. 최단 경로 알고리즘 Notation d[v] : start node에서 노드 v까지 최단 경로 estimate pi[v] : v까지의 최단경로 중 v의 직전 노드 C. Relaxation def relax(u,v,w): if d[v]>d[u]+w: d[v]=d[u]+v pi[v]=u D. Generic Algorithm 최단경로 알고리즘 문제는 , 노드와 에지들에 대해 어떤 순서로 얼마나 relaxation을 할 것이냐의 문제이다. E. Bellman-Ford Algorithm 최단 경로의 최대 에지 갯수는 n-1개 이므로 모든..
[javascript] MST-Kruskal 알고리즘 Minimum Spanning Tree를 구현하는 대표적인 방법 중 하나는 Kruskal 알고리즘이다. Def : Generic MST 어떤 mst의 부분집합 A에 대해서 A 합집합 Edge(u,v) 도 역시 어떤 MST의 부분집합이 될 경우, Edge(u,v)를 안전하다고 한다. A를 공집합에서 시작하여, 안전한 에지를 A의 원소의 갯수가 n-1이 될 때까지 반복한다. Th1 : A가 어떤 MST의 부분집합이고, (S,V-S)가 A를 Respect하는 컷 일 때, 이 컷을 Cross하는 에지들 중 가장 작은 가중치의 Edge(u,v)는 A에 대해서 안젆다. 밑에 Kruskal 알고리즘을 설명하며 이를 증명하였다. Kruskal Algorithm kruskal 알고리즘은 최소 가중치 순서대로 선택을 한다..
그래프 그래프 구현방법 1. 인접 행렬 - 인접 노드 탐색 시간 복잡도 : O(N) -> 한 행을 다 검색해야 한다 - 에지 탐색 시간 복잡도 : O(1) 2. 연결리스트 - 인접 노드 탐색 시간 복잡도 : O(degree(node)) - 에지 탐색 시간복잡도 : O(degree(node)) 위상정렬의 두가지 방법 1. indegree가 0인 애들을 찾는다. 그리고 outdegree 에지를 제거한 후 이 작업을 반복하면서 연결리스트 뒤에 추가한다. 2. DFS를 이용해 leaf child에 도달했을 때, leaf child를 제거하고 연결리스트 앞에 추가한다..

티스토리툴바