Blog Content

다익스트라 알고리즘은 최단 경로 알고리즘 중의 하나입니다.그래프의 어느 정점 하나를 시작으로 하고,나머지 정점들로의 최단 거리를 모두 구합니다. 다익스트라 알고리즘이 작동하는 방식은 다음과 같습니다.1. 아직 방문하지 않은 정점들 중 거리가 가장 짧은 정점을 하나 선택해 방문한다.2. 해당 정점에서 인접하고, 아직 방문하지 않은 정점들의 거리를 갱신한다. 거리 dist[] 배열을 하나 생성하여 초기값을 셋팅해 줄건데1번 정점이 시작점이라고 했을때, 자기 자신까지의 거리는 0이기 때문에시작점으로의 거리만 0으로 셋팅해주고, 나머지는 무한으로 초기값을 셋팅해줍니다. 이렇게 반복해서 동작하고, 끝나고 나면 각 dist 배열에 있는 값이, 각 정점으로까지의 실제 최단경로가 됩니다. 문제가 될 부분은 아직 방문하..

문제 : https://www.acmicpc.net/problem/9466 문제문제는 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께 하고 싶은 학생들을 선택하는데어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 문제이다. 풀이이 문제는 DFS를 활용하여 Cycle을 이루는지 확인하는 방법으로 문제를 풀 수 있다.DFS를 하다가, 싸이클이 발생하는 조건을 찾을 수 있다.정점 방문을 시작했는지 체크하는 visited 배열,그 정점의 방문함수가 완전히 끝났는지를 체크하는 finished 배열이 필요햐다. 다음에 방문할 정점을 k라고 했을때, visited[k] = true, finished[k] = false인 경우이다.예를들어 1->2->3->1 이 싸이클을 이룬다고 가정해보자.1번 정..

깊이 우선 탐색 (Depth First Search)- 방문한 적이 없는 정점 중, 갈 수 있는 곳부터 먼저 찾아가는 탐색 방법입니다. 한 우물만 판다고 생각하면 됩니다.- 스택구조를 사용하여 구현합니다.- 도착 지점이 깊은 단계에 있는 경우 효율적입니다.- 방문 순서를 활용한 자료구조 및 응용이 가능합니다. (위상정렬 등)- 얻어진 결과가 최단거리라는 보장을 하기 힘듭니다.- 해가 없는 경로에 빠질 가능성이 높습니다. 너비 우선 탐색 (Breadth First Search)- 방문할 수 있는 노드들을 큐에 넣고 큐에서 pop하는 순서대로 탐색합니다.- 큐로 구현합니다.- 초기 정점으로부터 거리순으로 정점들을 방문합니다.- 해를 찾게 되면 반드시 최단경로임이 보장됩니다. 그럼, 문제를 풀어보면서 이해해봅..

문제 : https://www.acmicpc.net/problem/2042 N개의 주어진 수가 빈번히 변경이 일어날 때, 중간에 어떤 구간에 대해 합을 구하는 문제이다.구간에 대해 합, 최소, 최대를 해결하는 자료구조는- Segment Tree- Interval Tree- Indexed Tree가 있는데, 그 중 Binary Indexed Tree를 사용하여 문제를 풀도록 하겠다. 문제풀이1. 트리구성하기 1) 2의 n제곱으로 Tree를 구성해야 하므로, 실제 트리 개수를 구한다. 2) 트리의 맨 아래 노드, 위쪽 노드를 채운다.노드의 index가 i일때, 부모 노드의 번호는 i/2, 왼쪽 자식의 노드 번호는 i*2, 오른쪽 자식의 노드 번호는 i*2+1 이다.이 성질을 이용하여 tree의 값을 채운다...

문제 : https://www.acmicpc.net/problem/2696 홀수번째 수를 읽을 때마다 지금까지 입력받은 수의 중앙값을 구하는 문제이다.이 문제는 Heap을 이용하여 풀 수 있다.Heap은 수를 담는 자료구조로, Java에서는 우선순위큐(PriorityQueue)로 구현할 수 있다.Heap은 완전이진트리이며, 모든 정점은 자신의 자식보다 우선순위가 높다는 것이 중요한 성질 중 하나이다. Top이 최대값인 우선순위큐를 최대힙(MaxHeap)Top이 최소값인 우선순위큐를 최소힙(MinHeap) 이라고 한다.따라서, MaxHeap은 담긴 수 중 최대값을 바로 알 수 있고 최대값을 pop할 수 있다.또한 MinHeap은 담긴 수 중 최소값을 바로 알 수 있고 최소값을 pop할 수 있다. Prior..

문제KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다. 예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모든 탑에서는 주어진 탑 순서의 반대 방향(왼쪽 방향)으로 동시에 레이저 신호를 발사한다고 하자. 그러면, 높이가..

Find 연산 어떤 정점의 루트를 찾아주는 연산입니다.자신이 루트라면 자신을 리턴합니다. 아래의 코드를 봅시다. 자신의 부모를 가르키는 배열이 par 이라고 정의했을 때,자신이 루트이면 자신을 리턴하고그렇지 않으면 재귀함수로 경로의 모든 노드의 부모를 루트로 재설정 해줍니다. Union 연산두 집합을 하나로 합쳐주는 연산입니다.들어온 인자들의 루트를 찾아서 비교한 다음루트가 다르면 둘 중 하나의 루트를 다른 하나의 루트의 자식이 되도록 변경합니다.그렇지 않으면 (루트가 같으면) 그냥 return하여 종료시킵니다. 요약하면,find(i) 는 i번의 루트를 찾는다는 연산이고union(a,b) 는 a와 b를 합치겠다는 연산입니다.

Stack과 Queue개념Stack과 Queue는 List보다 좀 더 제한된 Data Structure입니다.Element가 List처럼 순차적으로 배열되지만,추가 및 삭제시 컬렉션의 끝에서만 실행할 수 있습니다.아래 그림을 보고 좀더 구체적으로 알아봅시다. Stack은 LIFO (Last in, First out) 구조로서,엘리먼트가 추가될 때 stack에 쌓이고, 꺼내 쓸때는 위에서부터 꺼내쓰기 때문에마지막에 들어갔던 엘리먼트가 처음으로 꺼내지는 구조입니다. 반대로 Queue는 FIFO (First Out, First In) 구조로서,엘리먼트가 컬랙션의 끝(꼬리)에 하나씩 추가되고,꺼내질때는 컬랙션의 다른 끝(머리)에서 제거되므로처음에 들어갔던 엘리먼트가 처음으로 꺼내지는 구조입니다. Java에서의 ..

자료구조를 공부하다가, 아는 내용인데 자꾸 정리가 안되어서생활코딩 및 여러 블로그를 참조하여 공부한 것을 정리해보았습니다. 배열과 리스트의 개념배열 : 일렬로 늘어선 같은 종류의 자료 여러개를 저장하기 위한 가장 기초적인 자료구조리스트 : 배열의 단점을 보완하여, 빈틈없는 데이터 적재의 장점을 취한 자료구조 배열과 리스트의 특징배열 - 인덱스가 있어, 이를 이용해 데이터를 빠르게 조회할 수 있다.- 메모리 낭비를 초래함. 어떤 엘리먼트가 삭제되면 그 공간을 빈 공간으로 두어야 함.- 따라서 배열 내에 데이터의 여부도 함께 체크해야할 필요가 있음. 리스트- 리스트에서는 인덱스가 중요하지 않음. 핵심은 바로 엘리먼트들간의 순서임.- 즉 순서가 있는 데이터의 모임이 리스트라고 할 수 있음.- 또한 빈 엘리먼트..