공부공간

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 첫 시작점으로 부터 목적지(2) 까지 갈 수 있는지 확인한다 (bfs) 탐색전 마네킹거리(K, 마네킹 좌표에서 bfs로 k번이동하여 갈수있는곳)를 불가능 표시를 해두고 한번만 BFS를 진행하면 해결된다. import java.io.BufferedReader; import java.io.IOException; import ja..

오목/볼록 다각형을 판단하기위한 알고리즘으로 CCW를 사용한다. CCW가 잘 설명되어 있는글은 https://jason9319.tistory.com/358 CCW와 CCW를 이용한 선분 교차 판별 PS에서 종종 이용되는 선분 교차 여부 판별을 CCW를 이용하여 비교적 간단(?)하게 할 수 있는 방법을 소개하려고 합니다. 그 전에 우선 CCW에 대하여 이야기 해보겠습니다. CCW는 Counterclockwise의 약자 jason9319.tistory.com 이글을 판단하면 된다. Z=0인 두 벡터를 연결한다면, 1 > 2 > 3 순서의 ccw값이 ( z=0 인 외적값 ) 양수면 반시계방향에 위치에있다 0이면 일직선상에있다 ( 외적으로 만드는 평행사변형의 넓이값이 0이라는뜻) 음수면 시계방향으로 세점이 위치..

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 XOR연산(결합,교환) 특성에 의해 1-(A-1) 까지와 1-B까지 숫자에 대한 XOR이 A-B까지 XOR이 같게된다. 첫번째 자리를 제외한 비트를 나열해보면, 모두 주기를 띄고있다.( 0011 00001111 ... ) 따라서 2^N으로 비트를 밀면서 해당 번째가 00에속하는지 11에 속하는지 먼저 판단하고, 11영역에 속한다면, 해당 1의 누적개수가 짝수개면 0 홀수개면 1로 비트를 바꾸어준다. import java.io.Buffered..

https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net K개가 될때까지 더하고, 이후에는 K길이 전만큼은 빼주면서 현재 인덱스 값을 더해주며 진행한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static v..

https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net BFS를 통하여 1 2 3 4 5 6 7 8 0 인 경우에 도달할 수 있는지 확인해주자 ArrayList의 Clone() 메소드를 통하여 현재값과 동일한 객체를 쉽게 만들 수 있다. (방문체크용) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.ArrayList; import ..

https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net MCMF(Minimum Cost Maximum Flow)를 위한 SPFA(Shortest Path Faster Algorithm) 공부중 푼문제 1-N 의 정점에서 SPFA를 실행하여 음의 사이클이 있는지 확인한다. SPFA는 벨만-포드 알고리즘과 유사하게 작동하는데, 벨만 포드가 모든 간선에대해서 경로 업데이트를 진행한다면 SPFA는 변화가 있는 노드를 큐에넣고 큐가 더이상 진행되지..

https://www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 매번 가장큰 size를 가진 일반 블록을 찾기위해 NXN을 탐색한다. (사이즈가 같은경우는 무지개 블록이, 무지개블록이 같은경우는 대표블록의 Y,X값을 참조) 해당 블록이 그룹이 되는 조건을 BFS를 진행하며 확인해준다. ( size가 1이면 그룹이 될 수 없다 ) 또한, 점수를 획득할 그룹이 지정되면 반시계반향으로 돌리는 로직과 ( y,x -> 한변의 길이-x,y ) 중력을 받아서 아래로 내..

https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 �� www.acmicpc.net Stack 자료구조를 사용하여 현재까지의 탑의 높이를 저장하여 내 왼쪽의 탑들중 신호를 수신하는 탑을 찾는 문제이다. 수신되는 탑을 찾기위하여 현재까지 저장된 높이가 내높이보다 크면 add연산을 진행하고 작다면 나보다 큰 높이가 나올때까지 poll연산을 진행한다. package algorithm_2022; import java.io.BufferedReader; import java.io.I..