문제본문 입력 [물건의 개수] [최대 무게] 4 7 [물건 무게] [물건 가치] 6 13 4 8 3 6 5 12 ________________ 출력 [최대 가치] 14 동적프로그래밍의 대표 문제 불리는 Knapsack 알고리즘은 dp를 사용하여 무게와 가치 두 가지 요소로 가질 수 있는 최대 가치를 구하는 문제 유형이다. 문제 해설 동적프로그래밍은 dp를 어느 부분으로 잡는 지가 관건 인듯하다. Knapsack은 이중 배열로 dp를 설정한다. dp[i][j]라고 가정하면, i번째까지 물건을 집어 넣는 다고 했을 때, 남아있는 무게가 j라면 얻을 수 있는 최대가치를 뜻한다. 해당 알고리즘은 테이블로 과정을 묘사하면 이해가 더 쉽다. 무게 1 2 3 4 5 6 7 1번째 물건 0 0 0 0 0 13 13 2..
문제 본문 동적 프로그래밍이란 동적 프로그래밍 방법은 문제의 해결 과정에서 이전에 구했던 과정을 또 다시 반복하여 실행되는 것을 방지하는 방법으로, 불필요한 코드 실행이 줄어 시간을 단축시킬 수 있습니다. 하지만 O(n)의 메모리가 할당 되어야 합니다. 문제 해설 전깃줄은 백준 사이트에서 LIS(Longest Increasing Subsequence)의 응용으로 분류된 문제입니다. N개의 전깃줄을 겹치지 않게 제거해야 하는 최소 개수의 전깃줄을 구해야 합니다. 문제 설명 그대로 풀려고 해서 방법이 도저히 생각나지 않다가 사람들의 힌트를 보고 깨달았습니다. ㅎ.. 해답은 제거가 아니고 설치입니다. 최소 개수의 전깃줄을 제거하여 겹치지 않게 설치된 남은 전깃줄은 겹치지 않게 설치될 수 있는 최대 전깃줄 입니..
문제본문 스도쿠 규칙 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 백트래킹이란 가능하지 않는 집합을 배제하는 완전 탐색(브루트포스)을 의미합니다. 모든 경우의 수를 구하지만 정답이 아닐 확률이 높다면 시도하지 않는 것이죠. 때문에 완전탐색보다 빠른 시간안에 정답을 구현할 수 있습니다. 관련 알고리즘의 흐름과 설명은 참고 링크에 더 자세히 나와 있습니다. 스도쿠 입력 9 x 9 스도쿠판에 0 ~ 9 숫자 값이 들어 있습니다. 빈칸은 여러개 존재할 수 있으며 빈칸은 0으로 표시합니다. 0 3 5 4 6 9 2 7 8 7 8 2 1 0 5 6 0 9 0 6 0 2 7 8 1 3 ..
문제 본문 하노이 탑의 규칙 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 하노이 탑은 재귀 함수로 구현하는 대표적인 문제입니다. 재귀 함수란 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식으로 주어진 문제를 푸는 방법입니다.풀고자 하는 문제가 동일한 성격의 작은 문제들로 구성되어 있을 때 사용하면 좋습니다. 하노이 탑의 규칙으로 함수의 성격을 분석해보자 문제: N개의 원판을 1번째에서 3번째로 옮긴다. (1): N - 1개의 원판을 1번째에서 2번째로 옮긴다. (2): N번째 원판을 1번째에서 3번째로 옮긴다. (3): N - 1개의 원판을 2번째에서 3번째로 옮긴다. (1)과 (3) 을 보면 N의 크기만 다를 뿐 성격을..
문제 본문 소수는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수입니다. 대표적으로 2, 3, 5, 7.. 등등이 있습니다. 단순 소수 찾기 - O(n^2) public static boolean isPrime(int num) { if (num == 1) return false; for (int n = 2; n < num; n++) { if (num % n == 0 ) { return false; } } return true; } 가장 간단하게 소수를 구하는 방법은 1을 제외하고 자신보다 작은 자연수로 나누어 나머지가 0이 나오는 지 확인하는 것입니다. 하지만 위 방법은 O(n^2)의 시간 복잡도를 가져서 num의 값이 크다면 시간초과를 발생합니다. 제곱근을 활용하여 소수 찾기 -..
완전 탐색 무식해보여도 사실은 최고의 방법일때가 있지요 완전 탐색 알고리즘은 나올 수 있는 모든 경우의 수를 다 구해서 올바른 정답을 구하는 알고리즘 입니다. 완전 탐색을 구현하는 방법은 여러가지가 있지만 이 글에서는 재귀호출로 완전탐색 알고리즘을 구현해보도록 하겠습니다. 소수 찾기 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요. 제한 상황 nu..
