문제 풀이

[백준] 1197 - 최소 스패닝 트리 (자바/Java)

[Gold IV] 최소 스패닝 트리 - 1197 문제 링크 성능 요약 메모리: 230420 KB, 시간: 1196 ms 분류 그래프 이론(graphs), 최소 스패닝 트리(mst) 문제 설명 그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오. 최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. 입력 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며,..

[백준] 11660 - 구간 합 구하기 (자바/Java)

[Silver I] 구간 합 구하기 5 - 11660 문제 링크 성능 요약 메모리: 127496 KB, 시간: 728 ms 분류 다이나믹 프로그래밍(dp), 누적 합(prefix_sum) 문제 설명 N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다. 예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자. 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다. 표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로..

[백준] 16139 - 인간-컴퓨터 상호작용 (자바/Java)

문제 링크 성능 요약 메모리: 106172 KB, 시간: 608 ms 분류 누적 합(prefix_sum) 문제 설명 승재는 인간-컴퓨터 상호작용에서 생체공학 설계를 공부하다가 키보드 자판이 실용적인지 궁금해졌다. 이를 알아보기 위해 승재는 다음과 같은 생각을 했다. '문자열에서 특정 알파벳이 몇 번 나타나는지 알아봐서 자주 나타나는 알파벳이 중지나 검지 위치에 오는 알파벳인지 확인하면 실용적인지 확인할 수 있을 것이다.' 승재를 도와 특정 문자열 $S$, 특정 알파벳 $\alpha$와 문자열의 구간 $[l,r]$이 주어지면 $S$의 $l$번째 문자부터 $r$번째 문자 사이에 $\alpha$가 몇 번 나타나는지 구하는 프로그램을 작성하여라. 승재는 문자열의 문자는 $0$번째부터 세며, $l$번째와 $r$번..

[백준] 11659 - 구간 합 구하기 4 (자바/Java) : 누적 합

문제 링크 성능 요약 메모리: 235808 KB, 시간: 1080 ms 분류 누적 합(prefix_sum) 문제 설명 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다. 출력 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다. 누적합 알고리즘의 기본을 익힐 수 있는 문제다. 누적 합 arr[i] = 0~i까지의 합 i부터 j까지의 누적 합: arr[j]-arr[i-1]; = i, i+1, … j-1, j 까지의 합 pack..

[백준] 2565 - 전깃줄 (자바/Java)

문제 링크 성능 요약 메모리: 13084 KB, 시간: 124 ms 분류 다이나믹 프로그래밍(dp) 문제 설명 두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다. 예를 들어, 과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다. 전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에..

[SWEA][모의 SW 테스트] 2105 - 디저트 카페 (자바/Java)

대각선으로 사방탐색을 하는 문제다. 주의해야할 조건은 같은 숫자의 디저트를 만나면 안된다. 시작점을 제외하고 이미 방문했던 곳은 다시 방문할 수 없다. 시작점으로 돌아오도록 사각형이 그려져야 한다. 최대한 많은 디저트를 먹어야 한다. map의 좌표가 N일 때, 대각선으로 투어를 해야하기 때문에 양 끝 꼭짓점에서는 순회를 시작할 수 없다. 가장 큰 사각형의 가로 세로의 합은 N-1이다. 위 사진에서 N은 5고, 두 사각형이 가능한 최대 길이의 사각형이다. 왼쪽의 경우 가로가 3, 세로가 1이고 오른쪽은 가로가 2, 세로가 2다. 일직선이나 자기 자신만 투어하는 경우는 불가능하기 때문에 사각형의 한 변의 최소 길이는 1, 최대 길이는 N-2가 될 것이다. 이를 활용해서 두 변의 길이의 합이 최대일 때부터 최..

[백준] 11053 - 가장 긴 증가하는 부분 수열 (자바/Java)

문제 링크 성능 요약 메모리: 16964 KB, 시간: 192 ms 분류 다이나믹 프로그래밍(dp) 문제 설명 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000) 출력 첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다. 가장 긴 증가하는 부분 수열 (LIS)를 구하는 문제다. 여러 가지 방법이 있지만 입력이 10..

[백준] 1463 - 1로 만들기 (자바/Java) : DP

문제 링크 성능 요약 메모리: 55224 KB, 시간: 224 ms 분류 다이나믹 프로그래밍(dp) 문제 설명 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 정수 X가 2와 3 모두 나누어 떨어지지 않는 경우에는 X-1을 하면 된다. 문제는 2 또는 3과 나누어 떨어지는 경우에, 2나 3으로 나누는 것이 최적의 답이 아닐 ..

[SWEA] 1767 - 프로세서 연결하기 (자바/Java)

조합을 통해 경우의 수를 한정하는 방법을 자주 사용해야 할 것 같다. 처음에는 그냥 dfs로 풀어서 답은 맞았는데, 시간과 메모리를 너무 많이 잡아 먹었다. 지금 생각해보니 필요 없는 경우의 수까지 모두 탐색해서 그런 것 같다. 연결하는 코어의 수가 최대여야 하기 때문에, 모든 코어를 연결하는 경우의 수부터 dfs를 진행하고, 만약 그 수의 코어를 연결할 수 없다면 코어의 개수 N 중 N-1개, N-2개를 뽑는 조합을 통해 dfs를 반복하여 결과값이 나올 때까지 계속하면 된다. 이런 경우에서는 조합을 활용하는 게 유용한 것 같다. for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) { arr[i][j] = sc.nextInt(); if (arr[i][j] ..

[백준] 2579 - 계단 오르기 (자바/Java) : DP

문제 링크 성능 요약 메모리: 13208 KB, 시간: 128 ms 분류 다이나믹 프로그래밍(dp) 문제 설명 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다...