꾸준한 개발일기

알고리즘 1. BFS는 재귀와 관계가 없다. DFS는 재귀함수를 사용하여 접근하는게 일반적이다. BFS문제를 처음 접하고 문제에 관한 State Space Tree를 설계했지만 재귀함수로 구성하는데 무언가 문제가 있었다. 재귀함수로 구성하기 적절하지 않음 1. DFS의 경우 보통 재귀호출시마다 파라미터의 값(depth, etc.)을 갱신하여 base case에 도달하면 종료하는 구조이다. 하지만, BFS의 경우 depth를 기준으로 종료하는데 무리가 있었다.(애초에 depth로 접근하는 방법도 아닐뿐더러..) 2. BFS를 위해 큐를 사용했기 때문에 탐색 종료지점은 큐가 비어있는 경우이다. 이를 위해 while문을 사용했는데 while문에서 탈출한다는 것은 모든 방문이 끝났다는 것이고 그럼 재귀호출할 이..

문제를 요약하면 다음과 같다. 이진수 중 다음 성질을 만족하는 수를 이천수라고 한다. 1. 0으로 시작하지 않는다. 2. 1이 두번연속으로 나타나지 않는다. 숫자의 길이 N이 주어졌을 때, N자리 이천수의 개수를 구하시오. 설계 Dynamic Programming (동적계획법) 문제를 설계할 땐, 인접한 Computation Level 간의 "어떠한 재귀식"이 성립하는가? 를 파악하는 것이 전부이다. 다시 말해, Recursive Property를 Establish 해야한다. Recursive Property Establish 이를 위해선 계산단계를 어떻게 구분할 것인지 생각해봐야하고, 이에 따라 바로 풀리는 수준의 문제단계 (Lowest Level)에 대해서도 생각해봐야 한다. 즉, 아래와 같이 계산단..

문제를 요약하면, N개의 수로 이루어진 수열 A1, A2, ..., An 합이 n-1개인 정수 ex) 2 1 2 1 (차례대로 +, -, *, / 의 사용개수) => A1 + A2 + A3 - A4 * A5 * A6 / A7 A1 * A2 + A3 / A4 + A5 - A6 * A7 etc. 가장 큰 수와 작은 수는? 단, A1 ~ An 수의 순서는 고정. 연산자 우선순위 무시하고 앞에서부터 연산. 설계 변수정의 및 SST 설계 알고리즘 진행 시 필요한 변수를 파악하고 용도의 정의를 정확히 짚고 넘어가는 것이 굉장히 중요하다. State Space Tree를 생성하고 몇단계 진행해보면서 필요한 변수가 무엇인지 파악하고 변수들을 정리하자. 위의 그림처럼 SST에서 "방문"을 나타내고 연산순서를 저장하기 위..

Backtracking 문제는 설계 1. 문제를 어떻게 State Space Tree로 나타낼 것인가? 2. Promising Function은 어떻게 설정할 것인가? 구현 1. 재귀함수로 재귀적으로 트리를 탐색할 때 파라미터로 갱신해야하는 값은 있는가? 2. SST의 노드들의 방문과 되추적을 어떻게 코드로 나타낼 것인가? 3. 재귀함수의 basecase는 어떻게 설정해야 하는가? 설계상의 문제와 구현상의 문제를 모두 고려해야 한다. 설계 시도1 (실패) 설계 시도2 (성공) 설계1과 설계2의 차이는 "자식의 방문여부 기록"이다. N=3 M=3 이면 1~3까지의 숫자를 중복없이 M개를 고른 수열이므로 answer = 123, 132, 213, 231, 312, 321이 될 것이다. for (int i=1..

Backtracking 개념 주어진 문제를 트리(State Space Tree)로 어떻게 표현할지, 문제에 맞는 유망성검사(Promising function)는 어떻게 구성할지 설계상의 고민이 끝났다면 어떻게 코드로 나타내고 구현할지 코드상의 고민이 필요하다. 코드구현상의 고민 1. 트리의 묵시적 표현과 어떤 자료구조로 대체할 것인가? 트리는 우리가 구현할 알고리즘의 흐름을 파악하기 위한 용도이기 때문에 반드시 구현할 필요는 없다. 또한, 트리로 구현하지 않는다면 어떠한 자료구조로 대체하여 방문과 되추적을 표현할 것인가도 고민해줘야 한다. 예시 예를들어보자. 4-Queens Problem (4개의 Queen들을 서로 위협이 되지 않게 4 X 4 행렬에 배치하는 문제)의 SST는 다음과 같을 것이다. 어떤..

결론 0/1 배낭문제 (by DP Alg) 시간복잡도: O(2^n) (비효율적) 또한, 재귀식을 위해 사용한 이중배열이 sparse matrix 형태로써 공간의 낭비도 심하다는 것을 확인할 수 있다. 구현은 해보고 넘어가자. public class KnapSack { static int numitem = 3; static int weightlimit= 30; static int[][] P = new int[numitem+1][weightlimit+1]; static int[] profit = {0, 50, 60, 140}; static int[] weight = {0, 5, 10, 20}; public static void main(String[] args) { System.out.println(knap..

오답풀이 설계 원하는 쇠막대의 길이 [ 5, 4, 6, 2 ] 가 주어졌을 때, 첫번 째 자르는 경우의 수는 1) 5를 잘랐을 때 5 * (4 + 6 + 2) = 60 2) 2를 자랐을 때 (5 + 4+ 6) * 2 = 30 매 번 자를 때마다 작은 값을 곱하도록 설계하자. 즉, 양 끝단 중 작은 값을 곱하도록 설계하였음. 또한, 자른 막대기는 배제하기 위해 자를 때마다 ArrayList의 remove operation으로 해당 막대기를 삭제하였음. public class Prob16208 { public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader br = new BufferedRead..

논리적인 생각을 "어떻게" 구현해낼 것인지는 굉장히 중요하다 1. List plan[2, 1, 5, 3, 2, 1, 3] , Set plug[2, 1, 5]. 플랜리스트는 사용하는 가전제품의 순서, 플로그세트는 플로그에 꽂힌 가전제품이라고 해보자. 한 번에 하나씩만 플로그의 가전제품을 교체할 수 있고, 교체횟수를 최소화해야한다고 해보자. 플로그에 2, 1, 5 가전제품이 꽂혀있으니, 2, 1, 5가 다음번에 언제 등장하는지 길이(시간)을 통해 비교해야할 것이다. 내생각 plug에 가전제품이 꽂힐 때마다, last index를 별도로 만들어서 다음번 등장까지의 시간을 측정하려했다. 즉, 현재 last = 2이고 2가 등장하는 index에 last를 빼주어서 시도하려고 했다. 개선 sublist를 활용 su..

배열의 각 Elem을 곱하여 더한 값을 구하라 ex) arr = [1, 3, 5, 9] → {1*3 + 1*5 + 1*9} + {3*5 + 3*9} + {5*9} 방법1) 이중 for문 사용 for (int i=0; i