'algorithm' 카테고리의 글 목록 (30 Page)

코드

정답 코드 : 처음 풀어 본 트리 문제이다. 노드 클래스를 생성하여서 클래스 배열로 접근하였다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	static class NODE {
		String val;
		int parent, right, left;

		public NODE(String val) {
			this.val = val;
			this.parent = this.right = this.left = -1;
		}
	};

	static int N;
	static NODE array[];
	static String s;

	static void preOrder(int node) {
		System.out.print(array[node].val);
		if (array[node].left > -1)
			preOrder(array[node].left);
		if (array[node].right > -1)
			preOrder(array[node].right);
	}

	static void inOrder(int node) {
		if (array[node].left > -1)
			inOrder(array[node].left);
		System.out.print(array[node].val);
		if (array[node].right > -1)
			inOrder(array[node].right);
	}

	static void postOrder(int node) {
		if (array[node].left > -1)
			postOrder(array[node].left);
		if (array[node].right > -1)
			postOrder(array[node].right);
		System.out.print(array[node].val);
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		array = new NODE[26];
		N = Integer.parseInt(br.readLine());
		
		for (int i = 0; i < 26; i++) {
			array[i] = new NODE(Character.toString((char) (i + 'A')));
		}
		
		for (int i = 0; i < N; i++) {
			char a, b, c;
			s = br.readLine();
			a = s.charAt(0);
			b = s.charAt(2);
			c = s.charAt(4);
			if (b != '.') {
				array[a - 'A'].left = b - 'A';
				array[b - 'A'].parent = a - 'A';
			}
			if (c != '.') {
				array[a - 'A'].right = c - 'A';
				array[c - 'A'].parent = a - 'A';
			}
		}
		preOrder(0);
		System.out.println();
		inOrder(0);
		System.out.println();
		postOrder(0);
		System.out.println();
	}
}

'algorithm' 카테고리의 다른 글

[JAVA] 백준 17070번 : 파이프 옮기기 1 (0)	2020.10.07
[JAVA] 백준 11051번 : 이항 계수 2 (0)	2020.10.06
[JAVA] 백준 12865번 : 평범한 배낭 (0)	2020.10.05
[JAVA] 백준 11401번 : 이항 계수 3 (0)	2020.10.04
[JAVA] 백준 10989번 : 수 정렬하기 3 (0)	2020.10.04

코드

정답 코드 : st-lab.tistory.com/141를 통해 이해한 바로 작성하였다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
 
		int[] weight = new int[N + 1];
		int[] value = new int[N + 1]; 
		int[] dp = new int[K + 1];
 
		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			weight[i] = Integer.parseInt(st.nextToken());
			value[i] = Integer.parseInt(st.nextToken());
		}
 
		for (int i = 1; i <= N; i++) {
			for (int j = K; j - weight[i] >= 0; j--) {
				dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
			}
		}
		System.out.println(dp[K]);
	}
}

'algorithm' 카테고리의 다른 글

[JAVA] 백준 11051번 : 이항 계수 2 (0)	2020.10.06
[JAVA] 백준 1991번 : 트리 순회 (0)	2020.10.05
[JAVA] 백준 11401번 : 이항 계수 3 (0)	2020.10.04
[JAVA] 백준 10989번 : 수 정렬하기 3 (0)	2020.10.04
[JAVA] 백준 11052번 : 카드 구매하기 (0)	2020.09.30

코드

정답 코드 : onsil-thegreenhouse.github.io/programming/problem/2018/04/02/problem_combination/를 참고해서 이해하였다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        long[] factorial = new long[N+1];
        factorial[0] = 1;
        factorial[1] = 1;
       
        for(int i=2; i<=N; i++) factorial[i] = (factorial[i-1]*i)%1000000007;
        long denominator = (factorial[K]*factorial[N-K])%1000000007;

        long index = 1000000007-2;
        long fermatNum = 1;
        while(index > 0){
            if(index%2==1){
                fermatNum *= denominator;
                fermatNum %= 1000000007;
            }
            denominator = (denominator*denominator)%1000000007;
            index /= 2;
        }
        long result = ((factorial[N]%1000000007)*(fermatNum%1000000007))%1000000007;
        System.out.print(result);

    }
}

정답 코드 : 위의 코드보다 메모리도 1/4정도 잡아먹고, 속도도 위의 코드보다 좀 더 빠르다. 페르마의 소정리를 이용ㅇ해서 푼 코드이다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/* [페르마의 소정리] _ 혜민 코드 참고
a^(p-1) % p = 1
(a/b) % M = ((a % M) * (b^-1 % M)) = ((a % M) * (b^(M-2) % M))
*/

public class Main {
    static final int MOD = 1000000007;
	
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        long a = fac(N);
        long b = fac(N - K) * fac(K) % MOD;
        long result = a * pow(b, MOD - 2) % MOD;
        System.out.print(String.valueOf(result));
        
    }

    public static long fac(long n) {
        long result = 1;
        while (n > 1) {
            result = (result * n) % MOD;
            n--;
        }
        return result;
    }

    public static long pow(long a, int b) {
        long result = 1;
        long temp = a;

        while (b > 0) {
            if (b % 2 == 1) result = result * temp % MOD;
            b = b / 2;
            temp = (temp * temp) % MOD;
        }

        return result;
    }
}

'algorithm' 카테고리의 다른 글

[JAVA] 백준 1991번 : 트리 순회 (0)	2020.10.05
[JAVA] 백준 12865번 : 평범한 배낭 (0)	2020.10.05
[JAVA] 백준 10989번 : 수 정렬하기 3 (0)	2020.10.04
[JAVA] 백준 11052번 : 카드 구매하기 (0)	2020.09.30
[JAVA] 백준 1932번 : 정수 삼각형 (0)	2020.09.29

코드

실패 코드 : 시간 초과

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		int[] array = new int[N];
		
		for(int i = 0; i < N; i++) {
			array[i] = Integer.parseInt(br.readLine());
			
			for(int j = i - 1; j >= 0; j--) {
				if(array[j] > array[j+1]) {
					int temp = array[j];
					array[j] = array[j+1];
					array[j+1] = temp;
				} else break;
			}
		}
		
		for(int i = 0; i < N; i++)
			System.out.println(array[i]);
	}
}

실패 코드 : 메모리 초과 append(array[i] + "\n")를 append(array[i]).append("\n")로 바꾸니까 메모리 초과가 안뜨긴 함.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int N = Integer.parseInt(br.readLine());
		int[] array = new int[N];
		
		for(int i = 0; i < N; i++) 
			array[i] = Integer.parseInt(br.readLine());
			
		Arrays.sort(array);
		
		for(int i = 0; i < N; i++)
			sb.append(array[i] + "\n");
		System.out.print(sb);
	}
}

성공 코드 : Arrays.sort를 써서 그런지 생각보다 속도가 느리다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int N = Integer.parseInt(br.readLine());
		int[] array = new int[N];
		
		for(int i = 0; i < N; i++) 
			array[i] = Integer.parseInt(br.readLine());
			
		Arrays.sort(array);
		
		for(int i = 0; i < N; i++)
			sb.append(array[i]).append("\n");
		System.out.println(sb);
	}
}

성공 코드 : 위의 것에서 array.sort를 쓰지 않고 인덱스에 해당 숫자를 ++해주면서 출력 해주는 코드이다. 위의 코드보다 1/3 정도 더 빠르게 나온다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Algorithm {
	
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int N = Integer.parseInt(br.readLine());
        int[] array = new int[10001];
        
        for (int i = 0; i < N; i++) 
            array[Integer.parseInt(br.readLine())] ++;
         
        for (int i = 1; i <= 10000; i++) {
            if (array[i] > 0) { 
                for (int j = 0; j < array[i]; j++) 
                    sb.append(i).append("\n");                
            }
        }
        System.out.print(sb);
	}
}

'algorithm' 카테고리의 다른 글

[JAVA] 백준 12865번 : 평범한 배낭 (0)	2020.10.05
[JAVA] 백준 11401번 : 이항 계수 3 (0)	2020.10.04
[JAVA] 백준 11052번 : 카드 구매하기 (0)	2020.09.30
[JAVA] 백준 1932번 : 정수 삼각형 (0)	2020.09.29
[JAVA] 백준 2225번 : 합분해 (0)	2020.09.23

코드

정답 코드 :

민규가 구매하려고 하는 카드의 개수 N = 4, P1 = 1, P2 = 5, P3 = 6, P4 = 7

n개의 카드를 갖기 위해 지불하는 금액의 최댓값을 dp[n]이라고 할 때, 민규가 카드 1개를 갖는다고 한다면 dp[1] = p1이다.

민규가 카드 2개를 갖는다고 한다면 2개가 들어있는 카드팩 1개를 사던가, 1개짜리 카드팩 2개를 사는 경우이다.

dp[2] = MAX(P[2], dp[1] + dp[1])

만약 민규가 카드 3개를 갖는다고 한다면 3개가 들어있는 카드팩을 1개 사던가, 2개짜리 카드팩과 1개짜리 카드팩을 각각 하나씩 사던가, 아니면 1개짜리 카드팩 3개를 사는 경우로 dp[3] = MAX(P[3], dp[2] + dp[1], dp[1] *3)

dp[1] * 3 은 dp[1] * 2 + dp[1]과 같다. dp[2] + dp[1] 과 dp[1] * 2 + dp[1]을 비교할 때, dp[2]와 dp[1] * 2의 비교가 된다.

앞서 dp[2]의 값을 넣을 때 P[2]와 dp[1] * 2 중 큰 값을 dp[2]에 넣었을 때, dp[3] = MAX(P[3], dp[2] + dp[1]) 이다.

마지막으로 민규가 카드 4개를 갖는다고 할 때, dp[4] = MAX(P[4], dp[3] + dp[1], dp[2] + dp[2]) 이다.

따라서, 점화식은 dp[n] = MAX(P[n], dp[n - 1] + dp[1], dp[n - 2] + dp[2] ..., dp[n - n/2] + dp[n/2])

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] array = new int[N + 1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            array[i] = Integer.parseInt(st.nextToken());
        }

        int[] dp = new int[N + 1];

        dp[1] = array[1];

        for(int i = 2; i <= N; i++) {
            dp[i] = array[i];
            for(int j = 0; j <= i / 2; j++)
                dp[i] = Math.max(dp[i], dp[i - j] + dp[j]);
        }

        System.out.println(dp[N]);
    }
}

'algorithm' 카테고리의 다른 글

[JAVA] 백준 11401번 : 이항 계수 3 (0)	2020.10.04
[JAVA] 백준 10989번 : 수 정렬하기 3 (0)	2020.10.04
[JAVA] 백준 1932번 : 정수 삼각형 (0)	2020.09.29
[JAVA] 백준 2225번 : 합분해 (0)	2020.09.23
[JAVA] 백준 9252번 : LCS 2 (0)	2020.09.22

코드

정답 코드 : 한 노드를 기준으로 그 전의 행의 대각선(왼쪽, 오른쪽) 값을 더해서 최대가 되는 값을 현재 노드에 넣어주고 최대가 되는 노드의 값을 출력

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine()); 
        int [][]dp = new int[N+1][N+1];
        int max = 0;

        for (int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= i; j++) {
                dp[i][j] = Integer.parseInt(st.nextToken());

                dp[i][j] = Math.max(dp[i][j] + dp[i-1][j], dp[i][j] + dp[i-1][j-1]);
                max = Math.max(dp[i][j], max);
            }
        }
        
        System.out.println(max);
    }
}

'algorithm' 카테고리의 다른 글

[JAVA] 백준 10989번 : 수 정렬하기 3 (0)	2020.10.04
[JAVA] 백준 11052번 : 카드 구매하기 (0)	2020.09.30
[JAVA] 백준 2225번 : 합분해 (0)	2020.09.23
[JAVA] 백준 9252번 : LCS 2 (0)	2020.09.22
[JAVA] 백준 2631번 : 줄세우기 (0)	2020.09.14

코드

코드 설명 :

만약 입력에 5 3 가 주어졌다고 가정하면 우리는 이를 0+5, 1+4, 2+3, 3+2, 4+1, 5+0로나눌수있다.

0(2번 더해서 0이 되는 경우)+5(1번 더해서 5가 되는 경우)

1(2번 더해서 1이 되는 경우)+4(1번 더해서 4가 되는 경우)

2(2번 더해서 2이 되는 경우)+3(1번 더해서 3가 되는 경우)

3(2번 더해서 3이 되는 경우)+2(1번 더해서 2가 되는 경우)

4(2번 더해서 4이 되는 경우)+1(1번 더해서 1가 되는 경우)

5(2번 더해서 5이 되는 경우)+0(1번 더해서 0가 되는 경우)

즉, DP[2][5] = DP[1][0] + DP[1][1] + DP[1][2] + DP[1][3] + DP[1][4] + DP[1][5] 가 된다.

K와 N으로 바꾸면 DP[K][N] = DP[K-1][0] + DP[K-1][1] + … + DP[K-1][N] 임을 알 수 있다.

풀어서 표로 확인해보면

표를 토대로 좀 더 간단하게 점화식을 세우면 DP[K][N] = DP[K][N-1] + DP[K-1][N-1]라는 것을 유추할 수 있다.

정답 코드 : 나온 DP[K][N] = DP[K][N-1] + DP[K-1][N-1] 식을 사용하여 구현 하였다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());

		int[][] dp = new int[201][201];
		
		for(int i=1;i<=K;i++) {
			dp[i][0]=1;
		}
		for(int i=1;i<=K;i++) {
			for(int j=1;j<=N;j++) {
				dp[i][j] = dp[i][j-1] + dp[i-1][j];
			}
		}
		System.out.println(dp[K][N]%1000000000);
		
	}

}

'algorithm' 카테고리의 다른 글

[JAVA] 백준 11052번 : 카드 구매하기 (0)	2020.09.30
[JAVA] 백준 1932번 : 정수 삼각형 (0)	2020.09.29
[JAVA] 백준 9252번 : LCS 2 (0)	2020.09.22
[JAVA] 백준 2631번 : 줄세우기 (0)	2020.09.14
[JAVA] 백준 3020번 : 개똥벌레 (0)	2020.09.14

코드

정답 코드 : 기존 LCS 길이구하는 알고리즘 + dp배열을 통해 최장길이 문자열도 가져왔다. 문자열은 거꾸로가면서 같으면 추가해준 뒤 --, dp배열의 수가 x-1이 현재위치보다 값이 낮으면 x--, y-1이 현재위치보다 값이 낮으면 y--를 해주면서 반복문을 돌린다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String firstInput = br.readLine();
		String secondInput = br.readLine();

		int[][] dp = new int[firstInput.length() + 1][secondInput.length() + 1];

		for (int i = 1; i <= firstInput.length(); i++) { 
			for (int j = 1; j <= secondInput.length(); j++) { 
				if (firstInput.charAt(i - 1) == secondInput.charAt(j - 1)) { 
					dp[i][j] = dp[i - 1][j - 1] + 1;
				} else { 
					dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);				
				}
			}
		}
		
		int x = firstInput.length();
		int y = secondInput.length();
		StringBuilder sb = new StringBuilder();
		while(x != 0 && y != 0) {
			if(firstInput.charAt(x-1) == secondInput.charAt(y-1)) {
				sb.append(firstInput.charAt(x-1));
				x--;
				y--;
			}
			else if(dp[x][y] == dp[x-1][y])
				x--;
			else if(dp[x][y] == dp[x][y-1]) 
				y--;
		}
		

		System.out.println(dp[firstInput.length()][secondInput.length()]);
		System.out.print(sb.reverse().toString());

	}
}

'algorithm' 카테고리의 다른 글

[JAVA] 백준 1932번 : 정수 삼각형 (0)	2020.09.29
[JAVA] 백준 2225번 : 합분해 (0)	2020.09.23
[JAVA] 백준 2631번 : 줄세우기 (0)	2020.09.14
[JAVA] 백준 3020번 : 개똥벌레 (0)	2020.09.14
[JAVA] 백준 2667번 : 단지번호붙이기 (0)	2020.09.10

선장 일지

algorithm

[JAVA] 백준 1991번 : 트리 순회

'algorithm' 카테고리의 다른 글

[JAVA] 백준 12865번 : 평범한 배낭

'algorithm' 카테고리의 다른 글

[JAVA] 백준 11401번 : 이항 계수 3

'algorithm' 카테고리의 다른 글

[JAVA] 백준 10989번 : 수 정렬하기 3

'algorithm' 카테고리의 다른 글

[JAVA] 백준 11052번 : 카드 구매하기

'algorithm' 카테고리의 다른 글

[JAVA] 백준 1932번 : 정수 삼각형

'algorithm' 카테고리의 다른 글

[JAVA] 백준 2225번 : 합분해

'algorithm' 카테고리의 다른 글

[JAVA] 백준 9252번 : LCS 2

'algorithm' 카테고리의 다른 글

+ Recent posts

티스토리툴바