본문 바로가기

컴퓨터과학

 (6)
자료구조_우선순위 큐 우선순위 큐는 스택과 큐처럼 자료들의 반환 순서가 정해져 있는 자료구조다. 일반적인 큐라면 선입선출의 원리를 따르는 단순한 자료구조로써, 단순히 1차원 배열을 사용해 구현할 수 있었다. 반면에, 우선순위 큐는 어떤 원소가 먼저 들어왔는지보다 각 원소의 우선순위를 더 우선시하여, 우선순위가 더 높은 원소가 먼저 빠져나가게 된다. 우선순위 큐는 기본적으로 이진 트리로 구현할 수가 있다. 이진 트리란, 모든 부모 노드가 자식 노드 최대 2개를 가지는 트리를 말한다. 이때 트리에서 부모가 자식보다 항상 우선순위가 크도록 배열한다. 즉, 루트 노드의 우선순위가 최대가 된다. 이렇게 되면 잘 구성된 이진 트리에서 바로 우선순위가 최대인 원소를 구할 수 있다. 그리고 다음과 같이 우선순위 큐를 일차원 배열로 저장할 ..
플로이드-워셜 알고리즘 증명 * 스스로 증명한 것이라 틀린 부분이 있을 수도 있습니다 플로이드 워셜 알고리즘의 알고리즘을 보면 D는 N*N의 2차원 리스트. 사이에 간선이 있는 두 점 i, j는 D[i][j]에 둘을 간선들 중 최소 길이를 저장. 그렇지 않은 두 점은 D[i][j]에 매우 큰 수(무한에 대응)를 저장 경유점 k를 1부터 N까지: 시작점 i를 1부터 N까지: 도착점 j를 1부터 N까지: D[i][j] = min(D[i][j], D[i][k]+D[k][1]) 과 같다. k가 x일 때(x는 1, 2, ... N) x단계라고 하자. 0단계는 알고리즘을 아예 적용하지 않은 상황으로 하자. 그리고 다음 명제를 P(k)로 두자. k단계까지 알고리즘을 시행했을 때 D[i][j]는 i부터 j까지 1부터 k까지의 경유점만을 사용할 때..
알고리즘_플로이드-워셜 알고리즘 플로이드-워셜 알고리즘(줄여서 플로이드 알고리즘)은 가중치가 있는 그래프에서 모든 정점 간 최단 거리를 구할 수 있는 알고리즘이다. BFS나 나중에 다뤄볼 다익스트라 알고리즘 등은 1회 실행 시 한 점에서 한 점으로 혹은 모든 점으로의 최단 거리만 구할 수 있지만, 플로이드 알고리즘은 단 한 번의 실행으로 모든 점에서 모든 점으로를 구할 수 있다. 플로이드 알고리즘은 기존까지 알려진 최단 경로와 어떤 특정한 점을 '경유점'으로 사용할 때를 비교해 최단 경로를 갱신하는 알고리즘이다. 그 서술은 다음과 같다. 정점이 N개인 그래프에서, N*N인 2차원 리스트를 만든 후, 각 점 (i, j)에는 i번째 정점에서 j번째 정점으로 가는 간선의 길이(초기 최단경로)를 저장한다. 간선이 없으면 INF(무한대)를 입력..
군론 공부 5_ 준동형사상의 기본 정리 1. 사상 '사상'이란 두 집합의 원소들을 특정한 함수로 서로 대응시키는 것을 의미한다. 예를 들어 {1, 2, 3}에서 함수 (홀수)$\to$1 (짝수)$\to$0 를 이용해 {0, 1}을 만드는 것은 {1, 2, 3}에서 {0, 1}로의 사상이 된다. 2. 준동형사상 군과 군 사이에도 역시나 사상을 취할 수 있다. 이때 '준동형사상'이라는 특별한 사상을 만드는 것도 가능하다. 두 군 G, H에 대하여 f: G$\to$H가 아래 조건을 만족할 때 f를 준동형사상이라고 한다. G의 임의의 원소 x, y에 대해 f(xy) = f(x)f(y) (단, 좌변은 G의 연산으로 xy를, 우변은 H의 연산으로 f(x)f(y)를 계산) 그리고 f가 G에서 H로의 전사함수, 즉 H의 모든 원소들에 대해 각 원소를 f(x..
알고리즘_BFS(너비우선탐색) 대표적인 두 가지 그래프 탐색 알고리즘 중 하나인 BFS에 대해서 알아보자. (나머지 하나인 DFS는 여기서 확인할 수 있다.) BFS는 한 정점으로부터 시작해 '넓게 퍼져가며' 그래프를 탐색하는 이미지다. 조금 더 명확하게는, 한 정점과 직접적으로 연결된 모든 정점을 탐색한 뒤 방금 탐색한 정점들과 연결된 다른 정점들을 탐색하면서 연쇄적으로 탐색이 일어나는 방식이다. BFS의 과정을 아래처럼 그래프로 보면 한 점에서부터 시작해 간선 하나로 연결된 인근한 정점, 그다음은 간선 두개로 연결된 정점들로 탐색 대상이 점점 퍼져나가는 형태가 된다. 시작점과 연결된 두 정점을 먼저 탐색한다. 그다음은 방금 탐색한 두 점과 연결된 다섯 개의 점을 탐색한다. 그다음은 다섯 점 중 2번째 점과 연결된 나머지 한 점을 ..
알고리즘_DFS(깊이우선탐색) DFS(깊이우선탐색)는 BFS와 함께 대표적으로 사용되는 그래프 탐색 알고리즘 중 하나다. DFS의 탐색 과정은 한마디로 표현하자면 '끝까지 파고들기'다. 한 정점을 시작으로 하여, 현재 있는 정점과 연결되어 있는 방문하지 않은 정점 중 하나에 들어가며 경로를 탐색하는 과정을 막다른 점에 도달할 때까지 반복하는 것이다. 막다른 점에 도달하면 왔던 경로를 다시 되짚어가다, 이동할 수 있는 정점이 발견되면 다시 탐색 과정을 반복한다. 조금 추상적으로 표현하면, 시작점을 표현하는 그래프의 각 '줄기'(경로)들을 순차적으로 내려가면서 특정한 점 등을 찾는 알고리즘이다. 이 과정을 그래프로 시각적으로 확인해보자. 시작 갈 수 있는 점이 여러 개 있는 상황에서, "왼쪽 점부터 방문하기"로 규칙을 정하자. 시작 내려..

티스토리툴바