알고리즘, SQL/알고리즘
-
백준 2343번 : 기타 레슨알고리즘, SQL/알고리즘 2024. 9. 25. 22:56
https://www.acmicpc.net/problem/2343이분탐색이 코테문제로 많이 나오는거 같은데 이분탐색 문제가 익숙하지 못하다. 그래서 이분탐색 문제를 집중적으로 풀어보는데, 해당문제가 생각할 거리가 많아서 기록을 해두기로 했다. 문제강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 강의의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 강의와 j번 강의를 같은 블루레이에 녹화하려면 i와 j 사이의 모든 강의도 같은 블루레이에 녹화해야 한다.강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가급적 줄이..
-
백준 11404번 : 플로이드알고리즘, SQL/알고리즘 2024. 8. 15. 17:58
플로이드워셜 알고리즘을 공부하기 위해 해당 알고리즘의 기본 문제를 풀어봤다.https://www.acmicpc.net/problem/11404문제n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.출력첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b..
-
백준 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) 원칙으로 ..