알고리즘, SQL
-
깊이 우선 탐색/DFS 알고리즘이란?알고리즘, SQL/알고리즘 2023. 12. 29. 00:01
지난 포스팅에서 DFS와 BFS알고리즘을 알아보기 위해 그래프 자료구조를 선행하여 정리했다. https://hsch19.tistory.com/39 그래프(Graph) 자료구조란 무엇인가? 개요 DFS와 BFS에 대해서 정리를 해보려고 정리하던 중 그래프 자료구조에 대한 정리가 선행되어야 할 것 같아서 그래프 자료구조에 대해 먼저 정리하고자 한다. 그래프(Graph) 자료구조란? 그래프 hsch19.tistory.com DFS 알고리즘이란? DFS는 Depth-First Search의 약자로 깊이 우선 탐색이라고도 불린다. DFS는 트리나 그래프를 탐색하는 기법 중 하나로, 시작노드에서 자식의 노드들을 순서대로 탐색하면서 깊이를 우선으로 탐색하는 알고리즘이다. 비유하자면, DFS는 미로 탐색시 한 방향으로..
-
그래프(Graph) 자료구조란 무엇인가?알고리즘, SQL/알고리즘 2023. 12. 28. 00:03
개요 DFS와 BFS에 대해서 정리를 해보려고 정리하던 중 그래프 자료구조에 대한 정리가 선행되어야 할 것 같아서 그래프 자료구조에 대해 먼저 정리하고자 한다. 그래프(Graph) 자료구조란? 그래프 자료구조란 연결되어 있는 원소간의 관계를 표현한 자료구조이다. 그래프는 위와 같이 노드와(Node) 간선(Edge)의 집합으로 노드는 정점(Vertex)라고도 불린다. 즉, 노드는 하나의 도시가 되고, 간선들은 도로를 잊는 도로가 된다. 그래프 관련 주요 용어 정점/노드(Vertex/Node) : 객체 또는 위치 간선(Edge) : 정점들간의 연결관계를 나타내는 선 인접 정점(Adjacent Vertex) : 간선에 의해 직접 연결된 정점 차수(Degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의..
-
그리디(Greedy) 알고리즘이란? (+ 백준 5585번 : 거스름돈)알고리즘, SQL/알고리즘 2023. 12. 26. 23:42
그리디(Greedy) 알고리즘이란? 그리디(Greedy)란 탐욕스러운, 욕심 많은 이란 뜻으로 탐욕 알고리즘, 탐욕법이라고도 불린다. 탐욕법은 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다. 하지만 최적의 상황을 쫓는다고 해서 항상 최적의 해답을 보장하는 것은 아니다. 예를 들어 위와 같은 경우, 최적의 선택은 3 - 100 을 선택하는 경로이지만, 탐욕법은 지금 당장 큰 값인 10 - 8 경로를 선택하게 되기 때문에 선택의 순간에는 최적의 선택이지만, 최종적으로는 최적의 선택이 아닐 수 있다는 것이다. 탐욕 알고리즘 문제를 해결하는 방법 선택 절차 현재 상태에서 최적의 해답을 선택한다. 적절성 검사 선택된 해가 문제의 조건을 만족하는지 검사한다. 해답 검사 ..
-
백준 2775번 : 부녀회장이 될테야알고리즘, SQL/알고리즘 2023. 12. 23. 23:54
https://www.acmicpc.net/problem/2775 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net 문제를 보면서 공식을 찾아보려고 메모장 켜서 일부를 그려보니까 공식따위는 존재하지 않는듯 했다. 층/호 1호 2호 3호 4호 5호 6호 5층 1 7 28 84 210 462 4층 1 6 21 56 126 252 3층 1 5 15 35 70 126 2층 1 4 10 20 35 56 1층 1 3 6 10 15 21 0층 1 2 3 4 5 6 그래서 머리 좀 굴리다가..사람들 풀이를 살짝 참고해보니, 제한란에 k와n에 해당하는 값이 1이상 1..
-
백준 2292번 : 벌집알고리즘, SQL/알고리즘 2023. 12. 22. 22:35
간단하게 가운데 벌집모양부터 시작해서 인접한 변에 하나씩 추가되는 육각형에, 입력되는 숫자가 간운데로부터 몇번째에 접해있는지 찾는 문제이다! 육각형 하나를 방(room)이라고 생각했을 때, 가운데 1번방과 접해있는 가장 큰 방이 7이다. 7번방과 접해있는 가장 큰 방은 19번, 19번과 접해있는 가장 큰 방은 37번... 즉 1, 7, 19, 37, 61로 6의 배수만큼 커지는 것을 알 수 있다. 코드를 생성해보면.. public class Main { public static void main(String args[]) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int num ..
-
이분 탐색/이진 탐색(Binary Search)이란? (+백준 1920번)알고리즘, SQL/알고리즘 2023. 12. 15. 23:57
개요 알고리즘 문제를 풀다보니 이진탐색과 관련된 문제이지만, 이진탐색이 아닌 다른 방향으로 풀었던 기억이 있다. 그래서 이번에 이진탐색에 대해 정리하면서 이진탐색 문제가 나왔을 때 바로 떠올릴 수 있도록 해보고자 한다! 이진/이분 탐색이란? 순차적 탐색(선형 탐색)보다 빠른 탐색을 위해 나온 탐색 방법으로 정렬된 배열에서 특정값을 찾는 알고리즘을 의미한다. 탐색범위를 절반으로 줄여나가기 때문에 순차적 탐색에 비해 빠른 속도를 보장한다. 이진 탐색 과정 순차적 탐색(선형 탐색) 정렬된 배열에서 특정 원소를 찾기위해 모든 순차적으로 모든 인덱스를 탐색한다. 이분 탐색 정렬된 배열 안에서 특정원소를 찾을 때 인덱스 LOW값과 HIGH의 중간값을 비교 중간값이 특정원소가 아니라면 중간 값과 비교 후 다시 인덱스..
-
백준 2751번 : 수 정렬하기2 (+System.out.println 반복사용의 단점)알고리즘, SQL/알고리즘 2023. 12. 13. 23:57
https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 풀이 입력받은 값을 오름차순으로 정렬해주면 되는 간단한 문제다. 리스트를 정렬하기 위해서 Collections.sort메서드를 활용해서 public class Main { public static void main(String args[]) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(..
-
백준 7568번 : 덩치알고리즘, SQL/알고리즘 2023. 12. 12. 15:19
https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 예시 이름 (몸무게, 키) 등수 A (55, 185) 2 B (58, 183) 2 C (88, 186) 1 D (60, 175) 2 E (46, 155) 5 위 표에서 C보다 더 큰 덩치의 사람이 없으므로 C는 1등이 된다. 그리고 A, B, D 각각의 덩치보다 큰 사람은 C뿐이므로 이들은 모두 2등이 된다. 그리고 E보다 큰 덩치는 A, B, C, D 이렇게 4명이므로 E의 덩치는 ..