Algorithm/유형별 풀이 template

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..