rvrlo - [자료구조] 그래프(Graph)자바를 이용해서 그래프를 직접 구현해보려고 한다.그래프에 대한 설명은 위 링크에서 확인할 수 있다. 이 글에서는 설명 없이 코드로 구현한 과정만 적는다.    인접 행렬로 무향 그래프 구현하기무방향 그래프를 구현할 것이기 때문에 입력받은 정점은 뒤바꿔서 서로 연결을 다시 해줘야 한다.방향 그래프로 구현한다면, [ from → to ]만 연결해줘도 된다.  사용하는 메서드 - add, getPrint public static void add(int from, int to){ graph[from-1][to-1] = 1; graph[to-1][from-1] = 1; } public static String getPrint(){ ..

전에 파이썬을 이용해 1260번을 풀어본 적이 있다. 이번에는 자바를 이용해서 1260번을 풀고, DFS와 BFS를 구현하려고 한다. [알고리즘] 깊이우선탐색(DFS) & 너비우선탐색(BFS) 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선..

Hash Table - (key, value) 한 쌍의 형태로 데이터 저장 key와 value가 한 쌍의 형태로 저장되는 자료구조. 각 key에 해시 함수를 적용해 내부 버킷에 값을 저장하여 관리한다. 트리를 이용하면 해당 위치에 맞는 자리를 찾아야 하지만, 해싱은 key 하나로 쉽게 값을 가져올 수 있다. 특징 순서대로 저장되지 않는다. 트리나 배열보다 빠른 속도로 데이터에 접근할 수 있다. key는 중복된 값을 가질 수 없다. value는 중복된 값이 올 수 있다. key는 value를 찾기 위한 열쇠의 역할을 한다. 만약 동일한 키가 여러개 존재한다면, 해당 키로 우리가 찾고자 하는 값을 찾을 수 없다. 해당 컬렉션에서 키는 유일하게 존재해야 한다. 해시 함수 Hash Function 해시 함수를 ..

문제 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) 출력 예제와 같이 요세푸스 순열을 출력한다. Queue클래스를 사용해 문제를 풀어보았다. 풀이 입력받은 N을..

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

트리(Tree) - 계층적 관계를 표현하는 비선형 자료구조. 상위·하위로 나뉘거나 포함하는 관계일 시 계층구조로 표현. 자료가 저장된 노드 Node와 이 노드는 잇는 간선 Edge로 구성 루트 노드 Root node: 최상위에 있는 노드 단말 노드 Leaf node, Terminal node: 하위 노드가 없는 노드 내부 노드 Internal node: 단말 노드가 아닌 (하위 노드가 있는) 노드 형제 노드 Sibling node: 같은 부모 노드를 가지는 노드 레벨 Level: 루트 0레벨부터 아래로 내려갈수록 값 증가 크기 Size: 본인을 포함하여 자손 노드의 수 깊이 Depth: 해당 노드부터 루트까지 간선의 수 높이 Height: 최하 리프에서 루트까지 깊이 = 최대 레벨의 크기와 동일 서브 트..

Stack - Last in, First out : LIFO Queue - First in, First out : FIFO 스택과 큐는 일렬로 늘어선 자료를 표현한다. 자료구조는 데이터 표현에 따라 선형 자료구조와 비선형 자료구조로 나뉜다. 스택과 큐도 배열이나 리스트처럼 선형 자료구조의 일종이다. 이 두 가지를 나누는 기준은 자료를 어떤 순서로 삽입하고 삭제하냐로 볼 수 있다. 1. Stack 스택 : 후입선출 방식을 사용한다. 가장 늦게 들어온 데이터가 가장 먼저 빠져나간다. 웹 브라우저의 뒤로가기를 예시로 들수있다. 우리가 지나온 순서에 따라 스택에 삽입되고, 뒤로가기 버튼을 통해 직전에 왔던 길을 따라 되돌아간다. 이와 같이 가장 먼저 들어온 것이 제일 마지막에 빠져나가는 방식이 스택이다. 기본 ..

https://rvrlo.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%9E%98%ED%94%84Graph [자료구조] 그래프(Graph) Graph - 선형 자료구조로 표현하기 어려운 다:다 관계를 가지는 원소를 표현 G = ( V , E ) vertex 정점: 대상이나 개체 → V : 정점의 집합 edge 간선: 정점 간의 관계 → E : 간선의 집합 그래프는 정점과 rvrlo.tistory.com 그래프 탐색을 알기 위해 그래프에 대한 기본 지식이 있어야 한다. 그래프 탐색의 가장 대표적인 DFS와 BFS 깊이 우선 탐색 Depth First Search : DFS 현재 정점과 인접한 간선들을 하나씩 검사하다가 아직 방문하지..

Graph - 선형 자료구조로 표현하기 어려운 다:다 관계를 가지는 원소를 표현 G = ( V , E ) vertex 정점: 대상이나 개체 → V : 정점의 집합 edge 간선: 정점 간의 관계 → E : 간선의 집합 그래프는 정점과 간선으로 정의된다. 계층구조로 이루어진 트리는 선형으로 표현하기 어렵다. 선형으로 표현하기 어려운 자료를 표현하기 위해 그래프가 사용된다. 1. 종류 1) 방향으로 분류 ① 무방향 그래프, 무향 그래프 (undirected graph) 정점을 연결하는 간선의 방향이 없는 그래프 방향이 없어 정점 i와 j가 있으면 (i, j) = (j, i) ② 방향 그래프, 유향 그래프, 다이 그래프 (directed graph) 간선이 방향을 가지고 있는 그래프 선후 관계 등을 나타낼 수..