문제풀이/백준83 [JAVA] BOJ 백준 12015번 - 가장 긴 증가하는 부분 수열 2 목차 문제 내가 푼 방법 자바 코드 결과 및 회고 1. 문제 https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 2. 내가 푼 방법 가장 긴 증가하는 부분 수열의 길이를 구하는 방법은 DP 혹은 이분 탐색을 이용해야 한다. DP는 O(N^2)의 시간 복잡도를 가지고, 이분 탐색은 O(N logN)의 시간 복잡도를 가진다. 이 문제는 이분 탐색을 이용해야 하며, binarySearch를 직접 구현하는 방법과 Arrays.binarySearh()를 이.. 2024. 1. 5. [JAVA] BOJ 백준 11003번 - 최솟값 찾기 목차 문제 내가 푼 방법 자바 코드 결과 및 회고 1. 문제 https://www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 2. 내가 푼 방법 Deque 자료형을 알고 있었기 때문에, 금방 구현할 수 있는 문제였다. Deque는 스택과 큐 기능이 모두 들어간 양방향 자료형이며, 양쪽 끝 연산에 특화되어 있기 때문에 O(1) 시간복잡도로 처리할 수 있다. 이 문제는 가장 나중에 넣는 값이 항상 더 큰 값만 가지는 게 핵심이다. .. 2024. 1. 5. [JAVA] BOJ 백준 4195번 - 친구 네트워크 목차 문제 내가 푼 방법 자바 코드 결과 및 회고 1. 문제 https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 2. 내가 푼 방법 union-find를 이용하는 것까지는 짐작했지만, 어떻게 기존에 있는 친구 그룹 수를 카운팅해야 할지 감이 잡히지 않았다. 다른 사람 풀이를 보니 새로운 level 배열을 이용해 기존에 존재하던 친구 수를 새로 관계 맺은 그룹의 친구 수에 더해주는 방식임을 이해했다. 3. 자바 코드 깃허브 풀이 주소 : .. 2024. 1. 4. [JAVA] BOJ 백준 17472번 - 다리 만들기 2 목차 문제 내가 푼 방법 자바 코드 결과 및 회고 1. 문제 https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 2. 내가 푼 방법 다리의 방향이 바뀌면 안 되기 때문에 다른 조건들을 고려할 필요가 있던 BFS 문제였다. 크게 3개의 함수로 나누어 문제 풀이를 진행했다. public static void solution() { getIsland(); linkBridge(); choiceBridge(); } 먼저 getIslan.. 2024. 1. 4. [JAVA] BOJ 백준 2638번 - 치즈 목차 문제 내가 푼 방법 자바 코드 결과 및 회고 1. 문제 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 2. 내가 푼 방법 BFS 알고리즘을 이용해 모눈종이 가장자리처럼 치즈가 아닌 부분을 이동하면서 상하좌우에 +1씩 더해주었다. 그렇게 되면, 공기와 접촉한 부분을 알 수 있으므로 치즈 임과 동시에 2 이상일 경우에 치즈를 녹여주면 된다. Queue queue = new LinkedList(); boolean[][] visit.. 2024. 1. 4. [JAVA] BOJ 백준 19238번 - 스타트 택시 목차 문제 내가 푼 방법 자바 코드 결과 및 회고 1. 문제 https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 2. 내가 푼 방법 구현이 필요한 BFS 알고리즘 문제이다. 나는 크게 두 개의 함수로 분리했는데, 승객을 태우러 가는 getCustomer 함수와 승객을 도착지에 데려다주는 moveDestion 함수가 여기에 해당한다. 만약 M명의 승객을 모두 이동시키기 전에 연료가 바닥나거나 더 이상 움직일 수.. 2024. 1. 4. 이전 1 2 3 4 5 6 7 8 ··· 14 다음
