본문 바로가기
반응형

Programando/Algorithm

Programando/Algorithm 2021. 9. 24.
최단경로 / 다익스트라(Dijkstra) : 하나의 시작 정점으로부터 모든 다른 정점까지의 음의 가중치가 없을 때에 최단경로를 찾는 알고리즘 다익스트라 구현하기 최단 거리 저장 배열 : distance - 각 노드까지의 최단거리가 저장되며, 처음에는 MAX_VALUE로 초기화한다. 방문 확인 배열 : check - 각 노드에 방문했는지를 확인한다. 다익스트라 알고리즘 순서 distance 배열을 MAX_VALUE로 초기화한다. 시작노드의 거리는 0으로 표시하고, 시작노드의 check 값을 true로 바꿔준다. 시작노드와 연결되어 있는 노드들의 distance 값을 갱신한다. 방문하지 않은 노드 중 distance 값이 최소인 min_node를 찾는다. min_node의 check 값을 true로 바꾸고, min_node와 연결된, 방문하지 않은..
Programando/Algorithm 2021. 8. 8.
힙(Heap) : 완전이진트리의 일종으로, 부모노드와 자식노드는 우선순위에 따라 정렬이 되어 있지만 형제 간의 순위는 정렬되어 있지 않은 반정렬 상태이다. 또한, 중복값이 허용된다. 힙의 종류 최소힙 : 부모 노드가 자식노드보다 작은 힙 최대힙 : 부모 노드가 자식노드보다 큰 힙 최소힙 알고리즘 코드 출처 : https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net import java.util.ArrayList; import java.io.IOE..
Programando/Algorithm 2021. 7. 19.
그래프의 탐색_DFS : Depth-First-Search, 루트 노드나 임의의 노드에서 시작하여 최대한 깊숙이 들어가서 탐색한 후 다시 원점으로 돌아가 다른 루트로 탐색하는 방법이다. DFS의 특징 자동 미로 생성 또는 미로 탐색에 사용된다. 모든 노드를 방문하고자 경우에 사용한다. 자기 자신을 호출하는 순환 알고리즘의 형태 노드 방문 여부를 확인해야 한다. 그렇지 않을 경우 무한 루프에 빠질 위험이 있다. DFS의 구현 인접 행렬을 이용한 코드 class DFS { private int nV; private int[][] graph; private boolean[] visited; public DFS(int nV) { this.nV = nV; this.graph = new int[nV+1][nV+1]; this.visit..
Programando/Algorithm 2021. 7. 14.
그래프의 탐색_BFS Algorithm : 그래프의 탐색_BFS BFS : Breadth-First-Search, 시작 정점으로부터 가장 가까운 정점을 먼저 방문하고, 멀리 떨어져있는 정점을 나중에 방문한다. 루트 노드나 임의의 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다. BFS의 특징 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용한다. 큐를 이용해 반복적 형태로 구현한다. 노드 방문 여부를 확인해야 한다. 그렇지 않을 경우 무한 루프에 빠질 위험이 있다. BFS의 구현 인접 리스트를 이용한 구현 import java.util.ArrayList; import java.util.Queue; import java.util.LinkedList; public class Main { static int..
Programando/Algorithm 2021. 7. 11.
그래프(Graph) : 그래프(Graph)는 정점(Node 혹은 Vertex)과 간선(Edge 혹은 Branch)로 이루어져 있으며 간선은 정점과의 관계를 나타내는데 사용한다. G = (V, E)와 같이 나타낸다. 그래프의 종류 무방향 그래프 : 간선을 통해 양방향으로 이동할 수 있는 그래프로, G(A, B) = G(B, A) 방향 그래프 : 간선에 방향이 존재하는 그래프로, G(A, B) ≠ G(B, A) 가중치 그래프 : 간선에 비용 또는 가중치가 할당된 그래프 연결 그래프 : 무방향 그래프에서 모든 정점쌍들에 대해 항상 경로가 존재하는 그래프 비연결 그래프 : 무방향 그래프에서 특정 정점쌍들에 경로가 존재하지 않는 그래프 순환 그래프 : 단순 경로의 시작 정점과 종료 종점이 동일한 경우 비순환 그래프 : 순환이 없는 ..
Programando/Algorithm 2021. 6. 18.
덱과 JAVA Deque 클래스 : 데이터를 앞, 뒤에서 삽입하거나 삭제할 수 있는 자료구조로, 스택과 큐의 성질이 적절하게 섞였다. 클래스로 덱 구현하기 덱 노드 클래스 : Node - 덱에 저장할 변수 num과 덱의 왼쪽 노드를 저장하는 left, 덱의 오른쪽 노드를 저장하는 right로 이루어져 있다. 생성자 : Deque - front, rear를 null로 설정하고, count를 0으로 설정한다. push 메서드 pushFront - 전달받은 데이터를 새로운 Node 객체에 넣고, 덱이 비어있는지 확인한다. 덱이 비어있다면 해당 Node를 front와 rear에 넣어주고, 노드의 left와 right를 null로 설정한다. 덱이 비어있지 않다면 현재 front의 left에 Node를 넣어주고, Node의 left는 null로 ..
Programando/Algorithm 2021. 6. 15.
큐와 JAVA Queue 클래스 Algorithm : 큐와 JAVA Queue 클래스 : 데이터를 일시적으로 저장하기 위한 자료구조로, 가장 먼저 넣은 데이터를 가장 먼저 꺼낸다. 큐의 특징 FIFO(First In First Out), 가장 먼저 넣은 데이터가 가장 먼저 출력된다. 큐에 데이터를 넣는 작업은 enqueue, 큐에서 데이터를 꺼내는 작업은 dequeue이다. 데이터가 삽입되는 위치는 rear이고, 데이터를 꺼내는 위치는 front이다. 링 버퍼로 큐 구현하기 큐로 사용할 배열 : que - enqueue하는 데이터를 저장하기 위한 큐 본체용 배열 큐 용량 : max - que에 저장할 수 있는 최대 요소의 개수와 같다. 큐 요솟수 : num - que에 저장되어 있는 요소의 개수 생성자 : Queue - num과 fro..
Programando/Algorithm 2021. 6. 9.
스택과 JAVA Stack 클래스 Algorithm : 스택과 JAVA Stack 클래스 : 데이터를 일시적으로 저장하기 위한 자료구조, 가장 마지막에 넣은 데이터를 가장 먼저 꺼낸다. 스택의 특징 LIFO(Last In First Out), 가장 마지막에 넣은 데이터가 가장 먼저 출력된다. 스택에 데이터를 넣는 작업은 push, 스택에서 데이터를 꺼내는 작업은 pop이다. push와 pop이 일어나는 위치는 top, 스택의 가장 아래는 bottom이다. 스택 만들기 스택 본체 배열 : stk - stk[0]이 스택의 bottom 스택 용량 : max - 배열 stk의 요솟수와 같다. 스택 포인터 : ptr - 스택에 쌓여있는 데이터의 수를 나타낸다. 생성자 : Stack - ptr을 0으로 설정하고, max의 값을 설정하고, stk 배..
Programando/Algorithm 2021. 5. 29.
정렬: 좌표 압축 Algorithm : 좌표 압축 : 좌표의 범위가 너무 큰 경우 인덱싱으로 좌표 사이 갭을 없애는 기법으로, 데이터를 정렬해서 다시 순서를 부여하는 것 좌표 압축이 필요한 이유 일차원 직선상에 N=10만개의 점이 있고 [x, y] 구간의 점 개수를 출력하는 쿼리가 M개 있을 때, 점의 범위나 x, y의 범위가 [-109, 109] 라면 세그먼트 트리를 구성하려고 했을 때 일반적으로 문제에서 주어지는 메모리 256MB로는 해결이 불가능하다. 하지만 점의 개수에 비해 점의 범위가 훨씬 넓어 sparse 하다는 점을 이용한다면 각 점의 좌표마다 인덱싱을 해, 정렬된 순서로 번호를 매김으로써 답을 구할 수 있다. 좌표 압축 알고리즘 코드 출처 : https://www.acmicpc.net/problem/1887..
Programando/Algorithm 2021. 5. 27.
정렬: Comparator 어제 그리디 알고리즘 문제를 풀다가 또 Comparator를 사용할 기회가 생겨서 사용해봤다! 그리고 오늘 또 비슷하게 Comparable이나 Comparator로 풀만한 문제가 있길래 둘 다 구현해서 제출해봤당ㅎㅎ 1은 Comparable로 구현을 한 것이고, 2는 Comparator로 구현한건데 미세하게 1이 더 빠르긴 해서.. Comparable로 구현하는게 더 빠른가? 하고 고민중 Algorithm : Comparator Comparator 기본 정렬 기준(int/long 오름차순 정렬, String 사전순 정렬) 외에 다른 기준으로 정렬하고자 할 때 사용한다. compare 함수의 return 값이 양수라면 두 요소의 자리를 바꾼다. return 값이 0이나 음수라면 두 요소의 자리를 바꾸지 않..
반응형

티스토리툴바