Algorithm

Two Pointers

개념 문제를 풀기 위해 봐야 할 넓은 영역 중에서 볼 필요가 없는 부분들은 가능하면 안 볼 수 있게 하는 알고리듬 화살표 2개에 의미를 부여해서 탐색 범위를 압축하는 방법! 대표적인 카테고리 1차원 배열 위에 2개의 포인터를 만드는 경우 관찰을 통해 문제에 등장하는 변수 2개의 값을 포인터로 표현하려는 경우 포인터를 조작하는 방향에 대해서 2개의 포인터를 같은 방향으로 이동 2개의 포인터가 양끝에서 서로를 향해 이동 Two Pointers 문제들이 가지는 키워드 1차원 배열에서의 "연속 부분 수열" or "순서를 지키며 차례대로" 곱의 최소 문제 풀이 BOJ 1806 - 부분합 난이도 : 3 10

Binary Search

개념 정렬이 보장되어 있는 배열에서 특정 기준을 가지고 배열을 이분하면서 탐색하는 방법 시간복잡도 : O(log N) 활용 방안 항상 전형적인 변수 세팅을 가지고 시작 L : 탐색할 가치가 있는 왼쪽 끝 index R : 탐색할 가치가 있는 오른쪽 끝 index result : 탐색한 x의 위치 로직 L과 R 사이의 가운데 지점의 값을 확인하면서 L과 R을 계속해서 옮겨주고, 최종적으로 x와 일치하는 값, 혹은 x와 가장 가까운 값을 찾아냄 L > R 이 되어버리면 탐색할 가치가 있는 구간이 더이상 없다는 뜻 효율성 구간의 길이는 N → ½ N → ¼ N → ... → 1 의 방식으로 점점 좁아짐 총 비교 횟수는 구간의 변화 횟수인 O(log N) 예를 들어 N이 10만이라면 약 16번만 비교해도 되는 ..

Sort Application

활용 방안 자바의 경우 Comparable을 활용해서 구현 가능 static class Element implements Comparable { public int idx, num; @Override public int compareTo(Element other) { return num - other.num; } // 음수 값이 나오면 내가 먼저, 양수 값이 나오면 other가 먼저 // 위 비교식은 오름차순 정렬 } 시간복잡도 : 약 O(N log N) 각종 복잡한 Sorting Algorithm들은 차치해두고 자바의 Arrays.sort(arr) 메소드를 기준으로 봤을 때 sort 메소드는 Primitive 원소의 경우 Dual-Pivot Quick Sort를, Object 원소의 경우 Tim Sor..

Brute Force

개념 정답을 무조건 구하는 치트키 문제를 해결하기 위해 가능한 경우의 수를 모두 탐색 특히 backtracking, 재귀 함수를 활용해야 하는 문제 모든 코딩 테스트에서, 부분 점수라도 얻기 위해서 기본적으로 접근할 수 있어야 함 일반적으로 시간복잡도가 높은 편 종류 (문제 유형) N개 중에서 중복을 허용하면서 중복을 허용하지 않고 M개를 순서에 따라 나열하라 골라라 N개 중에서 중복을 허용하면서 M개를 순서에 따라 나열하라 BOJ 15651 - N과 M (3) static StringBuilder sb = new StringBuilder(); static int N, M; static int[] selected; static void recursive(int k) { if (k == M + 1) { f..

0-1 Knapsack Problem | Dynamic Programming

Problem n개의 아이템의 무게와 가치가 주어지고, 이 아이템들을 W 만큼의 용량을 가진 가방에 넣을 수 있는 최대치로 넣고자 한다. 좀 더 프로그래밍적으로 얘기하자면, 두 정수 배열 val[0, .. , n-1]와 wt[0, .. , n-1]는 각각 아이템의 가치와 무게를 나타내고, 주어진 정수 W는 가방의 용량을 나타낸다. 여기에서 부분집합의 총 무게가 W 보다 작거나 같은, val[]의 최대 부분 집합을 구하라. 아이템을 부술 수 없으며, 또한 하나의 온전한 아이템을 취하거나 취하지 않아야만 한다. (0-1 property) Example Recursion OR Exhaustive Search Solution Approach 간단한 해결책은 아이템들의 모든 부분집합의 무게와 가치를 확인하는 것이..

Ugly Numbers

Problem Ugly Numbers는 2, 3, 5로만 나누어 떨어지는 수이다. 11개 정도만 나열해보자면 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15가 된다. 참고로 맨 처음의 1은 편의상 들어가 있는 숫자이다. Ugly Numbers 문제에서는 숫자 n이 주어지며, n번째 Ugly Number를 리턴해야 한다. Example Input : n = 7 Output : 8 Input : n = 10 Output : 12 Input : n = 15 Output : 24 Input : n = 150 Output : 5832 Dynamic Programming Solution Ugly Number에서 1을 제외한 모든 수는 2, 3, 5로 나누어지기 때문에 다음과 같이 그룹을 3개로 나눌 ..

Longest Increasing Subsequence(LIS) | Dynamic Programming

Problem Longest Increasing Subsequence(LIS) 문제는 주어진 배열의 subsequence들 중에서 오름차순으로 정렬되었으며, 그 중에서도 길이가 가장 긴 subsequence를 찾아내는 문제이다. What is subsequence? 배열 {1, 2, 3}의 subsequence는 {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} 이다. 이 배열의 LIS를 굳이 따지자면, {1, 2, 3}이 된다. Example 위와 같은 배열이 주어졌을 때, LIS는 {10, 22, 33, 50, 60, 80}이 되고, 그 길이는 6이 된다. Input: arr[] = {3, 10, 2, 1, 20} Output: Length of LIS = 3 T..

Coin Change | Dynamic Programming

Problem 주어진 N이라는 값이 있다. 우리의 목적은 N cents에 대한 잔돈을 만드는 것이며, 우리는 각각 S={S1, S2, .. , Sm} 만큼의 가치를 가지는 동전들을 무한대로 공급할 수 있다. 잔돈을 만들기 위한 경우의 수는 몇인가? 여기서 동전들의 순서는 따지지 않기로 한다. Example 1) N = 4 and S = {1, 2, 3} 이 경우 4가지 해결책이 있다. {1,1,1,1}, {1,1,2}, {2,2}, {1,3} 2) N = 10 and S = {2, 5, 3, 6} 이 경우 5가지 해결책이 있다. {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5}, {5,5} Recursive Solution function count(S, m, n) { if (n ..

Sudoku | Backtracking

Approach 스도쿠의 칸 들 중에서 비어있는 칸들에 값을 하나씩 할당해보면서 해결하는 방식이다. 숫자를 할당하기 전에, 스도쿠의 규칙을 깨뜨리지 않는지 확인하는 로직이 필요하다. 그러기 위해서 같은 행이나 같은 열, 같은 3X3 subgrid에 넣으려는 숫자와 동일한 숫자가 있는지 없는지 판별해야만 한다. 넣으려는 숫자가 스도쿠 규칙을 깨지 않는다는 것이 확인된 이후에, 숫자를 할당하고 재귀적으로 해당 숫자가 해결책에 도달할 수 있는지 없는지 확인해야 한다. 만약 할당된 숫자가 해결책에 도달하지 못한다면, 그 다음 숫자를 현재의 빈 칸에 대해 다시 시도해본다. 이 작업을 1부터 9까지 다 시도해봤음에도 해결책을 찾아내지 못한다면, false 값을 리턴하고 해결책이 없음을 알린다. Algorithm 할..