본문 바로가기

전체보기

 (44)
[Java] BOJ2239_스도쿠 www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 모든 경우를 다 따지면 최악의 경우 9^81 횟수가 나온다. 따라서 가지치기를 해줘야 하는 문제이다. 매번 반복문을 돌아서 값이 0인것을 찾기보다는 0인 애들의 index를 리스트에 담아두고 list로 반복문을 돌리는 게 유리하다. "답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력한다." 출력 조건에 맞추기 위해 스도쿠가 처음 완성되는 시점에 함수를 빠져나오도록 했다. 1부터 채우기 때문에 처음 ..
[Java] BOJ11497_통나무 건너뛰기 www.acmicpc.net/problem/11497 11497번: 통나무 건너뛰기 남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 www.acmicpc.net 두 통나무의 높이의 차가 최소가 되려면 두 번째 통나무는 첫 번째 통나무의 바로 다음번째로 큰 통나무여야 한다. 여기서 정렬을 해야 하는 것을 알 수 있고, 정렬하여 가장 차이가 조금 나게 뽑아낼 것이기 때문에 그리디 알고리즘을 유추할 수 있다. 정렬을 한 배열을 다시 재배치 해야하는데 문제의 예시에서 힌트를 얻을 수 있다. [2, 5, 9, 7, 4]. 바로 왼쪽 오른쪽 번갈아가며 수를 배치하는 것이다. 이..
[Java] BOJ11404_플로이드 www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 문제 제목부터 플로이드다. 플로이드-와샬 알고리즘을 사용하면 된다. 다만 주의할 점은 "시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다."라는 조건 때문에 인접 행렬을 만들 시에 중복으로 들어오는 값 중 작은 값을 넣어줘야 한다. 또한 작은 값을 세팅해주기 위해 배열을 MAX_VALUE로 초기화해주었는데, "만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다."라는 조건을 잊지 말고..
[Java] BOJ11403_경로찾기 www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 모든 정점에 대해 모든 경로를 구하는 문제로, 플로이드-와샬 알고리즘으로 구현할 수 있다. 보통의 플로이드-와샬은 최단 비용을 구하기 위해 사용되지만 이 문제 같은 경우에는 갈 수 있는지만을 판단하는 것이기 때문에 i에서 j로 가는데 k를 거쳐서 갈 수 있을 경우 arr[i][j]를 1로 업데이트해주면 해결된다. import java.io.*; import java.util.StringTokenizer; public class Bj11403 { publ..
[Java] BOJ1107_리모컨 www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 달리 빠르게 찾을 방법이 없기에 단순 브루트 포스 문제이다. 가능한 숫자들을 순서에 상관 있게 누르고 같은 숫자를 또 누를 수 있기 때문에 중복순열로 구현하였다. 주의할 점은 찾아가야할 채널의 길이만큼만 누르는 것이 아니고 그보다 하나 짧은 길이, 하나 긴 길이를 다 체크해줘야 한다. 세 가지 체크를 하나의 함수로 구현할 방법도 있겠지만 나는 무식하게 각자 함수로 구현했다. 이래저래 조건 따지며..
[Java] BOJ11053_가장 긴 증가하는 부분 수열 www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 제목 그대로 최장 증가 부분 수열 문제이다. N의 범위가 1000으로 작기 때문에 단순 이중 포문으로도 구현 가능하다. DP[i]는 i번째 수를 마지막 원소로 가지는 수열의 길이를 의미한다. i번째 이전의 수들을 j번째 수라고 하면 i번째 수가 j번째 수보다 크고 현재 수열의 길이가 dp[j]+1보다 작다면 dp[i]를 업데이트..
[Java] BOJ10844_쉬운 계단 수 www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 출력 조건에서 값이 매우 크기 때문에 브루트 포스로는 할 수 없다는 것을 알았고, 이전 자리까지의 수가 다음 자리의 수를 결정하기 때문에 DP라는 것을 유추할 수 있었다. N자리 수에서 0, 1, 2, 3, 4, 5, 6, 7, 8, 9가 맨 끝에 몇 개 올 수 있는지에 대하여 DP 배열을 구성했다. 주의할 점은 0은 1번째자리에서 존재할 수 없고, 이전 수는 오직 1뿐만이 가능하다. 9는 8뿐만이 가능하다. 0과 9는 서로 계단 수가 아니다. 나머지 수는 자신보다 큰 값이나 작은 값 다음에 올 수 있다. *시도는 안해봤지만..
[Java] BOJ10836_여왕벌 www.acmicpc.net/problem/10836 10836번: 여왕벌 입력의 첫 줄에는 격자칸의 가로와 세로 크기 M(2 ≤ M ≤ 700)과 날짜 수 N(1 ≤ N ≤ 1,000,000)이 자연수로 주어진다. 첫날 아침의 애벌레 크기는 모두 1이므로 입력에 주어지지 않는다. 다음 N개의 www.acmicpc.net 단순 구현 문제이지만 생각보다 시간이 엄청 빡빡했다. 우선 날짜 수가 최대 백만으로 매우 크기 때문에 날짜마다 전체 배열을 업데이트시켜주는 것은 안된다. 제일 왼쪽 열과, 제일 위쪽 행의 애벌레들은 자신이 자라는 정도를 스스로 결정한다. 이들은 입력으로 주어질 것이다. 애벌레들이 자라는 정도를 왼쪽 제일 아래 칸에서 시작하여 위쪽으로 가면서 읽고, 제일 위쪽 칸에 도착하면 오른쪽으로 가..

티스토리툴바