ETC
-
[백준/JAVA] 14888번 연산자 끼워넣기 - BruteForce, 백 트랙킹ETC/Algorithm 2023. 6. 9. 09:21
문제 풀이 DFS를 재귀형식으로 구현하여, 모든 연산자의 경우의 수로 계속 반복하고 마지막 연산이 될 경우 값을 저장하여 최대 최소를 비교하였다. 한번의 재귀가 끝나면 진행되었던 연산자의 개수는 복구시켜야 다른 재귀가 영향을 받지 않는다. 코드 제출 코드 import java.io.; import java.util.; class Main { static int MAX = Integer.MIN_VALUE; static int MIN = Integer.MAX_VALUE; static int N; static int[] arr; static int[] ops; public static void main(String[] args) throws IOException { BufferedReader br = new ..
-
[백준/JAVA] 11726번 2xN 타일링 - DPETC/Algorithm 2023. 6. 9. 09:13
문제 2xN의 타일을 채워라 세로로 2칸, 가로로 2칸인 타일을 통해 2*N의 타일을 채우는 문제이다. 풀이 조건 1007로 나눈 나머지를 저장해야한다. DP 미리 값을 저장해두고 원하는 값을 불러오면 된다. 점화식 설정 경우의 수를 모두 작성해보고 규칙을 찾아보면 앞의 2개의 합이 지금의 값과 같다. 따라서 점화식은 dp[n] = dp[n-1] + dp[n-2] 이다. 즉, 점화식 시작은 3부터 시작한다. 코드 제출 코드 import java.io.*; class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System...
-
[백준/JAVA] 11758번 CCW - 기하학ETC/Algorithm 2023. 6. 9. 09:03
문제 CCW(Counter Clock Wise) 알고리즘 기하학을 마스터 한 것이 아니라 https://snowfleur.tistory.com/98 에서 참고하여 풀이하였다. 코드 제출 코드 import java.io.*; import java.util.*; class Main { static int[][] arr = new int[3][2]; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.o..
-
[백준/JAVA] 20365번 블로그2 - 그리디 알고리즘ETC/Algorithm 2023. 5. 30. 22:04
문제 내용 주어진 문제는 위와 같다. 이번 문제의 힌트는 이미 주어져 있다. 힌트는 다음과 같다. 즉, 칠하는 일이 귀찮으니 최소 작업 횟수를 구하는 방법이다. 풀이 일단 가장 많이 칠해야 하는 색깔을 붓는다고 생각하고, 적은 색깔을 일일이 칠해주는 경우가 최소 경우일 것이다. 구하는 방법은 다음과 같다. 입력 받을 때 중복을 제거한다. ex) BB RRR B RR B => B R B R B 로 변환해서 저장한다. 이렇게 했을 때 가장 적은 색깔을 찾는다. 같아도 상관 없다. 색깔이 칠해질 값에 + 1을 한 값이 답이다. 코드 코드 설명 배열의 중복이 삭제되면 크기가 어느정도 일지 모른다. 따라서 ArrayList로 중복이 제거된 배열을 선언한다. 첫 시작값은 직접 세어주고 이후 값부터는 반복문을 통해 ..
-
[백준/JAVA] 3009번 네 번째 점 - 기하학, 구현ETC/Algorithm 2023. 5. 30. 21:55
문제 내용 세 점이 주어지고, 축에 평행한 직사각형을 만들기 위해 필요한 네 번째 점을 찾는 문제이다. 풀이 축에 평행하다는 X축 Y축 각각 2개의 동일한 값의 점이 있기 때문에 평행한 축이 생성된다는 의미이다. 간단히 각각 X,Y축 좌표 중에서 1번만 정의된 값이 네 번째 점이다. 코드 코드 설명 비트 마스킹을 사용한 방법과, 카운팅 정렬을 사용한 방법 2가지가 있다. 제출 코드 (비트 마스킹) import java.io.*; import java.util.*; class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(Sy..
-
[백준/JAVA] 9095번 1, 2, 3 더하기 - Dynamic ProgrammingETC/Algorithm 2023. 5. 30. 21:49
문제 내용 정수 N이 주어질 경우 1,2,3의 합으로 나타내는 전체의 경우의 수를 구하는 문제이다. 주의 1+1+2와 2+1+1은 다른 경우이다. 최소 하나 이상의 수를 사용해야한다. 풀이 단순하게 dp배열을 선언한 후 숫자 3 까지 세어본 후 규칙을 찾는다. dp[1] = 1 dp[2] = 2 dp[3] = 4 dp[4] = 7 여기서 dp[5]까지 해봤다면 매우 귀찮았을 것이다. 그래도 5까지 구하고 나면 dp[5] = 13 이 나올 것이다. dp[n] = dp[n-1] + dp[n-2] + dp[n-3] 이라는 점화식이 보인다. 이를 바탕으로 7까지 세어 봤을 때 올바르게 44까지 나오게 된다. 코드 코드 설명 점화식의 시작은 4부터 시작한다. 초기값을 선언해준다. dp[n] = dp[n-1] + ..
-
[백준/JAVA] 11758 CCW - 기하학ETC/Algorithm 2023. 5. 30. 21:41
문제 CCW 이번 문제는 CCW(Counter Clock Wise)알고리즘 문제이다. 점이 세 개 있을 때, 이 점들을 순서대로 이은 직선의 방향을 찾는 문제다. 코드 코드 설명 입력된 점을 순서대로 A, B, C라 했을 때 점 A부터 점 B까지의 벡터를 AB 점 B부터 점 C까지의 벡터를 BC라 했을 때, 벡터 AB와 BC를 외적을 진행한 값이다. 제출 코드 import java.io.*; import java.util.*; class Main { static int[][] arr = new int[3][2]; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new Input..
-
[백준/JAVA] 2839 설탕 배달 - Dynamic ProgrammingETC/Algorithm 2023. 5. 29. 16:28
문제 3kg, 5kg 봉지가 있을 때, 더 적은 수의 봉지를 챙길 수 있는 방법을 찾는 것 풀이 규칙을 찾아야 한다. 1부터 25쯤 까지 3kg 봉지와 5kg 봉지의 개수를 각각 적어서 나열보면 3kg 미만인 1kg, 2kg은 절대로 불가능한 경우이다. 4kg과 7kg또한 절대 불가능 경우다. 5의 배수의 경우 ( N % 5 == 0 일 경우 ) N/5 개 만큼의 봉지수를 챙긴다. N % 5 == 1 의 경우 2 + ( a - 1 ) = a + 1 N % 5 == 2 의 경우 4 + ( a - 2 ) = a + 2 N % 5 == 3 의 경우 1 + a = a + 1 N % 5 == 4 의 경우 3 + ( a - 1 ) = a + 2 규칙성을 찾을 수 있다. 코드 코드 해석 절대 불가능한 경우 + N이 ..