Dev Log

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 풀이 1. 상어의 위치부터 시작한다. 2. 상어를 기준으로 Queue에 이동가능한 좌표를 +1씩 하면서 add한다. 3. 모든 맵을 순회하면서(BFS) 먹을 수 있는 물고기의 좌표는 따로 리스트에 담는다. 이중 가장 가까운 물고기를 사냥한다. 소스코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.I..

알고리즘/문제 2022. 1. 9. 21:13

https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 연결 요소의 개수를 구하라는 뜻은 몇개의 덩어리로 이루어저있는지 구하라는 뜻이다. 아무것도 연결되지 않은 정점도 포함되어야한다. DFS 또는 BFS 알고리즘을 이해했다면 앞서 말한 경우의 수는 자연스럽게 포함된다. DFS 풀이 import java.io.BufferedReader; import java.io.InputStreamRead..

알고리즘/문제 2021. 10. 29. 21:45

DFS / BFS DFS(깊이 우선 탐색)과 BFS(너비 우선 탐색)은 그래프를 탐색하는 방법 중의 하나이다. 그래프란, 노드(node)와 노드를 연결하는 간선(edge)으로 이루어진 자료구조이다. 그래프를 탐색한다는 것은 하나의 노드로부터 시작하여 모든 노드를 방문한다는 뜻이다. DFS(Depth-First Search) 루트노드(혹은 다른 임의의 노드)에서 다음 분기(Branch)로 넘어가기 전에 해당 분기를 끝까지 탐색하는 방법이다. 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다. 깊이 우선 탐색(DF..

알고리즘/개념 및 TIP 2021. 10. 28. 21:18

'에라토스테네스의 체' 알고리즘을 이용한 문제풀이 예제이다. 백준 1929 [소수 구하기] 라는 문제이다. 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw ..

알고리즘/문제 2021. 9. 27. 20:50

에라토스테네스의 체 고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법이다. 이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부른다. 임의의 자연수 n에 대해 그 이하의 소수를 찾는 가장 간단하고 빠른 방법이다. 에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전 수학에서 에라토스테네스의 체는 소수를 찾는 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다. 알고리즘[편집] 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 ko.wikipedia.org 아래의 개념만 숙지하면 된다. 1. 소수란 '1과 자기 자신 외의 약수를 가지지 않는 1보다 큰 자연수'이다. 2. 소수의 배수는 소수가 아니다. ex) 5는 소수이다. 5의 배수 10,..

알고리즘/개념 및 TIP 2021. 9. 26. 09:30

BufferedReader는 알고리즘 문제를 풀다 보면 접하게 된다. 필자도 처음에는 Scanner를 이용하여 알고리즘 문제를 풀었으며 시간 초과가 나서 다른 사람들의 풀이를 참조하다 알게 되었다. BufferedReader와 Scanner의 가장 큰 차이는 속도이다. BufferedReader Scanner와 BufferedReader의 속도 차이가 나는 것을 확인할 수 있다. BufferedReader는 사용자의 요청이 있을 때 데이터를 읽어오는 것이 아니라 데이터를 한 번에 읽어와 버퍼에 보관한 후 버퍼에서 데이터를 읽어오는 방식이다. 보통 readLine() 메소드를 사용하여 라인 단위로 입력을 받아 split 또는 StringTokenizer를 사용한다. 사용방법 BufferedReader br..

알고리즘/개념 및 TIP 2021. 9. 15. 14:11