기하19 [백준] 9610번 - 사분면 [Java] https://www.acmicpc.net/problem/9610 1. 아이디어 if else if else 문으로 조건 분기만 잘하면 간단하게 해결할 수 있다.2. 문제풀이 배열을 이용해서 점의 개수를 저장했다.0번 인덱스는 축에 위치하는 점, 1번부터 4번 인덱스에는 1사분면부터 4사분면에 위치하는 점을 저장한 후 StringBuilder로 양식에 맞춰 출력하는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputS.. 2025. 1. 2. [백준] 7869번 - 두 원 [Java] https://www.acmicpc.net/problem/7869 1. 아이디어 두 원이 교차하는 영역의 넓이는 두 원의 위치 관계에 따라 다르게 풀이한다. 두 원의 중심 사이의 거리가 두 원의 반지름의 길이의 합 보다 클 경우 두 원이 교차하는 영역이 없다.(두 원이 바깥에 서로 떨어진 경우)두 원의 중심 사이의 거리가 두 원의 반지름의 차보다 작을 경우 두 원이 교차하는 영역은 작은 원의 넓이와 같다.(한 원이 다른 원을 포함하는 경우)두 원이 두 개의 교점을 가지는 경우에는 두 원이 교차하는 영역의 넓이가 두 원이 만드는 현의 넓이의 합과 같음을 이용한다.2. 문제풀이 두 현을 통해 넓이를 구하는 경우가 아닌 케이스를 먼저 조건으로 처리해줬다. 두 현의 넓이를 통해 교차하는 영역의 넓이를 구하는 .. 2024. 12. 9. [백준] 12781번 - PIZZA ALVOLOC [Java] https://www.acmicpc.net/problem/12781 1. 아이디어 피자를 네 조각으로 나누려면 두 선분이 서로 교차해야한다는 점에서 선분 교차 유형임을 파악하고 CCW 알고리즘을 활용해서 사이 좋게 피자를 나누어 먹을 수 있는지 파악했다.2. 문제풀이 네 점을 A, B, C, D 순서라고 할 때 선분 AC와 선분 BD가 만들어진다.여기서 선분 교차 판정을 하면 되는데 선분 AC에 대해 두 점이 선분의 반대쪽에 있어야 하고, 선분 BD에 대해 두 점이 선분의 반대쪽에 있어야 한다.이를 CCW에 적용하면 벡터 AC와 벡터 AB의 외적, 벡터 AC와 벡터 AD의 외적, 두 외적 벡터의 방향이 반대여야하고, 벡터 BD와 벡터 BA의 외적, 벡터 BD와 벡터 BC의 외적, 두 외적 벡터의 방향이.. 2024. 12. 8. [백준] 10158번 - 개미 [Java] https://www.acmicpc.net/problem/10158 1. 아이디어 개미의 최종 위치를 x좌표와 y좌표를 분리해서 계산해도 똑같다는 점을 활용한다.2. 문제풀이 개미의 x좌표는 가로 길이의 2배만큼 이동했을 때, y좌표는 세로 길이의 2배만큼 이동했을 때 각각 제자리로 돌아온다는 점을 캐치하면 간단하게 해결할 수 있다. 제자리로 돌아오는 것은 (w * 2), (h * 2)로 나누었을 때 몫이므로 최종 위치는 나머지로 구할 수 있다. 이때 나머지가 w, h보다 크면 벽에 한번 더 부딫히는 것까지 고려하면 이를 식으로 세울 수 있어서 삼항 연산자를 활용해서 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { public.. 2024. 12. 6. [백준] 20149번 - 선분 교차 3 [Java] https://www.acmicpc.net/problem/20149 1. 아이디어 두 선분의 교차 여부는 CCW 알고리즘으로 구할 수 있다.2. 문제풀이 기존의 선분 교차 2 문제에서 교점이 하나만 존재할 경우 교점까지 출력하는 문제다.([코딩테스트 준비/백준] - [백준] 17387번 - 선분 교차 2 [Java]) 기존의 코드를 활용하기 위해 교점을 반환하는 메서드만 추가로 작성했는데 이 교점을 반환하는 과정이 상당히 까다로웠다. 먼저 교점이 없으면 null을 반환해서 구분하는 방식으로 구현했고 메서드 시작 부분에 교차하는지 여부를 CCW 알고리즘으로 빠르게 판단했다. 이후 두 선분에 대해 두 선분이 모두 y축에 평행한 경우(기울기가 없는 경우), 한 선분이 y축에 평행한 경우, 나머지 경우로 조건.. 2024. 12. 5. [백준] 17387번 - 선분 교차 2 [Java] https://www.acmicpc.net/problem/17387 1. 아이디어 두 선분의 교차 여부는 CCW 알고리즘으로 구할 수 있다.2. 문제풀이 세 점, 네 점이 일직선 위에 있을 수 있어서 조건 분기가 좀 까다로웠다.먼저 네 점이 일직선 위에 있는 경우, 세 점이 일직선 위에 있는 경우, 나머지 경우로 나누었다. 네 점이 일직선 위에 있는 경우 두 선분이 겹치는 경우가 있는지 판단해야한다. 이때는 각 점의 좌표 관계로 겹치는지 판단할 수 있는데 포함관계일 때, 적당히 겹칠 때, 한 점만 겹칠 때 어떻게 조건을 나눠야 할지 고려해야 한다. 세 점이 일직선 위에 있는 경우에는 CCW에서 기준 벡터가 됐던 선분에 나머지 한 점이 포함되는지 판단하면 된다. 나머지 경우 기존의 선분 교차 1 문제처럼.. 2024. 12. 5. [백준] 17386번 - 선분 교차 1 [Java] https://www.acmicpc.net/problem/17386 1. 아이디어 두 선분의 교차 여부는 CCW 알고리즘으로 구할 수 있다.2. 문제풀이 세 점이 일직선 위에 있는 경우가 없으므로 L1에서 L2의 두 점에 대한 외적 벡터의 방향이 다르고, L2에서 L1의 두 점에 대한 외적 벡터의 방향이 다르면 두 선분이 교차한다는 점을 이용해서 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(Syst.. 2024. 12. 5. [백준] 14215번 - 세 막대 [Java] https://www.acmicpc.net/problem/14215 1. 아이디어 삼각형을 만드려면 가장 긴변이 나머지 두변의 길이의 합 보다 짧아야 한다는 점을 활용했다.2. 문제풀이 막대의 길이를 줄일 수만 있으므로 짧은 두 막대는 그대로 두고 가장 긴 막대의 길이가 나머지 두 막대의 길이의 합보다 짧으면 그냥 사용하고 길면 두 막대의 길이의 합 -1 로 줄이는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputS.. 2024. 12. 5. [백준] 1064번 - 평행사변형 [Java] https://www.acmicpc.net/problem/1064 1. 아이디어 삼각형을 만들 수 있는지 여부는 CCW 알고리즘을 활용해서 구했고, 평행사변형 둘레의 길이의 차의 최댓값은 기존 삼각형의 각 변의 길이를 크기 순으로 a, b, c라고 했을 때, 가장 짧은 둘레의 길이는 2 * (a + b), 가장 긴 둘레의 길이는 2 * (b + c)라는 점을 이용했다.2. 문제풀이 세 점이 한 직선 위에 있으면 삼각형을 만들 수 없으므로 CCW의 값이 0인지 판단하는 방식으로 구현했다.둘레의 길이의 차는 위 수학적 테크닉으로 간단하게 구할 수 있다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void mai.. 2024. 12. 5. [백준] 1027번 - 고층 건물 [Java] https://www.acmicpc.net/problem/1027 1. 아이디어 현재 빌딩에서 특정 빌딩이 보이는지 여부를 CCW 알고리즘을 통해 구한 외적 벡터의 방향으로 알 수 있다는 점을 이용했다.2. 문제풀이 현재 빌딩의 지붕에서 특정 빌딩의 지붕이 보이는지 판단할 때 기준점에 대해 CCW를 통해 방향이 양의 값이면 보이는 빌딩이고 0이면 접하는 빌딩, 음이면 기준점에 가려진 빌딩이라는 점을 이용했다. 기준점은 현재 빌딩에 대해 빌딩의 바닥을 기준으로 하고 보이는 빌딩을 찾으면 해당 빌딩의 지붕으로 옮겨준다.보이는 빌딩에 대해 나중에 해당 빌딩에서 현재 빌딩을 비교할 때도 당연히 보이는 빌딩으로 판단하기 때문에 한번 확인하면 양쪽 모두 보이는 빌딩으로 체크를 해주고, 대신 현재 빌딩에서 오른쪽에.. 2024. 12. 5. [백준] 11758번 - CCW [Java] https://www.acmicpc.net/problem/11758 1. 아이디어 CCW 알고리즘을 구현만 하면 되는 문제로 벡터의 외적을 구하는 ccw 메서드를 작성해서 구현했다.2. 문제풀이 외적 벡터를 구한 이후 -1, 0, 1로 출력하기 위해 삼항 연산자와 절댓값을 구할 수 있는 Math.abs를 활용했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTo.. 2024. 12. 5. [백준] 3009번 - 네 번째 점 [Java] https://www.acmicpc.net/problem/3009 1. 아이디어 나머지 하나의 점의 좌표는 기존에 주어진 점 3개 중 한번만 등장한 좌표의 조합이 된다는 점을 활용했다.2. 문제풀이 주어진 3개의 x좌표, 3개의 y좌표를 각각 배열에 저장한 후 정렬을 해줬다.이후 배열의 가운데 원소와 앞 원소를 비교해서 다르면 앞 원소가 한번만 등장한 것이고 같으면 뒷 원소가 한번만 등장한 것이므로 간단하게 해결할 수 있었다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new B.. 2024. 12. 5. 이전 1 2 다음
