[BOJ] 17387 : 선분 교차 2(Java)

문제 링크 https://www.acmicpc.net/problem/17387 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 💡 풀이 해당 문제는 CCW라는 기하 알고리즘을 사용합니다. CCW CCW는 Counter-ClockWise의 약어로 평면 위에 놓여진 세 점의 방향관계를 구하는 알고리즘 입니다. 즉, CCW는 점 A, B, C를 순서대로 봤을 때, 부호에 따라 위치관계를 파악할 수 있습니다. CCW 0 := 반시계 방향 CCW는 외적을 이용해서 계산합니다. 하지만, 여기서 CCW에 대해 자세하게 다루..

• format_list_bulleted 알고리즘/BOJ
• · 2024. 2. 27.
• textsms

[BOJ] 14003 : 가장 긴 증가하는 부분 수열 5(Java)

문제 링크 https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 💡 풀이 기존 가장 긴 증가하는 부분 수열 즉, LIS을 응용해야 하는 문제입니다. LIS - DP LIS를 해결하는 가장 간편한 방법은 DP를 이용하는 것입니다. 주어진 숫자 배열에서 인덱스를 한 칸씩 늘려가며 확인하는 방법입니다. 하지만, 이 방법은 2중 반복문을 사용하기 때문에 $O(N^2)$의 시간복잡도를 가집니다. 따라서, 해당 문제는 입력 N의 ..

• format_list_bulleted 알고리즘/BOJ
• · 2024. 2. 8.
• textsms

[BOJ] 1509 : 팰린드롬 분할(Java)

문제 링크 https://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 💡 풀이 기존 팰린드롬 문제와 다이나믹 프로그래밍을 함께 사용하는 문제입니다. 로직은 다음과 같습니다. 문자열의 i번째까지 탐색했을 때의 분할 개수의 최솟값을 `dp[i]`로 나타내겠습니다. 이 `dp[]` 배열 활용해 다이나믹 프로그래밍을 진행합니다. 맨 오른쪽 즉, 문자열의 i번째 인덱스를 기준으로 1 ~ (i - ..

• format_list_bulleted 알고리즘/BOJ
• · 2024. 2. 6.
• textsms

[BOJ] 4386 : 별자리 만들기(Java)

문제 링크 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 💡 풀이 주어진 2차원 점들을 최소 비용으로 이었을 때의 가중치 값을 구하는 문제입니다. 그래프의 정점들을 모두 연결했을 때의 가중치의 최솟값을 구하는 문제이므로, 최소 스패닝 트리(MST)를 사용하면 쉽게 풀이할 수 있는 문제입니다. 최소 스패닝 트리(MST) - Prim 알고리즘 저는 최소 스패닝 트리를 해결하기 위해, Prim 알고리즘을 사용했습니다. 프림 알고리즘은 우선 순위 큐(..

• format_list_bulleted 알고리즘/BOJ
• · 2024. 2. 6.
• textsms

[BOJ] 20303 : 할로윈의 양아치(Java)

문제 링크 https://www.acmicpc.net/problem/20303 20303번: 할로윈의 양아치 첫째 줄에 정수 $N$, $M$, $K$가 주어진다. $N$은 거리에 있는 아이들의 수, $M$은 아이들의 친구 관계 수, $K$는 울음소리가 공명하기 위한 최소 아이의 수이다. ($1 \leq N \leq 30\ 000$, $0 \leq M \leq 100\ 000$, www.acmicpc.net 💡 풀이 중간에 시행착오가 좀 있었지만, Union-Find와 배낭 문제를 이용하면 풀 수 있는 문제입니다. 서로 친구 관계가 있는 아이들끼리 Union-Find를 통해 그룹을 만들어 줍니다. 각 그룹의 인원 수, 그룹의 총 사탕 개수로 이루어진 노드를 만들고 DP를 이용해 얻을 수 있는 최대 사탕 개..

• format_list_bulleted 알고리즘/BOJ
• · 2024. 2. 5.
• textsms

[BOJ] 6603 : 로또(Java)

문제 링크 https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 💡 풀이 49개의 숫자 중 주어진 K개 만큼 수를 골라 그 K개 중 6개로 집합 S를 만드는 문제입니다. 주어진 K개 중 6개를 순서 없이 중복을 허용하지 않고 고르는 경우 즉, $_kC_6$ 인 조합을 구하는 문제입니다. 조합을 구현 할 줄 안다면 간단하게 풀 수 있는 문제입니다. 조합(Combination) 자바에서 조합을 구현하기 위해 재귀를 사용했습니다. 우선, `nu..

• format_list_bulleted 알고리즘/BOJ
• · 2024. 1. 31.
• textsms