java

[백준] 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점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다...

[백준] 12100 - 2048 (Easy) (자바/Java)

문제 링크 성능 요약 메모리: 24332 KB, 시간: 348 ms 분류 백트래킹(backtracking), 브루트포스 알고리즘(bruteforcing), 구현(implementation), 시뮬레이션(simulation) 문제 설명 2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다. 이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다) ..

[SWEA] 4008 - 숫자 만들기 (자바/Java)

dfs를 통해 가능한 연산 결과를 완전 탐색하며 최대, 최소값을 저장하였다. 연산을 N-1번 수행하니까 idx가 N-1이 될 때 연산이 끝난 것이므로 함수를 return 한다. 연산자 배열에서 각 인덱스의 값이 0이 아니면 그 연산자로 계산할 수 있는 것이니까 계산 값을 재귀적으로 함수에 넣어준다. static void dfs(int idx, int res) { if (idx == N - 1) { min = Math.min(res, min); max = Math.max(res, max); return; } for (int i = 0; i < 4; i++) if (op[i] != 0) { op[i]--; dfs(idx + 1, cal(i, res, nums[idx + 1])); op[i]++; } } 가능..

[백준] 12865 - 평범한 배낭 (자바/Java) : Knapsack Problem

[Gold V] 평범한 배낭 - 12865 문제 링크 성능 요약 메모리: 52664 KB, 시간: 192 ms 분류 다이나믹 프로그래밍(dp), 배낭 문제(knapsack) 문제 설명 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 ..

[백준] 17069 - 파이프 옮기기 2 (자바/Java)

문제 링크 성능 요약 메모리: 11880 KB, 시간: 84 ms 분류 다이나믹 프로그래밍(dp) 문제 설명 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다. 오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다. 파이프는 회전시킬 수 있으며, 아래와 같이 3가지 방향이 가능하다. 파이프는 매우 무겁기 때문에, 유현이는 파이프를 밀어서 이동시키려고 한다. 벽에는 새로운 벽지를 발랐기 때문에, 파이프..

[백준] 1759 - 암호 만들기 (자바/Java)

문제 링크 성능 요약 메모리: 13036 KB, 시간: 120 ms 분류 백트래킹(backtracking), 브루트포스 알고리즘(bruteforcing), 조합론(combinatorics), 수학(math) 문제 설명 바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다. 암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서..

[백준] 11444 - 피보나치 수 6

[Gold II] 피보나치 수 6 - 11444 문제 링크 성능 요약 메모리: 12888 KB, 시간: 108 ms 분류 분할 정복을 이용한 거듭제곱(exponentiation_by_squaring), 수학(math) 문제 설명 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다. n=17일때 까지 피보나치 수를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오...