Kwin's Development Diary.

Queue : 선입 선출(FIFO: First In First Out)의 성격을 지닌 자료구조 [자료구조] 큐(Queue)에 대한 설명글 [자료구조] 큐(Queue) 큐 (Queue) - 스택과 마찬가지로 삽입과 삭제의 위치가 제한된 유한 순서 리스트 - 선입선출 구조(FIFO, First-In-First-Out) : 삽입 순으로 나열되어 가장 먼저 삽입한 원소가 가장 먼저 삭제된다. 삭제 kwin0825.tistory.com 선언 import java.util.Queue; import java.util.LinkedList; Queue 변수명 = new LinkedList(); ㄴ 위 같은 경우는 자료형에 넣은 자료형만 삽입, 삭제 가능 Queue 변수명 = new LinkedList(); ㄴ 위 같은 ..

문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다) 예를 들어, 그림이 아래와 같은 경우에 RRRBB GGBBB BBBRR BBRRR RRRRR 적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. ..

너비 우선 탐색(Breath First Search, BFS) : 하나의 정점으로부터 시작하여 인접한 정점들을 우선으로 탐색하여 최종적으로 모든 정점을 탐색하는 방법 특징 ① 목표 지점까지 최단 길이(경로)를 보장한다. ② 경로가 길수록 인접한 정점이 많이 생겨나므로(저장되므로) 저장 공간이 많이 필요하다. ③ 선입선출(FIFO, First In First Out) 구조이다. BFS 알고리즘 ① 시작 정점 v를 결정하여 방문 ② 정점 v에 인접한 정점들 중 방문하지 않은 정점을 차례로 방문하면서 큐에 enQueue ③ 방문하지 않은 인접한 정점이 없으면, 방문했던 정점에서 인접한 정점을 다시 차례로 방문하기 위해 큐에서 deQueue 하여 구한 정점에서 ②반복 ④ 큐가 공백이 될 때까지 ②~③반복 더보기..

문제 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다. 출력 첫째 줄에 연결 요소의 개수를 출력한다. 문제 접근 방법 이번 문제는 입력으로 주어진 그래프의 연결 요소의 개수를 파악하는 문제이다. 이때, 연결 요소란? 한 정점에서 출발하여 도착할 수 있는 정점들의 집합이라 생각하면 쉽다. 이게 무슨 의미냐면 정점 V1과 간선을 통해 해당 정점 Vn에 도착할 수 있다면 같은 연결 ..

문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 출력 첫째 줄에 DFS를 수행한 결과를, 그다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다. 문..

그래프 순회(graph traversal), 그래프 탐색(graph search) - 하나의 정점에서 시작하여 그래프에 있는 모든 정점을 한 번씩 방문하여 처리하는 연산 - 그래프 탐색 방법 ㄴ 깊이 우선 탐색 (Depth First Search : DFS) ㄴ 너비 우선 탐색 (Breadth First Search : BFS) 깊이 우선 탐색(Depth First Search : DFS) >>> A - B - D - G - E - C - F ① 시작 정점 v를 결정하여 방문 ② 정점 v에 인접한 정점 중 1. 방문하지 않은 정점 w가 있으면, 정점 v를 스택에 push 하고 w를 방문하고 w를 v에 대입하여 ②과정 반복 수행 2. 방문하지 않은 정점이 없으면, 탐색의 방향을 바꾸기 위해 마지막 방문 정..

큐 (Queue) - 스택과 마찬가지로 삽입과 삭제의 위치가 제한된 유한 순서 리스트 - 선입선출 구조(FIFO, First-In-First-Out) : 삽입 순으로 나열되어 가장 먼저 삽입한 원소가 가장 먼저 삭제된다. 삭제 ← front rear 삽입 ← 큐의 연산 과정 - 삽입 : enQueue 더보기 ① 공백 큐 생성 : 큐가 생성되지 않은 최초 상태에서만 실행 Q [0] [1] [2] ↑ front == rear == -1 ↑ ② 원소 A삽입 : enQueue(Q, A); Q [0] [1] [2] A ↑ front == -1 ↑ ↑ rear == 0 ↑ ③ 원소 B삽입 : enQueue(Q, B); Q [0] [1] [2] A B ↑ front == -1 ↑ ↑ rear == 1 ↑ - 삭제 :..

문제 정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 여섯 가지이다. push X: 정수 X를 큐에 넣는 연산이다. pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 큐에 들어있는 정수의 개수를 출력한다. empty: 큐가 비어있으면 1, 아니면 0을 출력한다. front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다. back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다. 입력 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 ..