분류 전체보기
[백준] 11066 파일 합치기 - Java
[백준] 11066 파일 합치기 - Java
2022.07.08언뜻 봐서는 파일들을 정렬한 후 그리디 느낌으로 풀어낼 수 있을 것 같지만.. 연속된 경우만 파일을 합칠 수 있다는 조건 때문에 그리디로는 풀 수 없다. 가능한 경우를 모두 탐색하는 방법은 시간이 너무 많이 걸리니.. dp를 사용해야 한다. 우선 i와 j를 설정하자. i는 시작, j는 끝을 의미하고 이차원 배열로 저장한다. dp[i][j] 는 i에서 j까지 파일을 합칠 때 소비되는 최소 비용을 의미한다. 위의 배열을 잘 채워넣은 후 dp[1][j-1]의 값을 답으로 사용하자. 공통점을 찾아보자. 항상 하던대로 "마지막에 어떻게 합치는가?"를 기준으로 구분할 수 있을 것 같다. import java.util.*; import java.io.*; public class Main{ public static v..
[백준] 1418 K-세준수 - Java
[백준] 1418 K-세준수 - Java
2022.07.02에라토스테네스의 체를 이용해서 푸는 방식인데.. 문제에 맞게 잘 변형해서 푼 풀이를 가져와서 공부했다. 원래 방식대로면 시간 초과가 나기 쉬운데 상황에 알맞게 잘 변형해서 푼 좋은 풀이인 것 같다. 공부하자.. import java.util.*; import java.io.*; import java.math.*; 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 K = Integer.parseInt(br..
[백준] 2579 계단 오르기 - Java
[백준] 2579 계단 오르기 - Java
2022.06.29dp배열에는 해당하는 계단을 밟을 때 얻을 수 있는 최대 점수가 들어간다. 세 번 연속으로 계단을 올라가면 안되는 조건이 있기에 dp배열을 두 개 생성해서 하나는 바로 전 계단을 밟은 배열, 나머지는 바로 전 계단을 밟지 않은 배열으로 설정해서 얻을 수 있는 점수의 최댓값을 구하자. import java.util.*; import java.io.*; import java.math.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br..
[백준] 1463 1로 만들기 - Java
[백준] 1463 1로 만들기 - Java
2022.06.29dp문제이다. 초기값으로 1과 2를 설정해주고, dp배열을 채워서 풀 수 있다. 이 때, 항상 3으로 나누는게 가장 좋은 방법이 아닐 수 있다. 2로 나누기, 1빼기 세 가지를 모두 고려해서 dp배열을 채우자. import java.util.*; import java.io.*; import java.math.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int dp[] = new int[1000001]; dp[1] = 0; dp[2] = 1; for(int i=3; i
Dynamic Programming
Dynamic Programming
2022.06.29문제의 크기를 변화시켜 작은 문제의 결과를 이용해 큰 문제의 정답을 계산하는 알고리즘이다. 우선은 완전탐색으로 풀 수 있는지 확인하고, 시간을 줄일 때 다이나믹 프로그래밍 방법을 적용하는걸 고려해 보자. 1. 작은 문제 정의하기 전체 문제를 바탕으로 좀 더 쉽게 구할 수 있는 작은 문제를 정의한다. 2. 검증 작은 문제가 전체 문제를 해결할 때 도움이 되는지 확인한다. 3. 정의한 작은 문제를 해결할 때 사용되는 초기값을 설정하자. 몇 가지 값들은 쉽게 구할 수 있다. 4. 규칙을 찾아 점화식을 작성한다. 초기값을 이용해 값들의 규칙을 찾고, 이를 식으로 표현해 모든 값들에 대해 답을 얻는다. 5. 큰 문제 해결하기 여기서 점화식을 작성하는게 까다로운데.. 유형이 그렇게 다양하지 않다. 여러 문제를 풀어..
[백준] 16928 뱀과 사다리 게임 - Java
[백준] 16928 뱀과 사다리 게임 - Java
2022.06.28"최단거리를 구해라" 라는 발문과 그래프 느낌이 나는 문제를 만나면 BFS를 돌리면서 카운트 배열을 채우는 생각을 해 보자. 이런 유형이 많이 나오니.. 반복해서 풀어서 익숙해져야겠다. import java.util.*; import java.io.*; import java.math.*; public class Main { static int N, M; static int count[] = new int[101]; static int[] object = new int[101]; static boolean visit[] = new boolean[101]; public static void main(String[] args) throws IOException { BufferedReader br = new B..
[백준] 1931 회의실 배정 - Java
[백준] 1931 회의실 배정 - Java
2022.06.27그리디 문제에는 정렬이 따라오는 경우가 많다. 정렬의 기준을 뭐로 설정할지가 매우 중요하다. 이 부분에 대해 고민해보자. 이 문제의 경우는 끝나는 시간을 오름차순으로 정렬하고, 같다면 시작 시간을 오름차순으로 정렬해야 한다. import java.util.*; import java.io.*; import java.math.*; 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()); Time[] arr = new Ti..
[백준] 1753 최단경로 - Java
[백준] 1753 최단경로 - Java
2022.06.27그래프를 입력받고 다익스트라 알고리즘을 돌려서 풀 수 있는 문제이다. 다익스트라 알고리즘을 알고 구현할 수 있으면 풀 수 있는 문제라서.. 더 설명할 건 없다. import java.util.*; import java.io.*; import java.math.*; public class Main { static int N, M, start; static int[] dist; static ArrayList[] edge; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new Str..
최단 거리
최단 거리
2022.06.27BFS와 다익스트라 알고리즘을 통해 그래프에서 특정 노드까지의 최단 거리를 구할 수 있다. BFS를 통해 계산하는 경우는 한 번 이동할 때 카운트를 하나씩 늘려가면 되고.. 해당 개념을 사용해 문제도 좀 풀어봐서 익숙하다. 이 때, 간선의 가중치는 1만 가능하다. 다익스트라 알고리즘은 간선의 가중치가 0이상 일 때 사용할 수 있다. 다익스트라 알고리즘에 대해 자세히 알아보자. Dijkstra 그래프 자료구조와 시작 노드가 주어지고, 시작점에서 모든 노드까지의 최단 거리를 출력하는 알고리즘이다. dist[] : 시작점에서 특정 정점까지의 최단 거리를 담는 배열이다. (다익스트라의 결과를 담는 배열) D (v, d) : 시작점에서 v까지 가는데 d만큼이 사용된다. 1. 시작점을 S라고 하자. dist[i]에..
[Spring Basic] 파라미터의 변환과 검증
[Spring Basic] 파라미터의 변환과 검증
2022.06.24위의 URL로 요청을 수행하면, 데이터는 Map 자료구조로 변환된다. 해당 Map을 컨트롤러가 파라미터에 있는 MyDate 객체로 묶어준다. 이 과정에서 WebDataBinder가 개입해 타입 변환과 데이터 검증 작업을 수행한다. WebDataBinder는 스프링 MVC가 제공하는 기능으로, HTTP 요청 파라미터를 자바 객체에 자동으로 바인딩하는 역할을 수행한다. WebDataBinder가 요청 파라미터를 자바 객체로 변환할 때는 내부적으로 PropertyEditor 또는 Converter 가 사용된다. PropertyEditor는 java.beans 패키지에 포함돼있고 문자열을 특정 타입의 객체로 변환하거나 객체를 문자열로 변환한다. Converter는 스프링에서 제공하는 인터페이스로 문자열을 객체로..
위상정렬
위상정렬
2022.06.24Topological Sort 그래프 자료구조에 대해 정렬을 수행할 때 위상정렬을 사용한다. 위상정렬은 DAG 그래프에 대해서만 수행 할 수 있다. (사이클이 없고 방향성이 있는 그래프) 위상정렬을 통해 DAG에서 간선의 방향성에 따라 정점을 위상에 맞춰 정렬해보자. N에서 K로 가는 간선이 있다면 N은 K보다 먼저 나타나야 한다. 위의 조건을 충족하면서 정점들을 나열하는 것을 위상정렬이라고 한다. 위의 조건 때문에, 사이클이 있는 그래프에 대해서는 위상정렬을 수행할 수 없다. 이제 위상정렬의 과정에 대해 알아보자. 제일 먼저 올 수 있는 정점은 들어오는 간선이 없는 정점이다. 위의 그래프에서 정점 1 9 7은 들어오는 간선이 없기 때문에 정렬을 수행한 결과 중 앞에 위치한다. (1 9 7 간의 순서는 ..
[백준] 2252 줄 세우기 - Java
[백준] 2252 줄 세우기 - Java
2022.06.24주어지는 입력을 DAG로 표현하고, 위상정렬로 정렬해서 풀 수 있다. import java.util.*; import java.io.*; import java.math.*; public class Main { static ArrayList[] adj; static int[] indegree; static int N, M; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); Deque dq = new LinkedList(..