본문 바로가기

장원익 기술블로그

💻 Computer Science191

[알고리즘 PS] 백준 2805번 나무 자르기 자바 문제풀이 문제 해당 포스팅은 백준의 2805번 나무 자르기 의 접근과 해결 방법을 설명한 글 입니다. 정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다. 이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자. 문제 접근 이 문제는 지난 랜선 자르기 문제와 비슷한 방법으로 해결할 수 있다. 우선 문제를 읽고 어떤 것을 원하는지 파악부터 해보자. 우리에겐 나무의 수 N과 그에 따른 나무들의 높이가 주어진다. 그리고 상근이가 집에 가져가야 할 나무의 높이또한 주어진다. 그럼 이를 한 문장으로 정리해보자. 나무의 수 N과 각각의 나무 높이와 상근이가 필요한 나무의 높이 M이 주어지고 M이 최소가 되는 절단기 높이를 구하라. 그럼 절단기 높이를 1 ~ 나무 최대 높이인 20억 까지 .. 2021. 2. 13.

[알고리즘 PS] 백준 1654번 랜선 자르기 자바 문제풀이 문제 해당 포스팅은 백준의 1654번 랜선 자르기 의 접근과 해결 방법을 설명한 글 입니다. 정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다. 이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자. 문제 접근 문제에서 원하는 내용을 한 문장으로 말 하자면 다음과 같다. K개의 랜선을 N개로 나누어 자를 때, 각 랜선의 길이가 최대가 되는 길이를 출력하라. 그럼 우선, 아무런 생각하지 말고 K개의 랜선을 N개로 나누어서 자를 때 최대의 길이를 구해보자. 어떠한 알고리즘이 생각나지 않아도 좋다. 아니 생각하지 말고 한 번 짜보자. public static void main(String[] args) { int k = 4; int n = 11; int[] arr = {.. 2021. 2. 13.

[알고리즘 PS] 백준 2178번 미로 탐색 자바 문제풀이 문제 해당 포스팅은 백준의 2178번 미로 탐색 의 접근과 해결 방법을 설명한 글 입니다. 정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다. 이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자. 문제 접근 문제를 읽으며 바로 파악해야 하는 것은 최소의라는 키워드이다. 해당 문제는 Dfs와 Bfs 모두 풀 수 있는 문제이다. 하지만 우리는 BFS를 사용한다. 예를 들어서 다음과 같은 관계가 있다고 가정해보자. 여기서 DFS를 이용하는데, 운이 나쁘게 DFS에서 처음으로 선택한 노드가 6이라고 해보자. 그럼 실제로 찾는 노드는 바로 한칸 앞에 있지만, DFS를 사용한다면 6의 끝 까지 들어가게 된다. 그래서 이런 최단 거리, 경로문제는 BFS를 이용해서 풀어야 한다.. 2021. 2. 11.

[알고리즘 PS] 백준 4963번 섬의 개수 자바 문제풀이 문제 해당 포스팅은 백준의 4963번 섬의 개수 의 접근과 해결 방법을 설명한 글 입니다. 정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다. 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자. 문제 접근 이 문제는 전형적인 Connected Component 문제이다. 다른 말로는 연결 요소 찾기라고 하는데, 해당 문제보다 조금 쉬운 버전이 백준의 11724번 연결 요소의 개수 문제이다. 연결 요소의 개수 문제 .. 2021. 2. 10.

[알고리즘 PS] 백준 2667번 단지번호붙이기 자바 문제풀이 문제 해당 포스팅은 백준의 2667번 단지번호붙이기 의 접근과 해결 방법을 설명한 글 입니다. 정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다. 이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자. 문제 접근 이 문제는 전형적인 Connected Component 문제이다. 다른 말로는 연결 요소 찾기라고 하는데, 해당 문제보다 조금 쉬운 버전이 백준의 11724번 연결 요소의 개수 문제이다. 연결 요소의 개수 문제 풀이에서 해당 문제의 접근과 해결을 볼 수 있으니 참고하면 좋을 듯 하다. 하지만 지난 연결 요소의 개수 문제 풀이와 다른 점이라고 한다면, 인접 리스트가 아니라 이차원 행렬이 그래프가 된다는 것이다. 인접 리스트는 하나의 노드가 몇 개의 노드를 갖.. 2021. 2. 10.

[알고리즘 문제 풀이 스킬] 자바 int 형 숫자 자리수 출력하기 숫자 자리수 출력하기 문제에서 숫자 자리수마다 누적합을 구하라, 혹은 누적 곱을 해라 라는 문제가 종종 출제된다. 실제로 백준 문제풀이에 2331번 반복 수열에서 문제 조건에 다음과 같은 조건이 있다. N = 57, P = 2 일 때, D[n] = D[n-1]의 각 자리 숫자를 P번 곱한 수들의 합 예를 들어 arr[1] = 57;가 있다고 했을 때, arr[2] = (5 * 5) + (7 * 7) = 74가 되는 것이다. 이걸 어떻게 구현할까? 정답은 모듈러 연산과 나눗셈을 이용하는 것이다. 구현 모듈러 연산과 나눗셈을 이용한 방법 int number = 572; while(number > 0) { System.out.println(number % 10); // 572 % 10 = 2 number /=.. 2021. 2. 7.

이전 1 ··· 8 9 10 11 12 13 14 ··· 32 다음

티스토리툴바