본문 바로가기

문제풀이/백준83

[JAVA] BOJ 백준 16946번 - 벽 부수고 이동하기 4 목차 문제 내가 푼 방법 자바 코드 결과 및 회고 1. 문제 https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 2. 내가 푼 방법 자칫하면 바로 시간초과가 발생할 수 있는 문제이다. 나는 처음에 큐 한 개와 for문을 돌려 풀었는데, 다른 사람과 비교했을 때 속도 차이가 많이 나서 Deque 큐 두 개를 이용해 다시 풀었다. Deque는 큐나 스택처럼 사용할 수 있는데 스택과 비교했을 때는 상황에 따라 다르지만 양 끝쪽에서 .. 2024. 1. 7.
[JAVA] BOJ 백준 14003번 - 가장 긴 증가하는 부분 수열 5 목차 문제 내가 푼 방법 자바 코드 결과 및 회고 1. 문제 https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 2. 내가 푼 방법 DP와 이분 탐색을 함께 사용해 풀었다. 우선 int[][] valueDP 배열은 가장 큰 수열 값이 들어가며 valueDP 값이 현재 값(arr[i])보다 더 클 경우 업데이트되며, 증가하는 부분 수열의 가장 긴 길이를 구하는 용도이다. int[][] indexDP 배열은 valueDP.. 2024. 1. 6.
[JAVA] BOJ 백준 1725번 - 히스토그램 목차 문제 내가 푼 방법 자바 코드 결과 및 회고 1. 문제 https://www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 자 www.acmicpc.net 2. 내가 푼 방법 너비를 구하는 게 조금 헷갈리는 문제이다. 스택을 이용하는데, push 되는 값이 가장 큰 값이 되도록 저장했다. 그래야 더 작은 값이 들어가기 전에 높이가 가장 긴 직사각형을 구할 수 있기 때문이다. 실제로는 스택에는 가장 큰 값의 인덱스를 저장해 두었는데, 새로 push 할 값(ar.. 2024. 1. 6.
[JAVA] BOJ 백준 16933번 - 벽 부수고 이동하기 3 목차 문제 내가 푼 방법 자바 코드 결과 및 회고 1. 문제 https://www.acmicpc.net/problem/16933 16933번: 벽 부수고 이동하기 3 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 2. 내가 푼 방법 처음에는 이동했던 경로를 확인하기 위해 4차원 배열을 사용해서 풀었지만 공간 복잡도와 시간 복잡도가 다른 분들에 비해 훨 성능이 떨어졌다. 그래서 다른 분들의 코드를 참고하여 다시 푼 문제이다. 이동했던 경로를 확인하기 위해 2차원 배열인 Integer[][] visit = new .. 2024. 1. 6.
[JAVA] BOJ 백준 12738번 - 가장 긴 증가하는 부분 수열 3 목차 문제 내가 푼 방법 자바 코드 결과 및 회고 1. 문제 https://www.acmicpc.net/problem/12738 12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 2. 내가 푼 방법 문제 제목 그대로 LIS(Longest Increasing Sequence) 알고리즘 문제이며, 이분탐색을 이용해 풀었다. 이분 탐색을 할 때 Arrays.binarySearch 함수를 이용했으며, 이 함수는 정렬된 배열에서 target에 해당하는 인덱스를 빠르게 찾아 반환해 주는 기능을.. 2024. 1. 5.
[JAVA] BOJ 백준 14442번 - 벽 부수고 이동하기 2 목차 문제 내가 푼 방법 자바 코드 결과 및 회고 1. 문제 https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 2. 내가 푼 방법 벽 부수고 이동하기 1을 풀었다면, 이번 문제도 BFS 알고리즘을 사용해 쉽게 풀 수 있을 것이다. 벽을 K번까지 부술 수 있는 것이며, 이를 위해 벽은 K번 부쉈을 때 이동했던 경로인지 확인하는 작업이 필요하다. 또한, 이동한 횟수가 작을 경우 더 높은 우선순위를 갖는 Priori.. 2024. 1. 5.

티스토리툴바