그래프 (Graph)현실세계의 사물이나 개념 간의 연결 관계를 수학적 모델로 단순화하여 표현한 것 그래프 표현1. 간선 리스트(Edge List)정점의 개수가 V개, 간선의 개수가 E개인 그래프에 대해서 E x 2 (or E x 3) 이차원 배열(A)에 간선 정보를 저장어떤 두 정점 vi, vj를 연결하는 간선 ek = (vi, vj) 에 대해서 A[k][0] = vi, A[k][1] = vi가중치 그래프의 경우 배열의 3번째 열에 간선의 가중치를 저장벨만-포드 알고리즘에서 사용한다.코드 구현간선 정보 classstatic class Edge{ int from; int to; int cost; public Edge(int from, int to, int cost){ th..
https://www.acmicpc.net/problem/2252알고리즘 분류 : 그래프 이론, 위상 정렬, 방향 비순환 그래프❓문제🔅해석위상정렬을 이용하여 풀이한다. 위상정렬은 비순회 방향 그래프에서 정점을 정렬하는 방식이며, 동일한 우선순위를 가진 작업들이 여러 가지 방법으로 나열될 수 있기 때문에 여러 개의 정렬 결과가 나올 수 있다. // input4 24 23 1 1. indegree 계산 및 indegree 배열 중에서 0인 노드를 Queue에 담는다. 2. Queue에서 pop를 하고, 3(pop 한 값)과 연결된 노드에 indegree를 하나 감소시킨다. 3. Queue에서 pop를 하고, 4(pop 한 값)와 연결된 노드에 indegree를 하나 감소시킨다. 4. Queue가 빌 ..
https://www.acmicpc.net/problem/1717알고리즘 분류 : 자료 구조, 분리 집합❓문제🔅해석Union-Find의 기초 문제이다. Union 연산은 어떤 두 원소 a, b에 대해서 각 원소가 속한 집합을 하나로 합치는 연산이다.먼저 두 원소가 같은 집합인지 확인하고 같은 집합이 아니라면 하나로 합친다. 보통 같은 집합을 확인하는 과정은 부모의 번호를 기재하여 확인한다.Find 연산은 어떤 원소 a에 대해서 a가 속한 집합(집합의 대표번호)을 반환한다. 문제의 예시를 아래와 같이 가정한다.//input7 40 1 31 1 70 7 61 1 3 1. 7 4n개의 집합을 생성한다. 각 집합의 부모는 자신을 가르키고있다. 2. 0 1 3union1과 3에 대해 parent를 확인하고 같..
https://www.acmicpc.net/problem/1202알고리즘 분류 : 자료 구조, 그리디 알고리즘, 정렬, 우선순위 큐 ❓문제🔅해석조건이 2개 이상이므로 우선순위 큐(PQ)를 사용하여 문제를 풀이한다. 보석의 속성이 2가지 있으므로 객체로 생성하여 짝을 이룰 수 있게한다. 가방에 넣을 수 있는 보석을 PQ에 담기 위해 가방과 보석의 무게를 오름차순 정렬한다. 이후 반복문을 돌면서 정답을 계산한다.1. 가방을 하나 고른다.2. 무게순으로 정렬한 보석을 해당 가방에 들어갈 수 있는지 비교하고 들어갈 수 있다면 해당 보석을 PQ에 넣는다.3. 한 가방에 다 넣었으면 PQ에서 보석을 꺼내어 해당 보석의 가격을 정답에 더한다. ⭕정답 코드import java.io.BufferedReader;impo..
유클리드 호제법빠른 시간에 두수의 최대공약수를 구할 수 있는 방법이다.2개의 자연수의 최대공약수를 구하는 알고리즘의 하나이다.2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a > b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다는 성질을 이용한다.gcd(a, b) = gcd(b, r) 공식 대입해보기a = 36, b = 24gcd(a, b) = gcd(b, a % b)gcd(36, 24)= gcd(24, 12)= gcd(12, 0)r == 0 일 때, b가 최대공약수가 된다. 예제문제백준 14476번 : 최대공약수 하나빼기 https://www.acmicpc.net/problem/14476 최대공약수 구하는 메소드// gcd(a, b) == gcd(b, r) : r ..
트라이(Trie)Prefix Tree, Digital Search Tree, Retrieval Tree문자열을 빠르게 검색할 수 있는 자료구조K진 트리 구조 (문자열 K를 담을 수 있는 트리)단어 사전을 트라이로 생성 후 찾을 단어를 트라이를 사용하여 검색한다.트라이의 root 노드는 항상 공백문자열 상태이다. 구축하기트라이 노드 설계class Node { Node child[]; boolean isWord; }단어 사전의 입력할 단어를 트라이에 삽입루트 노드부터 시작하여 단어의 첫 글자부터 트라이를 탐색만약, 현재 노드의 자식 중 현재 입력 중인 철자에 해당하는 자식이 있다면, 현재 노드를 해당하는 자식 노드로 이동만약, 현재 노드의 자식 중 현재 입력 중인 철자에 해당하는 자식이 없다면, 새로운 자식..
https://www.acmicpc.net/problem/9202알고리즘 분류 : 자료 구조, 그래프 이론, 문자열, 브루트포스 알고리즘, 그래프 탐색, 트리, 깊이 우선 탐색, 백트래킹, 트라이❓문제🔅해석Trie 알고리즘을 활용하여 문제를 해결한다. 먼저, 입력받은 단어들로 Trie를 생성한다."ACM'을 입력받았다면 아래와 같이 Trie 객체가 생성된다. for문을 순회하여 Trie 객체인 root를 완성하면 뒤에 N개의 맵을 입력받아 탐색한다. dfs를 작성할 때는 아래 6단계를 거쳐 작성하는 것을 추천한다. 1. 체크인visited 배열에 true 를 입력하고 현재 map 좌표에 있는 알파벳 하나를 Stringbuilder에 붙인다. 2. 목적지인가목적지의 기준은 1) 현재 노드가 단어이면서, ..
자료구조 (Data Structure)자료구조란 효율적으로 접근하고 수정할 수 있도록 데이터를 구성하고 저장하는 방법.저장되는 데이터의 형태에 따라 선형 자료구조와 비선형 자료구조로 구분된다.선형 자료구조 : 데이터가 일렬로 나열되어 있음배열, 연결 리스트, 스택, 큐비선형 자료구조 : 데이터가 특정한 형태를 띄고 있음트리, 그래프 1. 배열 (Array)가장 기본적인 자료구조로 동일한 자료형의 데이터를 일렬로 나열한 자료구조배열의 특징데이터 접근이 용이하다. (O(1)의 시간복잡도를 가짐)데이터 삽입/삭제가 어렵다. (O(N)의 시간복잡도를 가짐)중간에 데이터를 삽입하거나 삭제할 경우, 해당 위치 이후의 모든 요소를 이동해야 한다.구조가 간단하여 프로그램 작성이 쉽다.1) 배열 []int[] arr =..
https://www.acmicpc.net/problem/2243알고리즘 분류 : 자료 구조, 세그먼트 트리, 이분 탐색 ❓문제🔅해석 세그먼트 트리에서 구간의 정보를 조회하는 query는 총 다섯가지 정보를 넘긴다.query(int left, int right, int node, int queryLeft, int queryRight) 현재 문제에서는 해당 순위의 정보만 필요하므로 query(int left, int right, int node, int query) 으로 넘긴다. 문제의 입력을 보자면, 레벨 1 사탕 2개, 레벨 3 사탕 3개가 존재하고 여기서 2번째로 맛있는 사탕을 꺼내준다고 할 때, 답은 레벨 1이다. 위 그림을 볼 때, 노드를 탐색하면서 해당 노드의 값이 B보다 크거나 같을 때 왼쪽..
