[JAVA] 백준 2162 - 선분 그룹
2022. 10. 26. 19:15
JAVA/백준(BOJ) 문제풀이
문제 https://www.acmicpc.net/problem/2162 2162번: 선분 그룹 첫째 줄에 N(1 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N+1번째 줄에는 양 끝점의 좌표가 x1, y1, x2, y2의 순서로 주어진다. 각 좌표의 절댓값은 5,000을 넘지 않으며, 입력되는 좌표 사이에는 빈칸이 하 www.acmicpc.net 해결 방법 이 문제를 풀기 위해 두가지 알고리즘을 알아야 함 CCW를 사용해 두 선분이 겹치는지 판단 Union-Find를 통해 그룹을 합치고 확인하는 작업 진행 위 두 알고리즘을 알고 같이 사용한다면 쉽게 해결할 수 있음 입력받은 모든 선분들끼리 서로 겹치는지 판단 선분이 겹치는지는 CCW를 통해 판단 두 선분이 겹친다면 Union 과정 진행 위 작업이 끝..
[JAVA] 백준 2166 - 다각형의 면적
2022. 10. 8. 19:19
JAVA/백준(BOJ) 문제풀이
CCW 설명 및 백준 2166번 문제 풀이 https://chb2005.tistory.com/87 [JAVA] CCW CCW 란? Counter-ClockWise의 줄임말로 평면상의 3개의 점의 위치관계를 판한다는 알고리즘 세 점 A(X1, Y1), B(X2, Y2), C(X3, Y3) 이 있다고 가정했을 때 CCW의 공식은 CCW = ( X1*Y2 + X2*Y3 + X3*Y1 ) - ( X2*.. chb2005.tistory.com
[JAVA] 백준 1541 - 잃어버린 괄호
2022. 10. 4. 23:58
JAVA/백준(BOJ) 문제풀이
문제 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 해결 방법 5자리 이상의 수가 입력되지 않고, 식의 길이가 50이하이기 때문에 int 형으로 해결 가능 괄호를 사용해 최소값을 만들기 위해서는 빼주는 값을 최대로 만들어 주면 됨 ex) a + b + c - d + e + f - g - h 라고 가정해보자 ( a ~ h는 양의 정수 ) 이 결과를 최소로 만들어보면 a + b + c - (d + e + f) - g - h 가 됨 정리해보면..
[JAVA] 백준 2188 - 축사 배정
2022. 8. 19. 20:11
JAVA/백준(BOJ) 문제풀이
문제 https://www.acmicpc.net/problem/2188 2188번: 축사 배정 농부 존은 소 축사를 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, 존은 축사를 M개의 칸으로 구분하고, 한 칸에는 최대 한 마리의 소만 들어가게 계획했다. 첫 주에는 소를 임의 배정해 www.acmicpc.net 해결 방법 DFS로 해결했는데 이 알고리즘을 이분매칭이라고 하는것 같음 => 나중에 다시 알아봄 예제를 풀며 해결 방법 정리 ex) 입력이 아래와 같이 들어왔다고 가정 5 5 2 2 5 3 2 3 4 2 1 5 1 1 3 1 2 5 1번 소는 2, 5번 축사에 가고 싶어함 확인 후 비어있는 축사가 있으면 바로 집어 넣음 1, 2, 3번 소는 비어 있는 축사에 바로 들어갈 수 있음 이제 4번 소가..
[JAVA] 백준 2176 - 합리적인 이동경로 (Reverse Dijkstra + DP)
2022. 8. 19. 14:48
JAVA/백준(BOJ) 문제풀이
문제 https://www.acmicpc.net/problem/2176 2176번: 합리적인 이동경로 첫째 줄에 정점의 개수 N(1 정답은 몇개일까?? 1 -> 2로 갈 수 있는 방법은 총 6개 [1->2] [1->3->4->5->2] [1->3->5->2] [1..
[JAVA] 백준 2749 - 피보나치 수 3
2022. 8. 18. 21:14
JAVA/백준(BOJ) 문제풀이
문제 https://www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 해결 방법 문제에서 주어진 n이 1,000,000,000,000,000,000 이하의 자연수 반복문을 돌릴 수 없음 결과값은 피보나치 수를 1,000,000로 나눈 나머지이기 때문에 int 형으로도 처리할 수 있음 고민해본 결과, 피보나치 수를 1,000,000으로 나눈 나머지가 언젠가는 반복될 것이라는 생각이 들었음 코딩을 통해 반복되는 수를 찾음 피보나치 1,500,000 번째 숫자를 1,000,000으로 나눈 나머지는 0이었고, 피보나치 1,500,001 번째 숫자를..
[JAVA] 백준 1260 - DFS와 BFS
2022. 8. 18. 20:05
JAVA/백준(BOJ) 문제풀이
DFS, BFS 설명 및 백준 1260번 문제 풀이 https://chb2005.tistory.com/76 [JAVA] DFS, BFS DFS, BFS 란? DFS : Depth First Search의 줄임말로 깊이 우선 탐색을 뜻함 BFS : Breadth First Search의 줄임말로 너비 우선 탐색을 뜻함 다음과 같은 그래프를 탐색한다고 가정 DFS 수행 과정 1번 노드에서 시.. chb2005.tistory.com