목록알고리즘/백준 (42)

안드 공부를 해볼까?

[Kotlin] 백준 지능형 기차2

1. 문제분석 https://www.acmicpc.net/problem/2460 2460번: 지능형 기차 2 최근에 개발된 지능형 기차가 1번역(출발역)부터 10번역(종착역)까지 10개의 정차역이 있는 노선에서 운행되고 있다. 이 기차에는 타거나 내리는 사람 수를 자동으로 인식할 수 있는 장치가 있다. www.acmicpc.net 사실 문제분석이랄 것도 없는게 for문만 사용하면 풀 수 있다. 10개의 역에서 각각 내렸다가 탔다가 할 때 가장 많이 타고 있는 사람의 명수를 구하면 된다. 2. 구현 import java.io.BufferedReader import java.io.InputStreamReader import kotlin.math.max fun main(args: Array) { val br ..
알고리즘/백준 2023. 2. 24. 17:33
[Java] 백준 스카이라인 쉬운거

1. 문제분석 https://www.acmicpc.net/problem/1863 1863번: 스카이라인 쉬운거 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 50,000) 다음 n개의 줄에는 왼쪽부터 스카이라인을 보아 갈 때 스카이라인의 고도가 바뀌는 지점의 좌표 x와 y가 주어진다. (1 ≤ x ≤ 1,000,000. 0 ≤ y ≤ 500,000) 첫 www.acmicpc.net 스카이라인은 태양이 질 때에 보이는 건물들의 윤곽이라고 한다. 이때 건물의 최소 개수를 구하는 문제다. 힌트를 보면 이해하기가 쉬워진다. 스카이라인의 고도가 높아졌다가 낮아질때 그 건물의 개수가 특정된다. 고도를 처음부터 보면 1 2 2 2 1 3 3 1 이다. 2 2 2에서 1로 낮아졌을 때 2 2 2는 한 건물로 특정지을 수 ..
알고리즘/백준 2023. 1. 6. 00:24
[Java] 백준 빗물

1. 문제 분석 https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 가로와 세로가 주어지고 각 가로셀마다 높이가 주어진다. 그때 빗물이 몇개 고이는지 확인하는 문제다. 백준에 있는 힌트다. 여기서 가로 기준으로 잘 보면 규칙이 있다. 파란색으로 칠한 부분을 보면 된다. 검은색을 0, 하얀색을 1로 생각해보자. 첫째줄은 0 1 0 0이 된다. 빗물은 1칸 채워진다. 둘째줄은 0 1 1 0이 된다. 빗물은 2칸 채워진다. 셋째줄은 0..
알고리즘/백준 2022. 12. 31. 00:22
[Java] 백준 오르막 수

1. 문제분석 https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 숫자의 길이가 주어지고 오르막 수를 구하는 문제다. 간단한 dp 문제고 경우의 수를 구하면 규칙이 보인다. N이 1 ~ 3 일때를 구해봤다. 규칙은 회색칸을 더하면 파란색칸이 나온다는 것이다. 따라서 dp[i][j] = dp[i-1][j] + dp[i][j-1] 2. 구현 import java.io.BufferedReader; import java..
알고리즘/백준 2022. 12. 30. 00:15
[Java] 백준 세 친구

1. 문제분석 https://www.acmicpc.net/problem/17089 17089번: 세 친구 첫째 줄에 사람의 수 N(3 ≤ N ≤ 4,000), 친구 관계의 수 M(0 ≤ M ≤ 4,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계를 의미하는 두 정수 A, B가 주어진다. 친구 관계는 A와 B, 그리고 B와 A가 친 www.acmicpc.net 1부터 N까지의 사람이 주어지고 각 친구관계를 보여준다. 이 사람들 중 3명을 뽑았을 때 각 친구수가 가장 적은 사람수를 구하면 된다. 즉, 1 2 3 4의 친구관계가 주어지면 1 2 3 4 중 3명을 뽑았을 때 그 친구수가 가장 작은 값을 출력하면 된다. 2. 시행착오 먼저 문제가 이해안갔다. 친구관계를 주는데 무슨 또 친구를 뽑으라는건지..
알고리즘/백준 2022. 12. 23. 23:00
[Java] 백준 최단경로

1. 문제분석 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 방향그래프가 주어지고 모든 정점으로 최단 경로를 구하는 문제다. 이 문제는 시작 정점에 모든 정점을 탐색하는 것이므로 다익스트라를 사용했다. 또한, 출력값은 최단 경로의 경로값을 출력하면 된다. 2. 시행착오 그래프 문제를 풀어보고 싶어서 고른 문제였다. 대학교때 배운 것이 기억이 안나 답지는 안보고 알고리즘만 보고 문제를 풀어갈려고 했다. 1...
알고리즘/백준 2022. 12. 21. 16:23
[Java] 백준 연산자 끼워넣기

1. 문제 분석 주어진 숫자에 연산자를 넣는 문제다. 연산자의 개수는 주어진 숫자 - 1 만큼 주어지므로 순열을 통해 연산자의 집합을 구하면 된다. 2. 구현 import java.util.*; import java.io.*; public class Solution { static int size; static int[] numArr; static ArrayList operList = new ArrayList(); static int max = Integer.MIN_VALUE; static int min = Integer.MAX_VALUE; public static void main(String[] args) throws IOException { BufferedReader br = new Buffered..
알고리즘/백준 2022. 10. 14. 00:15
[Java] 백준 인구 이동

1. 문제 분석 문제를 제대로 이해해보자. 하루단위로 국가마다 연합을 만들고 인구이동을 하는 것이다. 필자는 인구이동이 일어났다면 하루라고 생각해서 시간이 꽤 걸렸다. DFS를 사용했고 연합이 만들어지는 조건을 달성하면 합쳐주고 합칠 국가가 없으면 걸린 날짜를 반환한다. 연합이 만들어지는 조건은 다음과 같다 1. 배열의 인덱스 값을 벗어나면 안된다. 2. 이미 방문한 곳은 가면 안된다. 3. L과 R 사이의 수여야만 한다. 3번 조건을 위해 절댓값을 활용했다(Math.abs) 2. 구현 import java.util.*; import java.io.*; class Point { int x, y; Point(int x, int y) { this.x = x; this.y = y; } } public clas..
알고리즘/백준 2022. 10. 13. 23:22
Prev 1 2 3 4 ··· 6 Next