[JAVA] 백준 25307 - 시루의 백화점 구경
2022. 7. 8. 20:51
JAVA/백준(BOJ) 문제풀이
문제 https://www.acmicpc.net/problem/25307 25307번: 시루의 백화점 구경 첫째 줄에 백화점의 세로 길이, 가로 길이, 마네킹과 떨어져야 하는 거리를 의미하는 정수 $N, M, K$가 공백으로 구분되어 주어진다. ($1 \leq N,M \leq 2\,000$, $0 \leq K \leq 4\,000$) 둘째 줄부터 $N$개의 줄 www.acmicpc.net 해결 방법 시루의 시작 위치에서 의자를 찾는 과정은 BFS를 돌리면 될 것이라 생각함 하지만 문제는 마네킹과의 거리가 K 이하인 곳을 방문하지 않아야 된다는 것 만약 모든 마네킹에서 각각 BFS나 DFS 등을 진행하여 갈 수 없는 곳들을 체크한다 마네킹이 최대 2000 * 2000 개 있을 수 있고 K가 최대 4000이..
[JAVA] 백준 25306 - 연속 XOR
2022. 6. 27. 18:26
JAVA/백준(BOJ) 문제풀이
문제 https://www.acmicpc.net/problem/25306 25306번: 연속 XOR 3에서 5까지의 자연수는 3, 4, 5로, 세 개 존재한다. 세 수를 XOR한 값은 (3 XOR 4) XOR 5 = 7 XOR 5 = 2 이다. www.acmicpc.net 해결 방법 문제에서 주어진 A, B의 범위가 10^18으로 매우 큼 하나씩 XOR 연산을 해서 답을 구하면 시간초과 발생할 것임 따라서 시간을 줄일 수 있는 방법을 찾아야 함 XOR 계산은 두 수가 같으면 0, 다르면 1을 뜻함 계산을 몇번 해보다보니 규칙을 하나 발견함 00 xor 01 xor 10 xor 11 의 결과는 항상 0임 그리고 이 앞에 어떤 수가 붙더라도 1이 짝수개 있기 때문에 0일수 밖에 없음 ex) 101110010..
[JAVA] 백준 20191 - 줄임말
2022. 6. 24. 18:26
JAVA/백준(BOJ) 문제풀이
문제 https://www.acmicpc.net/problem/20191 20191번: 줄임말 문자열 A가 문자열 B의 줄임말이라는 것은 B의 순서를 바꾸지 않고 0 또는 그 이상 개수의 문자를 지워 A를 만들 수 있다는 뜻이다. 정의에 의해서 B는 자기 자신의 줄임말임에 유의하라. 예를 들 www.acmicpc.net 해결 방법 문제에서 주어진 S, T의 길이가 매우 길기 때문에 S * T 방식으로 접근하면 시간초과 발생 문자열 S는 한번씩 돌면서 단어를 찾아야 하기 때문에 여기서는 시간을 줄일 수 없음 따라서 T에서 시간을 줄여야 함 => 이진탐색 사용 입력으로 S = abbcca, T = cbca가 들어왔다고 가정해보자 T의 각 문자별로 위치들을 담고있는 ArrayList 생성 (인덱싱 => a =..
[JAVA] 백준 1405 - 미친로봇
2022. 6. 24. 16:34
JAVA/백준(BOJ) 문제풀이
문제 https://www.acmicpc.net/problem/1405 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자 www.acmicpc.net 해결 방법 n의 범위가 매우 작아서 dfs로 해결 가능 dfs를 통해 모든 경로를 다 가다가 두번째 방문을 한다면 현재까지의 확률을 더해주고 return 이동 경로가 단순할 확률을 출력하라 했으니 위에서 구한 확률을 1에서 빼준 값 출력 코드 import java.util.Scanner; public class p1405 { static int n; static double[] direc..
[JAVA] CCW
2022. 6. 17. 19:48
JAVA/알고리즘 개념 정리
CCW 란? Counter-ClockWise의 줄임말로 평면상의 3개의 점의 위치관계를 판한다는 알고리즘 세 점 A(X1, Y1), B(X2, Y2), C(X3, Y3) 이 있다고 가정했을 때 CCW의 공식은 CCW = ( X1*Y2 + X2*Y3 + X3*Y1 ) - ( X2*Y1 + X3*Y2 + X1*Y3 ) 공식을 따로 외울 필요없이 아래 그림처럼 X1, Y1을 한 번 더 쓴 후, 검은 화살표 곱은 더하고 빨간 화살표 곱은 빼주면 됨 계산된 CCW 값으로는 2가지를 알 수 있음 CCW의 부호에 따라 시계방향, 반시계방향, 일직선의 위치관계에 있는지 파악 가능 CCW 시계 방향 CCW == 0 => 일직선 CCW > 0 => 반시계 방향 CCW의 절대값은 세 점의 벡터의 외적값을 나타냄..
[JAVA] 외판원 순회 문제 (TSP) + 시간초과 해결방법
2022. 6. 16. 14:20
JAVA/알고리즘 개념 정리
외판원 순회 문제(TSP) 란? 모든 도시들 간에 이동비용이 주어졌을 때, 각 도시들을 한번만 방문하고 처음 시작점으로 돌아오는 최소 비용을 구하는 문제 TSP의 핵심 논리는 반복되는 부분을 제거해서 시간복잡도를 줄이는 것 ex) 0, 1, 2, 3, 4, 5 도시가 있다고 생각해보자 모든 도시가 이어져 있을때 모든 경로를 가보려면, 최소 비용을 구하기 위해 (6-1)! = 120개의 경로를 비교해야 함 시간복잡도가 n! 식으로 나오면 n이 13정도만 되어도 1초가 넘어감 시간을 줄일 수 있는 방법을 생각해보자 0->1->2->3->...->0 과 0->2->1->3->...->0 의 상황을 생각해보면 0에서 출발해 1,2,3 도시를 거쳤고 현재 3번 도시에 있는 상황 이 두 상황에서는 4, 5번 도시를..
[JAVA] 세그먼트 트리 (Segment Tree)
2022. 6. 9. 17:31
JAVA/알고리즘 개념 정리
Segment Tree 란? 데이터 집합이 주어지고, 특정 구간의 합, 최대, 최소 값을 구해야하는 문제가 주어짐 이 때, 구간이 여러개이거나 데이터가 업데이트 될 수 있는 상황에서 더 빠르게 찾아내기 위해 고안된 자료구조 Sement Tree 사용 예제 입력으로 5, 2, 4, 3, 1이 들어왔다고 가정 + 업데이트를 반영한 구간합을 출력해야 되는 상황 트리 초기화 입력으로 들어온 5개의 데이터를 모두 리프 노드에 넣어야 됨 리프노드 : 자식이 없는 노드 이런 식의 트리로 만드는게 목표 배열 사용 (루트 노드가 1번, 1번의 자식들이 순서대로 2, 3번, .... index가 8인 위치에 5를 넣어줌, .....) arr[1~15] = [0, 0, 0, 0, 0, 0, 0, 5, 2, 4, 3, 1, ..