수학42 [백준] 10872번 - 팩토리얼 [Java] https://www.acmicpc.net/problem/10872 1. 아이디어 for문을 이용해서 팩토리얼을 구현하는 방식으로 풀었다.2. 문제풀이 정수 N이 12 이하이어서 팩토리얼 값이 int형 범위 이내다.3. 코드 import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); int ans = 1; for (int i = 1.. 2024. 12. 12. [백준] 8393번 - 합 [Java] https://www.acmicpc.net/problem/8393 1. 아이디어 1부터 n까지의 합은 n * (n + 1) / 2 를 활용하면 시간복잡도 O(1)로 해결할 수 있다.2. 문제풀이 합이 int형 범위 이내이므로 그대로 연산해서 출력하는 방식으로 구현했다.3. 코드 import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); Syste.. 2024. 12. 12. [백준] 23756번 - 노브 돌리기 [Java] https://www.acmicpc.net/problem/23756 1. 아이디어 시계 방향으로 돌리는게 최소일때와 반시계 방향으로 돌리는게 최소일때를 구분해서 해결했다.2. 문제풀이 현재 위치에서 노브의 각도와 다음 위치에 해당하는 노브의 각도 차이만큼 돌리는게 기본이다.이때 시계 방향 또는 반시계 방향 둘 중 하나가 최솟값이 되고 돌리는 과정에서 0도 위치를 지나는 경우 단순한 각도 차로 계산하면 오류가 발생한다. 이를 방지하기 위해 각도 차에 360도를 더해서 각도 차를 양수로 만들고 이를 다시 360도로 나누어서 각도 차가 0 ~ 360 이내에 들어오게 하는 방식으로 구현했다.3. 코드 import java.io.*;public class Main { public static void ma.. 2024. 12. 10. [백준] 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. 이전 1 2 3 4 다음
