전체 글 (89) 썸네일형 리스트형 [코딩테스트][알고리즘] 4. DP( Dynamic Programming) 다이나믹 프로그래밍 다이나믹프로그래밍의 기본적인 아이디어는 한 번 풀었던 문제를 다시 풀지 말자! 라는 것이다. 풀었던 문제의 답을 배열에 저장해놓고 필요할때 다시 사용함으로써 시간복잡도를 줄일 수 있게 된다. 이러한 과정을 메모이제이션(Memoization) 이라고한다. 이러한 메모이제이션을 거치면 저장할 공간이 필요하기에 공간복잡도는 불리해지지만, 시간복잡도는 유리해진다. DP는 분할정복기법( 해결했던 문제도 다시 계산 )을 개선 한 것 인데, 대표적인 예가 피보나치수열을 구하는 것이다. 피보나치 수열은 1 1 2 3 5 8 13 21 34 - - - 와 같이 D[i] = D[i-1] + D[i-2] 의 공식에 의해 진행되는 수들의 나열이다. 분할정복기법을 사용하여 피보나치 수열의 6번째 수를 구하는 과정은 다음과 같다.. JAVA - 백준 알고리즘 - 14852 타일 채우기 3 이 문제는 DP를 사용해서 풀 수 있다. N의 수가 크기때문에 1차원 dp를 사용한다면 시간초과가 된다. 그러므로 2차원 배열을 이용하여 dp를 해주면 된다. 또한 값을 저장하는 배열의 값이 21억이 넘는 경우가 발생하여 int 형으로 선언한다면 런타임에러가 뜨는 것만 조심해야한다. 이해가 잘 되지 않으면 아래 추천 영상을 보면서 이해하길 바란다. import java.util.Scanner; public class Main { private static final int MOD = 1000000007; static long[][] arr; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nex.. JAVA - 백준 알고리즘 - 2718 타일 채우기 https://www.acmicpc.net/problem/2718 이 문제는 DP를 사용하여 풀 수 있다. 코드는 다음과 같다. 자세한 설명이 필요하다면 아래 추천영상을 참고하길 바란다. import java.util.Scanner; public class Main { static int[] arr = new int[1001]; static int[] N; static int result, a; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N1 = sc.nextInt(); N = new int[N1+1]; for(int i = 0; N1>i ; ++i) { N[i] = sc.nextInt(); } for.. JAVA - 백준 알고리즘 - 2133 타일 채우기 https://www.acmicpc.net/problem/2133 이 문제는 DP (동적 계획법) 알고리즘을 사용하면 풀 수 있는 문제이다. 자세한 설명은 주석을 참고하면 된다. dp를 풀때는 아무것도 하지 않는 경우도 경우의 수 1로 본다는 것을 알아두어야겠다. import java.util.Scanner; public class Main { static int[] arr = new int[31]; // dp 값 저장을 위한 배열 static int result; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); // 입력 System.out.print(dp(N)); // 출.. JAVA - 백준 알고리즘 - 1700 멀티탭 스케줄링 이 문제는 그리디 알고리즘을 이용해 푸는 문제이다. 처음 생각하기로는 앞으로 꽂아야 할 용품의 수가 많으면 오래 남아 있도록 해야 정답이 나올 것이라 생각했다. 하지만 그렇게 풀이를 작성했더니 몇몇 테스트 케이스를 통과하지 못했다. 다시 생각한 결과 멀티탭에 꽂혀 있는 용품들 중 가장 나중에 사용될 것을 먼저 뽑도록 바꾸었다. 너무 오랫동안 문제를 풀고 추가하다보니 코드가 많이 복잡해졌다. 최적화를 하면 코드를 많이 줄일수 있을 거 같지만 지금 당장은 이 코드를 수정하고 싶은 생각이 들지 않는다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringT.. JAVA - 백준 알고리즘 - 1080 행렬 이 문제는 그리디 알고리즘으로 쉽게 풀 수 있는 문제이다. 두 개의 배열에 입력을 받고 0,0부터 차례대로 두 배열의 원소가 같은지 비교해주면 된다. 만약 배열의 원소가 같지 않다면 3x3에 해당되는 원소를 true에서 false로 , false에서 true로 바꿔주고 count를 1 증가시켜주면 된다. 배열의 인덱스 범위에 대해서 조금만 신경을 쓴다면 쉽게 맞을 수 있는 문제인 것 같다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int N, M, count, temp; s.. JAVA - 백준 알고리즘 - 1969 DNA 이 문제는 알고리즘 스터디를 하는 도중 강사님께서 그리디 알고리즘 연습문제로 추천해주신 것이다. 차례대로 문자열을 입력받아 각각의 자리에 들어가는 A C G T의 개수를 세어주고 Math.max() 함수를 이용하여 갯수를 비교해주었고 가장 큰 값을 차례대로 입력했다. 입력할 때 사전 순으로 정렬하기 위해서 A C G T의 순서로 for문을 작성하였다. max가 아닌 알파벳의 모든 갯수를 더해주어 Hamming Distance를 얻었다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { stati.. 컴활 1급 필기 독학 합격 공부방법, 후기 컴활 1급 필기시험을 친 후기와 공부방법에 대해서 알려드려고 합니다. 저는 컴활 필기가 첫 자격증 시험입니다. 그래서인지 컴활 공부를 시작하기 전에 별로 무서움이 없었습니다. 먼저 시험을 접수해 놓고 거의 까먹고 있다가 2일 전에 급하게 공부를 시작했습니다. 하지만 막상 공부해보니 그렇게 쉽지만은 않았습니다. 저는 운 좋게 거의 60점 가까운 점수로 통과했지만, 한 번에 확실하게 통과해야겠다! 하시는 분들은 저보다 공부를 더 많이 하고 가셔야 할 것 같습니다! 제가 공부했던 방법을 소개해드리겠습니다. 1. 공부기간 : 2일 ( 하루 6시간 정도) 2. 공부방법 : cbt 사이트에서 기출문제 반복 1단계 : 해설 보고 답을 기억한다는 느낌으로 반복 2단계 : 해설 없이 70~80점 나올 때까지 반복 3단계.. 이전 1 ··· 7 8 9 10 11 12 다음
