본문 바로가기

코딩테스트 준비664

[백준] 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.
[백준] 1085번 - 직사각형에서 탈출 [Java] https://www.acmicpc.net/problem/1085 1.  아이디어 직사각형 각 변까지의 거리 중 최솟값을 찾는 문제로 좌우 이동에 대한 최솟값과 상하 이동에 대한 최솟값을 구해서 최종 최솟값을 구하는 방식으로 구현했다.2. 문제풀이 경계까지 가는 최솟값은 쭉 한 방향으로 가는 것이므로 4가지 경우만 따지면 된다.Math.min 메서드를 이용해서 한 줄로 간단하게 풀이했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new Input.. 2024. 12. 5.
[백준] 14681번 - 사분면 고르기 [Java] https://www.acmicpc.net/problem/14681 1.  아이디어 좌표의 부호로 사분면을 구분할 수 있다는 점을 활용하면 간단하게 해결할 수 있다.2. 문제풀이 x좌표와 y좌표의 부호에 맞게 조건문 분기처리를 해서 해결했다.3. 코드 import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int x = Integer.parseInt(br.readLine()); int y = Integer.parse.. 2024. 12. 5.
[백준] 10610번 - 30 [Java] https://www.acmicpc.net/problem/10610 1.  아이디어 30의 배수는 3의 배수면서 10의 배수라는 점을 활용하면 간단하게 해결할 수 있다.3의 배수는 각 자릿수의 합이 3의 배수가 되고 10의 배수는 1의 자릿수가 0이라는 특징이 있는데 이 두가지를 모두 만족하면 30의 배수가 된다.2. 문제풀이 각 자릿수를 저장하는 배열 nums, 0을 포함했는지 판단하는 변수 hasZero, 각 자릿수의 합을 저장하는 변수 sum을 선언하고 입력에 맞게 초기화해준다.이후 0을 포함하면서 각 자릿수의 합이 3의 배수면 재배치로 30의 배수가 될 수 있으므로 nums를 정렬한 이후 역순으로 순회하며 가장 큰 수를 구해주고 30의 배수가 아니면 -1을 출력하는 방식으로 구현했다.3. 코드 i.. 2024. 12. 4.
[백준] 10250번 - ACM 호텔 [Java] https://www.acmicpc.net/problem/10250 1.  아이디어 문제 설명이 약간 어려운데 간단하게 101, 201, 301, 401, ..., 102, 202 이렇게 채워나가면 된다.한칸씩 이동하며 찾아도 되지만 몫과 나머지의 특성을 잘 활용하면 O(1)로 구할 수 있다.2. 문제풀이 N번째 손님에 대해 층은 N % H, 방은 N / H 로 계산할 수 있다.손님과 층, 방 모두 1번부터 시작하므로 보정으로 N을 N - 1, 층을 N % H + 1, 방을 N / H + 1로 바꾸면 답을 구할 수 있고 방은 10호 보다 작을 때는 앞에 0을 붙여야 하는 점만 조건문으로 처리하면 된다.3. 코드 import java.io.*;import java.util.*;public class Mai.. 2024. 12. 4.
[백준] 15965번 - K번째 소수 [Java] https://www.acmicpc.net/problem/15965 1.  아이디어 에라토스테네스의 체로 소수 리스트를 미리 구하고 인덱스로 찾는 방식으로 구현했다.자연수가 최대 500,000으로 주어졌는데, 50만번째 소수가 1000만 이하 범위에 있는 점으로 좀 더 간편하게 구현했다.2. 문제풀이 에라토스테네스의 체로 소수 여부를 먼저 판정을 하고 해당 결과로 소수 리스트를 구했다.K번째 소수는 소수 리스트에서 K-1 인덱스에 위치한다는 점을 이용하면 간단하게 구할 수 있다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { .. 2024. 12. 4.
[백준] 1735번 - 분수 합 [Java] https://www.acmicpc.net/problem/1735 1.  아이디어 두 분수의 합을 기약분수로 만드려면 통분 이후 유클리드 호제법으로 약분을 하면 간단하게 해결할 수 있다.2. 문제풀이 통분으로 두 분수의 덧셈을 먼저 해주고 분자, 분모의 최대 공약수로 분자, 분모를 나눠주는 방식으로 구현했다.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)); BufferedWrit.. 2024. 12. 4.
[백준] 9613번 - GCD의 합 [Java] https://www.acmicpc.net/problem/9613 1.  아이디어 GCD의 쌍은 유클리드 호제법을 활용하면 간단하게 구할 수 있다.2. 문제풀이 중복이 가능하기 때문에 반복문에서 유클리드 호제법으로 최대 공약수를 반복해서 구하면 간단하게 해결할 수 있다.이때 최대 공약수의 합은 int형 오버플로우가 발생할 수 있는 점에 주의해야 한다.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.i.. 2024. 12. 4.
[백준] 12779번 - 상품 is 뭔들 [Java] https://www.acmicpc.net/problem/12779 1.  아이디어 약수의 개수가 홀수인 숫자는 제곱수라는 점을 활용한다.2. 문제풀이 4, 9, 16 같은 제곱수만 약수의 개수가 홀수가 되므로 해당 범위에 포함된 제곱수를 찾은 후 유클리드 호제법으로 기약분수로 출력하는 방식으로 구현했다.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)); BufferedWriter.. 2024. 12. 3.
[백준] 9506번 - 약수들의 합 [Java] https://www.acmicpc.net/problem/9506 1.  아이디어 완전수인지 아닌지의 여부를 판단하는 문제로 일일이 약수들을 더해서 완전수가 되는지 판단하고 형식에 맞게 출력하는 방식으로 간단하게 구현했다.2. 문제풀이 1부터 N 이전까지 모든 수로 나누어보며 약수들을 리스트에 담아주고 완전수가 되는지 판단했다.이후 StringBuilder를 활용해서 완전수일 때와 완전수가 아닐 때 형식에 맞게 출력하는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br =.. 2024. 12. 3.

티스토리툴바