전체 글
-
[백준/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이 ..
-
[백준/JAVA] 1463번 1로 만들기 - Dynamic ProgrammingETC/Algorithm 2023. 5. 27. 23:48
문제 3가지 방법 3으로 나눠지면 3으로 나누고 2로 나눠지면 2로 나누고 위의 2 방법이 안되면 1빼기 풀이 주의점 최소 연산 횟수를 구하기 위해 큰 수를 먼저 나누면 안된다. ex) 10 (2나누기) -> 5 (1빼기) -> 4 (2나누기) -> 2 (1빼기) -> 1 원하는 계산이 안된다. 예시 점화식의 시작은 2부터이다. 배열 arr[0] = arr[1] = 0으로 초기화 후 시작한다. arr[2]의 경우 2로도 나눠지지만 문제에서 1보다 큰 값이 N으로 주어지므로, 1을 뺀 값에 1을 더하여 값을 저장한다. arr[3]의 경우 3으로도 나눠진다. 여기서 Math.min(arr[i], arr[i / 3] + 1)이 사용된다. 둘 중 최솟값을 1을 더하여 저장한다. arr[6]의 경우 2와 3 둘 ..
-
[백준/JAVA] 2206 벽 부수고 이동하기ETC/Algorithm 2023. 5. 27. 01:45
문제 문제 인식 변수 상황 N * M의 행렬로 표현되는 맵이 있고, 0은 이동가능 1은 이동 불가능한 벽으로 표현된다. 이동은 (1,1)에서 시작하며, 도착점은 (N,M)으로 고정되어있다. 하지만 변수 상황이 주어지는데 간단히 기존 BFS 문제에서 벽을 한번은 통과할 수 있다는 것이다. 그렇다면 다른 BFS 문제와 형태는 같지만 벽을 한 번 통과 가능하다는 점을 어떻게 구현할 것인가가 문제의 핵심으로 인식했다. 실패한 문제 해결 처음 생각한 방법은, BFS를 재귀를 통해 다시 불러오는 방식을 생각하였다. 첫 시작은 벽 부신 값을 false로 갖고 시작 재귀를 통해 한번 벽을 부셨다면 true 값을 주고 반복하여 진행하였다. 여기서 문제가 발생하는데, 벽을 한번 부신 경우가 그냥 정상적인 길로 가도 거리 ..
-
[Spring Boot] @RestController와 @ContollerSpring/Study 2023. 5. 26. 21:20
서론 Spring Boot에서 중요한 컨트롤러를 구현할 때 사용되는 두 가지 어노테이션 @RestController와 @Controller에 대하여 간략히 정리하겠다. @Controller @Controller 어노테이션은 해당 클래스가 컨트롤러의 역할을 하도록 스프링에게 알려주는 역할을 한다. 이를 통해 프런트컨트롤러 (Dispatcher Servlet)가 해당 클래스를 사용하여 요청을 처리하며, 일반적으로 뷰에 대한 정보를 전달하는 용도로 사용된다. 메소드에 @ResponseBody 어노테이션이 없다면, 값을 리턴할 때 문자열로 리턴되어 View의 이름으로 매칭되어 실행된다. @RestController @RestController는 @Controller와 @ResponseBody 어노테이션의 조합버..