분류 전체보기
-
백준 1026번 : 보물 (JAVA)알고리즘, SQL/알고리즘 2024. 2. 13. 13:13
https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 지문에 A 배열은 정렬이 가능하지만, B배열은 정렬하지 말라는 조건이 있지만, 풀고나서 다른 사람들 풀이를 참고하니 다들 B배열까지 정렬하길래 풀이를 남겨본다. 풀이 방법 풀이방법으로는 A배열을 오름차순으로 정렬한 뒤, A배열의 가장 작은 값과 B배열의 가장 큰 값을 순서대로 찾도록 했다.(A배열의 가장 작은 값과 B배열의 가장 큰 값이 곱해지도록) 그리고 B배열에 같은 값이 중복해서 들어..
-
백준 7576번 : 토마토알고리즘, SQL/알고리즘 2024. 1. 27. 00:01
https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 풀이과정 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; import java.io.IOException; public class Main { public st..
-
유니온 파인드(Union Find)알고리즘이란 무엇인가?(+ 백준 1717번 : 집합의 표현)알고리즘, SQL/알고리즘 2024. 1. 26. 22:06
코딩테스트 알고리즘 유형을 보던중 유니온 파인드라는 유형을 보게 되었고, 무엇인지 궁금해서 정리하면서 공부해보려고 한다. 유니온 파인드(Union Find)란? 유니온 파인드(UnionFind)란 그래프 알고리즘으로 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘으로 노드를 합치는 Union연산과 노드의 루트 노드를 찾는 Find연산으로 이루어져있다. 서로소 집합, 상호 베타적 집합(Disjoint-Set)으로도 불린다. 위의 그래프에서 3번과 7번이 연결되어 있는지 확인하기 위해서는 DFS/BFS를 통해서 찾을 수 있지만, 이 외에 다른 노드들의 정보(예를 들어 5번과 9번 노드가 연결되었는지, 2번과 6번 노드가 연결 되었는지)를 확인하고 싶을 수 있다. 이 외에도 현재는 적은 노드수의 그래프이지..
-
백준 1012번 : 유기농 배추알고리즘, SQL/알고리즘 2024. 1. 15. 13:09
https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net BFS사용 public class Main { public static void main(String args[]) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int T = Integer.parseInt(br.readLine()); for(int test=0; test
-
백준 2110번 : 공유기 설치알고리즘, SQL/알고리즘 2024. 1. 1. 23:57
https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net public class Main { public static void main(String args[]) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer..
-
너비 우선 탐색/BFS 알고리즘이란?알고리즘, SQL/알고리즘 2023. 12. 30. 15:26
BFS 알고리즘이란? BFS는 Breadth-First Search의 약자로 너비 우선 탐색이라고도 불린다. BFS는 시작노드에서 가까운 노드를 먼저 방문하고, 멀리 떨어진 정점을 나중에 방문하는 탐색 방법이다. 즉, 깊게 탐색하기 전에 넓게 탐색하는 것이다. BFS의 특징 두 노드 사이의 최단 경로, 임의의 경로를 찾고 싶을 때 사용한다.(ex.미로를 빠져나가는 최단경로) BFS는 재귀적으로 동작하지 않는다. 탐색 시 노드를 방문하면 반드시 방문여부를 체크해야 한다.(이를 검사하지 않으면 무한루프에 빠질 수 있음) BFS는 일반적으로 방문한 노드들을 순서대로 저장 후 순서대로 꺼낼 수 있는 자료구조인 큐(Quque)를 사용한다. - 즉, 선입선출(FIFO /First in First Out) 원칙으로 ..
-
깊이 우선 탐색/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) : 무방향 그래프에서 하나의 정점에 인접한 정점의..