[JAVA] 백준 2098 - 외판원 순회
2022. 8. 18. 19:56
JAVA/백준(BOJ) 문제풀이
TSP 알고리즘 설명 및 백준 2098번 문제 풀이 https://chb2005.tistory.com/86 [JAVA] 외판원 순회 문제 (TSP) + 시간초과 해결방법 외판원 순회 문제(TSP) 란? 모든 도시들 간에 이동비용이 주어졌을 때, 각 도시들을 한번만 방문하고 처음 시작점으로 돌아오는 최소 비용을 구하는 문제 TSP의 핵심 논리는 반복되는 부분을 제거 chb2005.tistory.com
[JAVA] 백준 17387 - 선분 교차 2
2022. 8. 18. 19:54
JAVA/백준(BOJ) 문제풀이
CCW 설명 및 백준 17387번 문제 풀이 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] 백준 2110 - 공유기 설치
2022. 8. 18. 19:24
JAVA/백준(BOJ) 문제풀이
문제 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 해결 방법 일단 문제를 이해하는 것도 조금 헷갈려서 문제부터 정리해 봄 집 주소로 [1, 2, 4, 8, 9]가 들어오고 공유기 개수가 3개로 들어왔을 때 왜 정답이 3일까? 최대 거리가 1이라면 => [1, 2, 4, 8, 9] 5개의 집에 공유기를 설치해야 됨 최대 거리가 2라면 => 1번집에 공유기를 설치하면 2번집에는 설치하지 않아도..
[JAVA] 백준 11062 - 카드게임
2022. 8. 16. 22:04
JAVA/백준(BOJ) 문제풀이
문제 https://www.acmicpc.net/problem/11062 해결 방법 DP 알고리즘을 사용해서 풀어야 함 먼저 뽑는 근우를 playerA라 하고, 나중에 뽑는 명우를 playerB라고 하고 dp[ i ][ j ] = i ~ j 번째 카드가 남았을 때 playerA의 최대값으로 가정하면 dp[ 1 ][ n ]이 정답이 됨 1장 남았을 때부터 n장 남았을 때까지 거꾸로 생각해보자 dp[ i ][ j ]를 구하려면 dp[ i + 1 ][ j ]와 dp[ i ][ j - 1 ] 값을 알아야 함 ex) 2 4번째 카드가 남았다면 => 3 4번째 카드가 남은 상태에서 2번째 카드를 고른 경우와 2~3번째 카드가 남은 상태에서 4번째 카드를 고른 경우 위 2가지 경우를 고려 dp 배열은 playerA의..
[JAVA] 백준 12920 - 평범한 배낭 2
2022. 8. 16. 18:43
JAVA/백준(BOJ) 문제풀이
문제 https://www.acmicpc.net/problem/12920 12920번: 평범한 배낭 2 첫 번째 줄에 N, M (1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000) 이 빈칸을 구분으로 주어진다. N은 민호의 집에 있는 물건의 종류의 수이고 M은 민호가 들 수 있는 가방의 최대 무게다. 두 번째 줄부터 N개의 줄에 www.acmicpc.net 해결 방법 평범한 배낭 문제 푸는 방법을 안다고 가정 ( 평범한 배낭 문제 풀이 => https://chb2005.tistory.com/158 ) 평범한 배낭 문제와 유사하지만 물건들의 갯수가 1개 고정이 아닌 최대 10000개 까지 있을 수 있음 따라서 다른 해결책이 필요함 만약 물건1(무게:1, 가치:1)의 개수가 15개라고 가정해보자 처음 생각했..
[JAVA] 백준 12865 - 평범한 배낭
2022. 8. 16. 16:47
JAVA/백준(BOJ) 문제풀이
Knapsack 알고리즘 설명 및 백준 12865 문제 풀이 https://chb2005.tistory.com/158 [JAVA] Knapsack 알고리즘 ● Knapsack 알고리즘 이란? Knapsack은 배낭이란 뜻으로, Knapsack 알고리즘은 배낭 알고리즘 이라고도 불림 Knapsack 알고리즘은 DP의 일종으로 배낭 채우기 문제에서 유래되었음 배낭 채우기 문제란 배 chb2005.tistory.com
[JAVA] 백준 1238 - 파티 ( Reverse Dijkstra )
2022. 8. 16. 14:24
JAVA/백준(BOJ) 문제풀이
문제 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 해결 방법 n개의 노드가 주어지고 모든 노드에서 노드 X로 갔다 오는 최단 거리를 구해야 함 모든 노드 -> 노드 X + 노드 X -> 모든 노드 와 같이 2부분으로 나누어 생각해 봄 노드 X -> 모든 노드의 최단 경로는 다익스트라 알고리즘을 사용 ( 다익스트라 -> https://chb2005.tistory.com/78 ) 모든 노드 -> 노드 X로 가는 최..