본문 바로가기

Programming/algorithm

백준 10844번 쉬운 계단 수 dp 풀이 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net arr[N][L] = arr[N - 1][L - 1] + arr[N - 1][L + 1]=> 길이가 N 일 때, 마지막 수가 L일 경우의 계단 수 주의할 점은 위의 점화식은 L이 (1 ~ 8) 일 때 성립한다. 왜냐하면 0은 +1을 한 1만 허용되고 9는 -1을 한 8만 적용되기 때문이다. 구체적인 점화식은 다음과 같다. L = 0 => dp[N][L] = dp[N - 1][L + 1] L = (1 ~ 8) => arr[N][L] = arr[N - 1][L - 1] + arr[N - 1][L + 1] L = 9.. 더보기
백준 1463 자바 dp 풀이 and bfs 풀이 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net Top-down은 가장 큰 문제를 방문 후 작은 문제를 호출하여 답을 찾는 방식이고, Bottom-up은 가장 작은 문제들 부터 답을 구해가며 전체 문제의 답을 찾는 방식이다. 흔히 top-down은 재귀 호출을, bottom-up은 반복문을 이용해 구현한다. Top-down 방식은 점화식을 이해하기 쉽다는 장점이 있고, Bottom-up 방식은 함수를 재귀 호출하지 않기 때문에 시간과 메모리 사용량을 줄일 수 있다는 장점이 있다. 우선 D[j]를 구한다고 해보자 (1 더보기
백준 1932 자바 DP 풀이 연두색 부분은 j == 0 일때 하늘색 부분은 i == j 일때 보라색 부분은 둘다 해당되지 않는 경우이다. 현재 i 행의 j번째 위치까지의 최대 합은 i행의 j번째로 입력 받은 값 triangle[i][j]와 이전 i - 1행의 j - 1번째 triangle[i - 1][j - 1] 혹은 j번째까지의 합 triangle[i - 1][j] 중 최대값을 더한 값이다. 단, 0번째 위치의 값은 j - 1번째가 존재하지 않고 삼각형의 끝 위치에 있는 값은 j번째 값이 존재하지 않으므로 예외 처리를 해준다. 코드로 나타내면 다음과 같다. import java.io.*; import java.util.StringTokenizer; public class t1932 { static int[][] triangle; .. 더보기
백준 2579 자바 풀이 계단오르기는 Dynamic programming 초반에 가자 많이 연습하게 되는 문제입니다. DP를 왜 사용할까? DP는 기본적으로 중복으로 여러번 계산되는 것을 막기위해 고안된 방법입니다. 예를들어 파스칼의 삼각형에 경우 이항계수의 앞 계수를 구할때 사용하는 방법인데, 중복되느 경우가 있습니다 이 중복 계산이 시간을 반복적으로 잡아먹게되어 시간 초과 나는 경우가 발생합니다. DP는 중복값이 나올때마다 이미 계산한 값이라면 계산하지 않고 값이 나오는 방식을 이용합니다. 이때, '중복 값을 미리 계산처리 하는 것'을 중점으로 두고 문제를 풀어야합니다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음.. 더보기
백준 1904 자바 DP 풀이 01 타일은 동적 계획법으로 푸는 문제이다. 01 타일의 특이한 점은 n에 따른 증가폭이 어디서 본 것 같은 모양새로 증가한다. N = 1일 때 1개 (1) N = 2일 때 2개 (00, 11) N = 3일 때 3개 (100, 001, 111) N = 4일 때 5개 (0011, 0000, 1001, 1100, 1111 ) ..... 즉, 1,2,3,5,8.... 이런 식으로 증가하는 게 피보나치 증가하는 것처럼 보인다. 이때, 점화식이 dp [n] = dp [n-1] + dp [n-2] 이므로 그대로 적용하여 풀되 46번째부터 int 범위를 벗어나므로 15746으로 나누어 나머지를 저장한다. import java.io.*; public class t1904 { static final int mod = 1.. 더보기
[APIO 2010] 특공대 (Commando) 풀이 https://www.acmicpc.net/problem/4008 4008번: 특공대 입력은 세 줄로 구성된다. 첫 번째 줄에 전체 병사들 수인 양의 정수 n이 주어진다. 두 번째 줄에 특공대의 조정된 전투력 계산 등식의 계수인 세 정수 a, b, c가 주어진다. 마지막 줄에 병사들 1, 2, www.acmicpc.net Convex Hull Trick (CHT) 를 이용하는 대표 문제로써 2010년 출제 당시 학생들에게 충공깽을 선사했지만 지금은 국민문제가 되어버린 비운의 문제다. 우선 간단한 O(n3)O(n3), O(n2)O(n2) 해법을 간단히 소개하고 그 뒤 CHT 를 이용한 O(N)O(N) 해법을 소개하도록 하겠다. 1. O(N3)O(N3) 해법 간단한 다이나믹 프로그래밍으로 해결 가능하다. D.. 더보기
백준 2577 java 풀이과정 입력 받은 수, 결과 값의 자리 수 만큼 배열 생성. substring 이용. 한자리씩 잘라 넣음. (지금 생각해보니 %10 하면 substring 안써도 될듯...) for문 과 if 문 활용해서 j와 값이 같아질 때마다 countarr[해당숫자]에 +1씩 더 함. import java.io.*; public class t2577 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.o.. 더보기
2017 kakao blind test question_1 https://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1/ public class question_1 { public static void main(String[] args) { int n = 5; int[] arr1 = {9, 20, 28, 18, 11}; int[] arr2 = {30, 1, 21, 17, 28}; //["#####","# # #", "### #", "# ##", "#####"] String[] result = new String[n]; //type #1 for (int i = 0; i < n; i++) { int arr = arr1[i] | arr2[i]; System.out.println(""+Integer.toBinar.. 더보기

티스토리툴바