Algorithm 썸네일형 리스트형 가장_긴_증가하는_부분수열[BOJ_11053] 오늘은 BOJ 11053 문제인 가장 긴 증가하는 부분수열을 구하는 문제를 풀어보겠습니다. 마찬가지로 DP 방식대로 풀 것 입니다. DP 관련 문제를 많이 풀다보면 DP가 적응되어서 상당히 유형을 확인하는 눈이 넓어지는 것 같습니다. DP(다이나믹프로그래밍)에서 가장 중요한 것은 점화식입니다.Top-Bottom 이던 Bottom-Up 이던 결국 N번째 식에서의 점화식이 중요합니다.그리고 이를 메모하는 배열을 만들어줍니다. d 또는 dp로 배열 이름을 설정해주고 풀게 되면 됩니다. DP는 문제를 많이 풀고 유형을 익혀야 합니다. 따라서 설명을 줄이고 문제에서 유형을 체크해보겠습니다. N이 현재 1000 이하 입니다.따라서 자료형을 int로해서 진행해도 됩니다.또한 이러한 문제는 DP 방식으로 풀 경우, 먼.. 더보기 Back-Tracking 알고리즘 Back-Tracking 알고리즘이란? 기본적으로 탐색을 기반으로 한 알고리즘입니다. DFS 던 BFS 던 모두 다 쓰이는 방법으로, 탐색의 횟수가 많을 때, 답으로 가지 않는 트리는 과감히 버리고, 답으로 갈 만한 트리만 가지치기 하여서 체크하는 방법입니다. 소개에서도 말씀드렸듯, 답으로 갈 수 있는 상태 공간 트리를 만들어서 탐색 횟수를 기가막히게 줄입니다. 아래 그림을 참조해봅시다. 백트래킹은 위에 그림으로 설명이 끝난다.한 노드에 있어서 이어지는 경로 중 해결책으로 이어지지 않을 경우 더이상 따라가지 않아서시도 횟수를 줄게 만든다. (가지치기 방식) --> 불필요한 경로는 조기에 차단 이는 깊이 우선 탐색의 문제를 해결해줍니다.깊이 우선 탐색은 경우의 수가 많으면 처리하기 힘듭니다.가령, 8-Qu.. 더보기 DFS알고리즘 DFS 알고리즘이란? 깊이 우선 순회로 그래프에서 자식 노드를 다 찾아간 다음에 다음 인접 노드로 이동하는 알고리즘으로횟수 N (노드)이 많을 경우 깊이 우선 탐색은 사용하기에는 많이 제약이 있을 것입니다.깊이 우선 탐색에서는 인접행렬 또는 인접 리스트로 푸는 두 가지 방법이 있습니다.공간복잡도를 줄이고자 저는 인접리스트로 풀겠습니다. 이 전에 BFS(너비우선순회)를 잠깐 다뤘었는데, 마찬가지로 DFS도 비슷하게 진행됩니다.단, BFS와 다른 점은 Queue가 아닌 Stack을 사용해서 푼다는 점입니다.이유는, BFS는 한 번에 여러 노드를 확인하면서 체크하지만, DFS는 자식노드를 먼저 다 거친 다음에 이웃 노드를 체크하기 때문에 노드간의 순서가 중요합니다. 따라서 쌓여서 순서가 정해져있는 스택을 사용.. 더보기 BOJ1182_부분집합의 합의 갯수 부분 집합의 합 갯수 문제는 여러 방법으로 풀 수 있는데, 이번 포스팅에서는 Back Tracking 방법과 비트마스크 방법으로 풀어보겠습니다. 보통 부분집합의 합을 구하는 것은 비트마스크 방법으로 푸는 것이 가장 좋지만, 재귀 함수를 이용한 Back Tracking 방법을적용해서도 풀어보려 합니다. 우선 비트마스크 방법을 사용해서 풀어보겠습니다. 비트 마스크의 기본 공식부터 체크하고 가겠습니다. A > B: A / 2^B A & ( 1 더보기 BOJ_1987_알파벳문제 이번에는 알파벳 문제를 풀어볼텐데, 이는 기존 BFS문제의 전형적인 문제이며 BackTracking을 활용한 문제입니다.보통 재귀함수로 BFS를 구현한다면 BackTracking을 한다고 생각하시면 될 것 같습니다. [문제] 문제를 확인해보면, 알파벳으로 이루어진 배열 하나와 해당 위치를 지났는지 체크하는 배열을 만들면 될 것 같다는 생각이 듭니다.처음에는 2,4가 2행 4열을 나타낸다고 생각하여 CAAB와 ADCB는 아래와 같다고 생각했습니다. C A A BA D C B 2x4 행렬 그치만 자바에서는 굳이 다음과 같이 구현할 필요가 없었습니다. 1차원 배열에 CAAB와 ADCB를 다 넣어두고 이를 charAt함수를 이용하여 각 요소들을 찾아가면 되기 때문입니다. CAAB와 ADCB를 담는 배열 하나를 .. 더보기 BOJ_9663_N-Queen 두기 이번 N_Queen 문제에서는 BFS의 심화버전인 Back Tracking, 다른 말로 퇴각검색법에 대해서 알아볼 것입니다. [문제] N-Queen 문제를 해석하는 데에도 저는 조금 오래 걸렸습니다.체스를 어릴 때 해보고 안해봐서도 있지만 생각을 어떻게 다르게 하느냐에 대해서도 고민이 많았기 때문입니다. 기존 풀이 방법은 앞서 설명한 대로Queue를 만들고 Queue에서 맨 앞에 있는 것을 빼가면서 큐가 비어 있지 않다면 계속해서 반복문을 돌리도록 구현하였습니다.또한 이미 지나간 곳이라면 boolean 배열의 값을 true로 주어서 다음에는 해당 노드를 방문하지 않도록 만들었고,이동하면서 dist라는 배열로 해당 노드에서 다음 노드로 이동할 때 +1을 해주면서 값을 관리하였습니다. BFS 문제가 다음과 .. 더보기 BOJ_암호만들기_1759 BOJ 1759번 암호만들기입니다. 문제는 아래와 같습니다. 문제에서 모음은 최소 한 개 이상 자음은 최소 두 개 이상 사용해서 여러 종류의 암호를 만들라고 하였으므로,우선 현재까지 만들어진 암호 방식이 모음을 최소 한 개 이상 사용하였고, 자음을 최소 두 개 이상 사용했는지 체크해야 한다.이 전에 BFS에서 해당 노드를 방문했는지 여부를 파악했던 boolean 배열을 만들거나 boolean값을 반환하는 함수를 만들면 된다. 다음으로는 재귀 함수로 돌아갈 함수를 만들어야한다.구조를 생각해보자 입력 받은 알파벳이 하나씩 패스워드에 입력되면서 재귀 함수가 돌아갈 것이고, 4자리의 암호를 만들려고 했기 때문에만들어진 패스워드의 길이가 4자리가 맞고 모음 1개 이상 , 자음 2개 이상이 맞다면 출력하도록 구현하.. 더보기 BOJ_9095_1,2,3 더하기 문제는 다음과 같다. 재귀 함수를 이용해서 풀어보려한다. 본 문제에서 중요한 핵심은 아래와 같은 함수를 만들어내는 것이다. private static int solution(int count, int sum, int goal) {if (sum > goal)return 0;if (sum == goal)return 1; // 바로 같을 경우는 1 출력 (1회) int ans = 0;//System.out.println(count + " / " + sum + " / " + goal);for (int i = 1; i goal)return 0;if (sum == goal)return 1; // 바로 같을 경우는 1 출력 (1회) int ans = 0;//System.out.println(count + " / " .. 더보기 이전 1 2 3 4 5 6 다음
