java
-
[백준 7576번] 토마토 (자바)Algorithm/BFS 2022. 5. 13. 21:46
백준알고리즘 7576번 : 토마토 (Solved.ac 난이도 Gold5) https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 전형적인 BFS문제이다만.. 나는 DFS로 몇 번 시도해보고서야 완전 틀린 해석이었다는 걸 깨달았다. DFS로 하게되었을 때의 문제점이라면, 각 구역마다 한번의 탐색으로 끝내도 될 것을 계속 접근하여 비효율적으로 만드는 것이다. 잘 익은 토마토를 기준으로 너비 우선탐색으로 뻗어나가면, 애초에 검증이 많이 필요..
-
[백준 2473번] 세 용액 (Java 풀이)Algorithm/정렬(Sort) 2022. 5. 6. 20:27
백준알고리즘 2473번 : 세 용액 (Solved.ac 난이도 Gold4) https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 숫자 3개를 선택하여 가장 절대값이 가장 작은 숫자를 만드는 조합을 출력하는 문제이다. 두개라면 two pointer를 사용하여 풀 수 있을꺼라 생각하였는데, 고민하다가 하나를 고정하는 대신 나머지 2개를 투 포인터로 fix하는 방법은 어떨까 생각해보았다. 물론 내가 작성한 logic은 중복으로 탐색하..
-
[백준 7453번] 합이 0인 네 정수 (Java 풀이)Algorithm/정렬(Sort) 2022. 4. 29. 13:07
백준알고리즘 7453번 : 합이 0인 네 정수 (Solved.ac 난이도 Gold2) https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 첫번째로 간과한 부분은 12초가 꽤 러프하다고 생각하여 단순 계산으로 시도해본 것이고, 두번째로 간과한 부분은 속도를 높이기 위해 투 포인터 방식을 사용했으나 동일한 연산에 대하여 곱셈이 아니라 덧셈으로 count를 해준 것이다. 예를들어 AxB 배열에 13이 3개, CxD 배열에 -13이 3개..
-
[백준 2193번] 이친수 (자바)Algorithm/Dynamic Programming(DP, 동적 프로그래밍) 2022. 4. 20. 20:05
백준알고리즘 2193번 : 이친수 (Solved.ac 난이도 Silver3) https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 규칙을 찾고나면 어렵지 않게 풀 수 있는 문제같다. 그리고 규칙을 찾는 방법은 작은 경우에서부터 하나씩 크기를 늘리면서 앞전 경우와 연결되는 연속성을 발견하는 것이다. 예를 들어 3자리 숫자일때와 4자리 숫자일때를통ㅇ해 규칙을 찾아보자. 3자리 숫자일때는 100, 101로 총 2가지 경우의 수가 있다. 4자리 ..
-
[백준 11727번] 2×n타일링2 (자바)Algorithm/Greedy Algorithm 2022. 4. 16. 18:35
백준알고리즘 11727번 : 2Xn 타일링 2 (Solved.ac 난이도 Silver3) https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 2xn 타일링1 문제를 풀었으면 이 문제도 어렵지 않게 풀수 있을 것 같다. 역시 dp 알고리즘의 기본은 쪼개기다. 다만 이번에는 2xn 타일링1 문제때와는 달리 '2x1 막대가 오는 경우와 1x2 막대가 오는 경우'로 나누지 않고 '2x1 막대가 오는 경우와 2x1 막대가 오지 않는 경우'로 나눠주었다. 이렇게 나눈 이유는 이번 문제에는..
-
[백준 1082번] 배 (Java 풀이)Algorithm/정렬(Sort) 2022. 4. 15. 19:36
백준알고리즘 1082번 : 배 (Solved.ac 난이도 Gold5) 박스를 배로 옮기는데 드는 시간의 최솟값을 구하는 문제이다. 이 문제에서 크레인의 무게제한을 비중있게 생각할 필요는 없다. 무게가 많이 나가는 박스부터 옮기되 들수 있는 무게가 적은 크레인이라도 어느 하나의 박스라도 옮길 수 있도록 체크해주면 된다. 따라서 크레인과 박스를 내림차순으로 정렬하고 크레인 배열이 박스 배열을 돌면서 옮겨주면 된다. 옮긴 박스는 체크하고, 크레인 배열이 한 번 돌때마다 시간을 1씩 늘린다. https://www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000..
-
[백준 8979번] 올림픽 (Java 풀이)Algorithm/정렬(Sort) 2022. 4. 13. 21:19
백준알고리즘 8979번 : 올림픽 (Solved.ac 난이도 Silver5) 특정 국가의 올림픽 순위를 출력하는 문제이다. 금메달, 은메달, 동메달 총 3개의 값을 비교하여 적절한 순위를 출력한다. https://www.acmicpc.net/problem/8979 8979번: 올림픽 입력의 첫 줄은 국가의 수 N(1 ≤ N ≤ 1,000)과 등수를 알고 싶은 국가 K(1 ≤ K ≤ N)가 빈칸을 사이에 두고 주어진다. 각 국가는 1부터 N 사이의 정수로 표현된다. 이후 N개의 각 줄에는 차례대로 각 www.acmicpc.net Comparator를 이용하여 2차원 배열의 3개 값을 비교하는 것 까지는 어렵지 않았으나, 동점일 경우에 순위를 확정지을수 있는 방법에 대한 고민이 필요했다. 결과적으로는 2차원..
-
[백준 3273번] 두 수의 합 (Java 풀이)Algorithm/정렬(Sort) 2022. 4. 12. 19:10
백준알고리즘 3273번 : 두 수의 합 (Solved.ac 난이도 Silver3) 더해서 자연수 x를 만족하는 쌍이 몇개 있는지 확인하는 문제이다. https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 처음에는 100만까지 숫자가 주어진다는 것을 확인하여 Int 배열의 크기를 100만으로 만들고, 받아온 숫자값에 1을 넣어서 숫자가 1이면 count한다, 라는 식으로 풀어보았다. 예제를 반영하자..