본문 바로가기

알고리즘27

BOJ 17386 선분 교차 1, BOJ 17387 선분 교차 2 해당 문제는 CCW를 통해 해결하는 문제이다.CCW에 대한 자세한 포스트는 카테고리 - 알고리즘 종류에서 확인 가능하다. CCW를 통해 어떻게 해결 할 수 있는지 확인해보자. 선분은 교차하는 경우와 교차하지 않는 경우로 가볍게 구분할 수 있다.각각의 방향을 따져보자. 교차하는 경우 CCW(A,B,C)는 음수 CCW(A,B,D)는 양수를 갖게 될 것이다.또 CCW(C,D,A)는 양수, CCW(C,D,B)는 음수를 갖게 될 것이다. 즉, 한 선분을 기준으로 다른 선분의 끝 점이 서로 다른 부호를 가지고 있으면 교차한다고 판단 할 수 있는 것이다. 간단히 선분 AB만 예시로 보자.그림과 같이 교차하지 않는 경우 CCW(A,B,C)와 CCW(A,B,D)는 무조건 같은 방향을 보게 될 것이다. 우리는 이제 C.. 2025. 6. 30.

CCW (Counter Clock Wise) 세 점의 방향성을 판단하는 기하학적 문제 CCW 값에 의해 세 점이 어느 방향으로 향하는지 알 수 있다. 공식은 아래와 같다.CCW(A, B, C) = (B.x - A.x) × (C.y - A.y) - (B.y - A.y) × (C.x - A.x)결과 값에 따라 양수: 반시계방향, 음수: 시계 방향, 0: 일직선을 나타낸다. CCW가 어떻게 도출되는지 알아보자.좌측 그림과 같은 좌표를 가진 세 점이 있을 때, A를 원점으로 C와 B의 벡터를 구하면 오른쪽 그림과 같이 된다. 공식은 아래와 같다.A' = (0, 0) ← A에서 A를 뺀 것B' = (bx - ax, by - ay) ← B에서 A를 뺀 것 (6, 2) 이라고 가정C' = (cx - ax, cy - ay) ← C에서 A를 뺀 것 (7, 3) 라.. 2025. 6. 30.

BOJ 1106 호텔 https://www.acmicpc.net/problem/1106 유명한 배낭 문제이다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;public class Main { static class Info { int cost; int additionalCustomers; public Info(int cost, int additionalCustomers) { this.cost = cost; this.additionalCustomers = additionalCustomers; } } .. 2025. 6. 28.

Unbounded Knapsack (무한 배낭) 중요 키워드:"각 물건을 무한개 선택 가능""같은 물건을 여러 번 사용""동전 교환", "최소 개수"시간 복잡도: O(nW)핵심 아이디어:dp[w] = 무게 w에서 최대 가치 (같은 물건 재사용 가능) public class UnboundedKnapsack { // 최대 가치 구하기 public static int maxValue(int W, int[] weights, int[] values) { int[] dp = new int[W + 1]; for (int i = 0; i 2025. 6. 28.

[BOJ 9252] LCS2 문제 정리LCS(Longest Common Subsequence, 최장 공통 부분 수열) 문제두 수열이 주어진다.부분 수열을 찾는다.그 중 가장 긴 것을 찾는다.예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.LCS의 길이와 LCS를 출력한다.제한 사항0.1s, java11: 0.4s각 수열 = 최대 1000글자LCS가 0인 경우, 길이만 출력핵심 포인트LCS를 naive하게 찾아보자.A 수열과 B 수열이 있을 때, B 수열로 A 수열의 LCS를 찾는다면 O(N^3)이 발생한다.B 수열의 각 글자를 첫 부분 수열의 글자로 생각하고 찾는다면 1000 글자에 대해 각 각 1000 - i 글자 수를 연산해야 된다. (N^2)각 N^2의 부분 수열의 글자가 A 수열에 있는지 확인해야한다. (N.. 2025. 4. 8.

[BOJ 17406] 배열 돌리기 4 문제 정리배열의 최솟값을 구한다.배열의 최솟값은 각 행의 모든 원소의 합 중 가장 작은 값이다.배열이 주어지면 k번의 회전을 한다.각 회전은 r, c, s 값으로 회전한다.(r-s, c-s) 부터 (r+s, c+s) 까지 시계 방향으로 회전한다.회전 연산이 두 개 이상이면, 연산을 수행한 횟수에 따라 최종 배열이 달라진다.제한 사항3 ≤ N, M ≤ 501 ≤ K ≤ 61 ≤ A[i][j] ≤ 1001 ≤ s1 ≤ r-s 1 ≤ c-s 핵심 포인트다른 연산이 존재하므로 백트래킹백트래킹으로 구할 수 있는 모든 연산 과정이 적으므로 완전 탐색 가능배열 회전의 최종 결과로 최종 배열을 획득 할 수 있으므로 가지치기 필요 없음.배열 회전에 대한 구현력 필요핵심 로직백트래킹을 통해 다른 경우에 대한 회전 상태 저.. 2025. 4. 3.

[BOJ 1826] 연료 채우기 문제 정리트럭으로 마을까지 이동 중 1KM를 이동 할 때마다 1L의 연료가 빠져 나가는 상황이동하는 곳곳에 N개의 주유소가 존재트럭은 충전 할 때 마다 연료를 충분히 충전할 수 있음.각 각의 주유소 위치와 연료의 양이 주어 질 때, 최소한으로 충전하는 횟수 구하기마을에 도착할 수 없는 경우 -1제한 사항 제한사항 1: 주유소 개수 1 제한사항 2: 주유소 위치 1 제한사항 3: 주유소 연료 1 제한사항 4: 현재 위치에서 마을까지 거리 1 제한사항 5: 현재 트럭의 연료량 1 핵심 키포인트충분히 많이 충전 -> 한 번에 최대한 많은 이익, 그리디의 핵심핵심 포인트거리와 연료 중 어느 것을 포커스로 두어야하는가?의심해야 할 포인트 1: 가장 많은 연료를 얻는 것이 좋은가?의심해야 할 포인트 2: 가장 멀리.. 2025. 3. 31.

[BOJ 20207] 달력 문제 정리날짜가 1일 ~ 365일로 표시되어 있는 달력을 가지고 있음.올해 일정을 모두 계획해서 달력에 표시함.날씨로 인해 달력에 표시한 일정 중 일부가 지워지려고 함.방지하기 위해 일정이 있는 곳에만 코팅지를 달력에 붙이려고 함.너무 귀찮은 탓에 아래와 같은 규칙을 따라 코팅지를 붙이려고 한다.연속된 일정을 모두 감쌀 수 있는 가장 작은 직사각형의 코팅지를 만들어 붙인다.연속된 두 일자에 각 각 일정이 1개 이상있다면, 연속된 일정이다.연속된 모든 일정은 하나의 직사각형에 포함되어야 한다.달력은 아래와 같은 규칙을 따른다.일정은 시작 날짜와 종료 날짜를 포함한다.시작일이 가장 앞선 일정부터 차례대로 채워진다.시작일이 같은 경우 일정의 기간이 긴 것부터 채워진다.일정은 가능한 한 최 상단에 배치된다.일정.. 2025. 3. 31.

[MST] 최소 스패닝 트리 - 크루스칼(Kruskal), 프림(Prim) MST란? 최소 신장 트리(Minimum Spanning Tree)로 가중 그래프(Weight Graph)에서 가장 적은 비용(Weight)으로 모든 정점(Vertex)으로 이동할 수 있는 부분 그래프(Sub Graph)이다. MST는 각 정점에서 정점 사이에 하나의 간선(Edge)만 필요하므로 총 N-1 개의 간선을 가지게 되므로 마치 트리의 형태를 하고 있어서 트리라는 이름이 붙는다.크루스칼 알고리즘 1. 모든 간선을 비용이 적은 순서를 기준으로 정렬한다. - Sort2. 간선에 붙은 정점 u와 v를 기준으로 부모를 찾는다. - Find3. 정점 u의 부모와 정점 v의 부모가 다르다면 서로 다른 집합에 속해있지만, 1번 과정으로 인해 해당 간선이 두 정점의 최소 비용의 간선임을 알 수 있으므로 하나의.. 2024. 7. 11.

이전 1 2 3 다음

티스토리툴바