프로그래밍 diary

1010번 - 다리 놓기 https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 점화식: dp[n][m] = dp[n][m - 1] + dp[n - 1][m - 1] n 값이 1일 때, 경우의 수는 m의 값을 따른다. n == m 일 때, 경우의 수는 1이다. 더보기 #include #define MAX 31 using namespace std; int T, N, M; long long dp[MAX][MAX] = {0, }; int site(int n..

2156번 - 포도주 시식 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net arr[] -> 문제에서 입력 받은 포도주의 용량을 저장 dp[][] -> 선택한 포도주 잔의 용량의 합을 저장 점화식 dp[0][i] = max(dp[1][i-1], dp[2][i-1]) + arr[i] dp[1][i] = max(dp[0][i-2], dp[1][i-2], dp[2][i-2]) + arr[i] dp[2][i] = max(dp[0][i-3], dp[1][i..

10844번 - 쉬운 계단 수 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net N = 1 1, 2, 3, 4, 5, 6, 7, 8, 9 N = 2 10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98 N = 3 101, 121, 123, 210, 212, 232, 234, 321, 323, 343, 345, 454, 456, 432, 434, 543, 545, 565, 567, 654, 656, 676, 678, 765, 767, 787, 789, 876, 878, 898, 987, 989 처..

1912번 - 연속합 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 완성된 dp 배열에서 최댓값을 출력하면 문제에서 찾는 답이 된다. 점화식: dp[i] = dp[i] + dp[i-1], dp[i] = arr[i] 더보기 #include using namespace std; int n; int dp[100001] = { 0, }; int arr[100001] = { 0, }; int main() { cin >> n; for (int i = 1; i > ..

1699번 - 제곱수의 합 https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 점화식: dp[i] = dp[j * j] + dp[i - j * j] = 1 + dp[i - j * j] #include #include using namespace std; int N; int dp[100001] = { 0, }; int solution(int n) { //제곱근이 맞으면 0, 아니면 1 long long re; ..

11054번 - 가장 긴 바이토닉 부분 수열 #include #include using namespace std; int N; int arr[1001] = { 0, }; int dp_In[1001] = { 0, }; int dp_De[1001] = { 0, }; int max_Value = 0; int main() { cin >> N; for (int i = 1; i > arr[i]; } for (int i = 1; i = 1; i--) { //감소하는 부분수열의 길이 구하기 dp_De[i] = 1; for (int j = N; j > i; j--) { if (arr[j] < arr[i] && dp_De[i] < dp_De[j] + 1) dp_De[i] = dp_De[j] + 1; } } for (int..

다형성(polymorphism) -> 다형성은 다양한 형태 또는 특성을 가진다는 의미입니다. 자바와 같은 객체 지향 언어에서 의미는 부모 클래스를 상속받은 자식 클래스의 인스턴스가 부모의 객체로 사용되고, 자식 클래스의 객체로도 사용될 수 있는 다양한 상황을 의미합니다. 예를 들어, "앵무새가 말을 하네"라는 문장은 "새가 말을 하네"라는 문장으로 사용하여도 어색하지 않습니다. 앵무새가 새의 한 종류이기 때문에 같은 의미로 사용 가능합니다. class Bird {} class Parrot extends Bird {} public class Main { public static void main(String[] args) { Bird b1 = new Bird(); Parrot p1 = new Parrot(..

1759번 - 암호 만들기 문제를 읽고 처음 시도한 접근은 조합입니다. 6개의 알파벳 문자 중에 4개를 선택하여 암호를 완성한다. 대신 모음은 최소 1개 자음은 최소 2개를 포함한다. 즉, 6C4(15개)를 구해서 모음이 포함되지 않았거나 자음이 1개 이하로 포함된 암호를 빼줍니다. 또, 암호는 증가하는 순서로 정렬되었을 것이라고 추측되기 때문에 sort 함수를 사용하여 미리 입력받은 알파벳 문자를 오름차순으로 정렬합니다. * 재귀를 사용하여 조합된 암호를 출력하는 combinatin 함수 public static void combination(String[] alpha, boolean[] visit, int dep, int r) { if(r == 0) { print(alpha, visit); //조합된..

추상 클래스(abstract) -> 추상 클래스는 클래스의 구체적인 내용을 작성하지 않고 '공통적인 특징'을 추상적으로 선언합니다. 반환 값도 없으며, 메소드 명만 선언합니다. 메인 클래스에 추상 클래스의 객체를 바로 생성할 수 없습니다. 그렇다면 추상 클래스는 어떻게 사용해야 할까요? 추상 클래스는 자식 클래스에게 상속을 해줌으로써 사용 가능합니다. 즉, 추상 클래스는 부모 클래스의 역할을 하며 자식 클래스는 추상 메소드를 재정의하여 사용합니다. 이러한 추상 클래스의 특징 때문에 추상 클래스는 상속의 '강제성'을 가집니다. (추상 클래스에도 일반 메소드를 포함할 수 있음) abstract class Animal { abstract void cry(); //추상클래스 void eat() {System.o..

오름차순, 내림차순 정렬 1. 오름차순 import java.util.Arrays; Arrays.sort(배열명); 랜덤으로 0 ~ 99까지의 정수를 score 배열에 저장한 뒤 오름차순으로 정렬하여 출력하는 알고리즘입니다. import java.util.Arrays; public class Main { public static void main(String[] args) { int[] score = new int[8]; System.out.print("Before -> "); for(int i = 0; i < score.length; i++) { score[i] = (int)(Math.random() * 100); System.out.print(score[i] + " "); } System.out.pr..