본문 바로가기

분류 전체보기242

[백준] 2602: 돌다리 건너기 - JAVA https://www.acmicpc.net/problem/2602 풀이길이 두개가 있고, 두 길의 발판을 번갈아가며 밟으면서 길을 건너야 한다. 밟아야 할 발판의 종류는 정해져 있다. 완전탐색하면 시간초과가 날 것이고, dp를 사용해야 한다. 건너기 위해 밟아야 할 발판을 route라하고, 길을 a와 b라고 하면, dp배열을 [2][route][a,b]로 만들 수 있다. 지금 밟아야 할 발판과 현재 보고 있는 길의 발판이 같으면 `dp[현재 길][i][j] = dp[현재 길][i][j-1] + dp[다른 길][i-1][j-1]` 이 된다. 발판이 다르면 같은 길에서 바로 전에꺼를 가져오면 된다. 즉, `dp[현재 길][i][j] = dp[현재 길][i][j-1]` 이 된다. 끝까지 진행하여 dp[a]의 .. 2024. 5. 17.
[백준] 9576: 책 나눠주기 - JAVA https://www.acmicpc.net/problem/9576 풀이이분 매칭 알고리즘을 이용해 풀 수 있는 문제였다. ArrayList에 학생마다 배정할 수 있는 책들을 저장한다. 책의 주인을 담을 수 있는 배열을 만들고, 방문 처리를 할 배열을 만들었다. m명의 학생을 탐색하면서 dfs를 하는데 배정되지 않은 책의 경우 해당 학생에 배정하고, 배정된 경우 해당 책의 주인으로 등록된 사람을 dfs탐색하여 다른 책에 배정할 수 있는 지 확인하고 가능할 경우 새로 배정한다.  메모리: 100992KB시간: 1064ms언어: Java 11import java.util.*;import java.io.*;public class Main { static ArrayList> list; static bo.. 2024. 5. 16.
[백준] 2188: 축사 배정 - JAVA https://www.acmicpc.net/problem/2188 풀이이분 매칭 알고리즘으로 푸는 문제였다. 소가 각각 희망하는 축사 번호가 주어진다. 이것을 `ArrayList>` 에 저장했다. 그 후 1번 소부터 n번 소까지 dfs탐색을 하는데 이때 각 소가 희망하는 축사의 번호를 반복 탐색으로 체크하여 이미 축사가 선점되었으면 그 축사의 주인이 되는 소를 찾아 다른 축사에 들어갈 수 있는지 판단하는 과정을 거친다. 해당 번호의 소가 축사를 배정받을 수 있었다면 카운트를 1늘려준다.  메모리: 17364KB시간: 252ms언어: Java 11import java.util.*;import java.io.*;public class Main { static ArrayList> list; stat.. 2024. 5. 16.
[자바] JUnit을 이용한 단위 테스트 JUnit이란 자바의 대표적인 단위 테스트를 하는 프레임워크이다. JUnit의 버전 중 하나인 JUnit5와 AssertJ 라이브러리가 사용되는데 AssertJ는 자바 테스트를 돕기 위해 다양한 문법을 지원한다. Assert 구문테스트에서 기대값과 출력값을 비교하는 구문은 Assert이다. 변수 타입의 종류가 다양하기 때문에 여러 종류의 Assert 구문을 지원하고 있다.메서드내용assertEquals(expected, actual)두 객체의 equals 결과가 참인지 검사한다.assertTrue(actual)계산 결과가 참인지 검사한다. assertFalse(actual) 계산 결과가 거짓인지 검사한다.assertNotNull(actual) 계산 결과가 null이 아닌지 검사한다.assertNull(a.. 2024. 5. 16.
[백준] 19238: 스타트 택시 - JAVA https://www.acmicpc.net/problem/19238 풀이빈칸과 벽이 있는 지도가 주어진다. 택시의 시작위치와 승객의 출발지와 도착지가 주어진다. 택시는 한칸 이동할 때 연료 1씩 소모하며, 승객을 태우고 이동하여 목적지에 도달하였다면 승객을 태우고 이동한 만큼의 2배 연료를 획득한다. 이동하는 중에 연료가 다 떨어지면 끝난다. bfs탐색을 통해 택시로부터 승객까지 최소 위치를 구했고, 다시 bfs탐색으로 승객을 목적지까지 이동시켰다. 택시가 승객에 도착하거나, 목적지에 도착했을 때, 연료 체크를 하여 도중에 0이 되었는지 확인했다.  메모리: 22748KB시간: 220ms언어: Java 11import java.util.*;import java.io.*;public class Main {.. 2024. 5. 16.
[백준] 1749: 점수따먹기 - JAVA https://www.acmicpc.net/problem/1749 풀이n \* m 행렬에서 직사각형의 구간을 잡아 구간의 합의 최대값을 구하는 문제이다. 입력을 받으면서 n \* m 행렬을 누적합으로 저장했다.board[i][j] = Integer.parseInt(st.nextToken()) + board[i - 1][j] + board[i][j - 1] - board[i - 1][j - 1];탐색을 해서 최댓값을 구해야 하는데 구간의 길이가 정해져 있지 않으므로 행시작/끝, 열시작/끝 4중for문을 통해 탐색해야 한다. 열 시작을 rs, 끝을 re, 행 시작을 cs, 끝을 ce로 하여 정답을 갱신했다.ans = Math.max(ans, board[re][ce] - board[rs - 1][ce] - b.. 2024. 5. 16.
[백준] 2955: 스도쿠 풀기 - JAVA https://www.acmicpc.net/problem/2955 풀이숫자 하나를 골라 가로, 세로, 3*3박스를 체크하는 cross-hatching 방법으로 스도쿠를 채우는 문제였다. boolean 배열을 통해 가로, 세로, 박스를 체크해놓고 박스가 false인 구간들을 다시 가로, 세로를 이용해 체크했다. 모순이 일어나는 경우도 체크하여 에러임을 표시했다. 코드 작성 중 오타로 인해 시간이 오래 걸린 문제였다.  메모리: 14204KB시간: 128ms언어: Java 11import java.io.*;public class Main { static int[][] board; static boolean error = false; public static void main(String[] .. 2024. 5. 16.
[백준] 14461: 소가 길을 건너간 이유 7 - JAVA https://www.acmicpc.net/problem/14461 풀이격자로 이루어진 땅을 건너가야하는데 세칸을 이동할 때 마다 격자에 써있는 만큼의 풀을 먹어야 한다. 한칸을 이동할 때는 T만큼의 비용이 든다. 격자 칸마다 다른 가중치가 있다. 즉, 다익스트라를 이용해 문제를 풀면 된다. 3칸을 이동하는 방법은 ABA 처럼 갔던 칸에 다시 방문하는 방법이 있고, ABC처럼 다른 칸에 갈 수도 있다. 이러한 방법들을 적어보니 16가지가 된다. 이차원 배열로 만들어 사용했다.static int[][] vector = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 }, { 3, 0 }, { -3, 0 }, { 0, 3 }, { 0, -3 }, { 2, 1 },.. 2024. 5. 16.
[자바] 단위 테스트(unit test) 알아보기 TDD란 Test Driven Development의 약자로 테스트 주도 개발을 말한다. 테스트를 먼저 만들어 이를 통과하기 위한 코드를 짜는 것. 즉, 만드는 과정에서 테스트를 작성하고 그걸 통과하는 것을 만들고 반복하면서 제대로 동작하는 것에 대한 피드백을 받는 것이다. 테스트의 종류로는 단위 테스트와 통합 테스트가 있다. 단위 테스트(Unit Test)단위 테스트는 하나의 모듈을 기준으로 독립적으로 진행되는 가장 작은 단위의 테스트이다. 모듈이란 애플리케이션에서 하나의 기능 또는 메서드라고 이해하면 된다. 즉, 단위 테스트는 애플리케이션을 구성하는 하나의 기능이 올바르게 동작하는지를 독립적으로 테스트하는 것이다. 통합 테스트(Integration Test)통합 테스트는 모듈을 통합하는 과정에서 모듈.. 2024. 5. 16.
[백준] 15824: 너 봄에는 캡사이신이 맛있단다 - JAVA https://www.acmicpc.net/problem/15824 풀이매운 정도를 배열로 입력받아 몇 개를 선택하여 조합을 만들 경우 그 안에서 최댓값과 최솟값의 차이가 그 조합의 맛의 정도가 된다. 이런 맛의 정도들의 합을 구하는 문제이다. 먼저 입력받은 배열을 정렬했다. i번째 인덱스의 경우 이 값이 최솟값이 되는 경우는 2^i개의 경우, 이 값이 최댓값이 되는 경우는 2^(N - i - 1)개의 경우가 된다. 2의 거듭제곱을 구하기 위해 분할정복을 이용했다.  메모리: 58472KB시간: 792ms언어: Java 11import java.util.*;import java.io.*;public class Main { static final int MOD = 1_000_000_007; st.. 2024. 5. 16.

티스토리툴바