PS/Java
-
[백준 20041] EscapingPS/Java 2025. 8. 14.
무한 정수 좌표 평면 위 한 격자 점에 있는 도둑 잡기 게임을 해 보자. 이 도둑을 잡기 위해 N명의 경찰이 도둑이 없는 N개의 다른 격자 점에 배치되어 있다. 도둑 한 명과 N명 경찰들은 서로 한번씩 번갈아 가면서 움직인다. 도둑이 먼저 시작한다. 경찰 차례일 때는 N 명의 경찰 모두가 동시에 움직인다. 경찰과 도둑은 상하좌우 인접한 네 개의 격자 점 중 하나로 이동할 수 있다. 단, 경찰은 그대로 머물러 있을 수 있지만 도둑은 자신의 차례가 오면 반드시 이웃 격자 점으로 이동해야 한다. 이때 경찰과 도둑이 같은 격자 점에서 만나면 도둑은 잡힌 것이 되고 게임은 끝이 난다. 이 게임에서 경찰과 도둑은 최선을 다한다. 즉, 도둑은 최대한 잡히지 않으려는 전략을, 경찰은 최대한 빨리 잡으려는 전략을 쓴다...
-
[백준 13708] 모든 점을 포함하는 원PS/Java 2025. 7. 7.
담금질 기법(Simulated Annealing) 관련해서 글을 읽다가 내용이 기계학습 관련해서 공부했던 경사하강법(Gradient Descent) 과 거의 비슷해서 문제를 찾아보게 되었습니다. 담금질 기법과 경사하강법 두 방법 아무거나 써서 풀 수 있는 문제 중 이 문제를 찾게 되었고담금질 기법에 관련된 코드를 당장 이해하기 힘들어 알고 있던 경사하강법을 적용하게 되었습니다. 경사하강법의 내용을 적어보자면, 특정 구간에서 함수의 기울기를 찾아 이 기울기가 수렴하는 방향으로 각종 파라미터를 변경해 반복적으로 업데이트 하여 근사한 답을 찾아내는 과정입니다. 아래 내용은 https://lighter.tistory.com/389 를 보고 공부하였습니다.1. 특정 점 x, y를 잡고 그 점에서 가장 멀리 떨어..
-
[백준 28277] 뭉쳐야 산다PS/Java 2025. 5. 21.
작은 집합에서 큰 집합으로 합치는 Small-To-Large 입문격? 문제같다구현 자체는 엄청 단순한데 일방적인 방식으로 합쳐버리면 최악의 경우 쿼리당 N개의 원소를 전부 이동해야되서 O(QN)이 걸린다. 극단적인 예시를 들면 문제에서 1 a b는 b의 원소를 a에 합치고 b를 비우는것이라 되어있는데, b의 원소가 N개 있고, a의 원소가 0개 있으면 b에서 a로 가는데 O(N)이 걸린다. 설명하자면S1에 N개의 원소가 전부 들어가 있고 쿼리가 아래처럼1 2 11 3 21 4 3... 1 N N-1오게되면 쿼리마다 계속 O(N)의 시간이 걸리게 되는 것이다. 그래서 나온게 두 집합의 크기를 비교한 후 작은쪽에서 큰 쪽으로만 이동하면 평균 O(QlogN)쯤으로 통과가 가능하다. 그런데 a에 합치고 b를 비..
-
[백준 8462] 배열의 힘PS/Java 2025. 5. 16.
https://www.acmicpc.net/problem/8462 배열의 크기 N과 부분배열의 개수를 묻는 쿼리의 수 T가 주어진다.N과 T가 최대 10만까지이니 일반적인 쿼리로는 처리하기 힘들고 mo's algorithm을 이용해야 한다. 문제에서 요구하는 내용을 이해하는데 좀 걸렸는데 Ks는 부분 배열 안에 있는 자연수 s의 개수이다.부분 배열의 힘이란 모든 자연수 s에 대해서, Ks⋅Ks⋅s를 합한 값이다.처음 읽었을 땐 무슨 말이지? 했다가 계속해서 예제를 분석해보았다.8 34 3 1 1 1 3 1 22 71 63 8예제를 보면2 ~ 7 범위에 해당하는 수가 각각 3 1 1 1 3 1이고 여기서 1의 갯수는 4개, 3의 갯수는 2개니(4 * 4 * 1) + (2 * 2 * 3) = 16 + 12 ..
-
[백준 17469] 트리의 색깔과 쿼리PS/Java 2025. 4. 30.
트리에서 쿼리를 처리하는 문제이다. N개의 정점이 있고 각 정점은 1 ~ N까지의 색깔을 가지고 있다.루트는 항상 1번 정점이고, 트리라고 했으니 간선의 갯수는 항상 N - 1개이다. 쿼리가 들어올 때 두 가지 질문을 한다.1. 두 정점을 끊는다.2. a 정점에서 갈 수 있는 모든 정점을 보았을 때 색깔 종류의 갯수를 출력한다. 이 문제의 조건을 보고 예전에 풀었던 오프라인 쿼리+유니온파인드 관련 문제가 떠올랐다 https://www.acmicpc.net/problem/13306 문제에서는 간선들이 모두 연결되있고 하나씩 끊어서 처리하라고 했지만, 이 순서대로 하면 구현 난이도도 높고 시간복잡도의 크기가 커진다. 그래서 거꾸로 생각을 해 보는 것이다.모든 정점은 서로 연결되어 있지 않고, 두 정점을 끊는..
-
[백준 18917] 수열과 쿼리 38PS/Java 2025. 2. 24.
수열과 쿼리 문제중에 아마 접근 아이디어가 가장 쉬운 문제가 아닐까 싶습니다. 문제 내용은 아주 단순합니다.처음에 0이 하나 포함되어있는 배열 A가 있다. 이때, 다음 쿼리를 수행해야 한다.1 x: A의 가장 뒤에 x를 추가한다.2 x: A에서 x를 제거한다. A에 x가 두 개 이상 있는 경우에는 가장 앞에 있는 하나만 제거한다. 항상 A에 x가 있는 쿼리만 주어진다.3: A에 포함된 모든 원소를 더한 값을 출력한다.4: A에 포함된 모든 원소를 XOR한 값을 출력한다.여기서 봐야할 건 "포함된 모든 원소" 라는 내용입니다. 평소 수열과 쿼리 문제에서 요구하는 건 어떠한 배열이 주어질 때 i ~ j 구간에서 요구하는 합계나 최댓값 등 세그먼트 트리를 이용해야 했습니다. 하지만 모든 원소를 구하라 했으니 ..
-
[백준 13976] 타일 채우기 2PS/Java 2024. 6. 24.
https://www.acmicpc.net/problem/13976 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 타일의 크기가 2칸으로 고정되어 있으므로, N이 홀수일 때는 만들 수 있는 경우의 수가 없다. 2칸을 만드는 경우의 수는 3가지함수로 표현하면 f(2) = [2] 4칸을 만드는 경우의 수는 [2][2] 처럼 3 * 3인 경우 9가지[4] 처럼 2인 경우총 9가지 경우의 수가 나온다함수로 다시 써보면 f(4) = [2]*[2] + [4] 6칸을 만드는 경우의 수는 [2][2][2] 처럼 3 * 3인 경우 27가지[4][2] 처럼 2 * 3인 경우 6가지[2][4] 처럼 3 * 2인 경우 6가지[6]인 경우 2가지총 41가지 경우의 수가 나온다.함수로 다시 써보..
-
[백준 1858] 기울기가 가장 큰 두 점PS/Java 2024. 6. 24.
https://www.acmicpc.net/problem/1858 문제의 조건에서 임의의 두 점을 지나는 직선의 기울기의 절댓값이 가장 큰 두 점을 찾고 싶다. 두 점의 좌표가 (x1, y1), (x2, y2) 라고 할 때, 기울기의 절댓값은 다음과 같은 수식으로 표현된다.| (y2-y1) / (x2-x1) |모든 점의 x좌표는 다르다고 하자. 또한, 모든 점의 y좌표 역시 다르다고 하자. 라는 조건으로 기울기가 가장 크려면 x좌표의 차이가 가장 작아야하고, y좌표의 차이가 가장 커야한다 모든 점의 x, y좌표가 다르니 각 좌표마다 중복되는 점은 없다. x좌표가 1, 1이라면 x좌표가 1, y인 다른 점이 없다는 뜻이다. 그렇게 되면 기울기가 x2 - x1이 0이 되어 기울기를 정의할 수가 없는 것이다...