mondegreen

백트래킹의 개념 해를 찾는 도중 해가 아니면, 되돌아가서 다시 해를 찾아가는 방법 => 모든 가능한 경우의 수 중 특정한 조건을 만족하는 경우만 살펴보는 방법 => 만족하지 않는 것이 확인되면 부모 노드로 돌아가 다음 자식 노드를 확인한다. => 가지치기라고 말하는데 불필요한 부분을 굳이 연산하지 않아 효율적이다. => 최악의 경우에는 여전히 지수함수 시간을 요할 수 있어 반드시 답을 얻는 것은 아님 깊이우선탐색(DFS) + 가지치기(Pruning) DFS만으로는 답이 될 수 없는 경우도 모두 리프까지 탐색하므로 이 때 특정 조건문을 작성하여 조건에 해당하지 않으면 해당 경로를 가지는 않는 가지치기 방식을 적용해 백트래킹을 구현할 수 있다. 백준 9663 import java.util.Scanner; p..

분할정복의 개념 1) 분할: 해결할 문제를 여러 개의 작은 부분으로 나누기 2) 정복: 나눈 작은 문제를 각각 해결하기 => 이 때 나눈 작은 문제가 더 나눠질 수 있다면 다시 나눈다. 3) 통합: 해결한 해답을 모으기 분할정복의 응용 1) 병합 정렬(top-down 방식) - 안정 정렬 (1) 데이터 집합의 크기가 0 또는 1인지 확인 => true면 정렬 (2) 데이터 집합을 반으로 분할 (3) 나눈 집합을 하나의 집합으로 병합 (4) 최소 크기가 될 때까지 분할 (5) 조각난 데이터 집합을 정렬하며 병합(재귀 호출 이용) 시간 복잡도 공간 복잡도 O(nlogn) O(n) 2) 퀵정렬 - 불안정 정렬 (1) 데이터 집합의 크기가 0 또는 1인지 확인 => true면 정렬 (2) 데이터 집합을 반으로 ..

모든 선택에서 현재 당장 최적인 답("부분 최적해")을 선택해 최종 결과를 도출하는 알고리즘이다. 백트래킹을 하지 않고 현재 조건에서 선택을 했다면 더 이상 다른 선택 가능한 경우는 검증하지 않는다. 그리디 알고리즘의 한계는 각 단계에서는 최적이었을 수 있으나 결과론적으로 전체의 최적이 되지 않을 수 있다는 것! 그럼에도 그리디 알고리즘을 사용하는 이유는 속도가 빠르기 때문이며 어느 정도 최적 해에 근사한 값을 구할 수 있기 때문이다. 그리디 알고리즘을 사용해서 답을 도출할 수 있으려면 탐욕 선택 속성(이전의 선택이 이후에 영향을 주지 않음)과 최적 부분 구조(부분 문제의 최적 결과가 전체에도 그대로 적용)를 충족해야 한다. 1) 거스름돈 문제(동전 개수 최소 구하기; 단, 각각의 거스름 돈의 서로의 배..

자료구조 트리에 대한 개념 트리는 그래프의 한 종류이며 비선형 자료구조로 계층적 관계를 표현한다. - DAG(Directed Acyclic Graph; 방향성이 있는 비순환 그래프)의 한 종류이다. 트리는 하나의 루트 노드를 가지며 루트 노드는 0개 이상의 자식 노드를 가지고 있다(즉, 루트 노드만 있어도 트리) 트리는 노드와 노드를 연결하는 간선으로 구성되어 있으며 트리에는 사이클이 존재하지 않는다. 노드: 트리를 구성하는 기본 요소 (노드의 구성요소: key, value, 하위 노드에 대한 포인터) 간선(링크, 엣지, 브랜치): 노드와 노드를 잇는 연결 간선의 수는 노드의 수 - 1이다. 루트 노드: 트리 내에서 단 한 개 존재, 부모 노드가 없는 노드 리프(말단, 외) 노드: 자식 노드가 없는 노드..

자료의 논리적인 순서와 메모리 상의 물리적인 순서가 일치하지 않음 자료 크기를 동적으로 조정 가능함에 따라 메모리를 효율적으로 사용할 수 있음 개별적으로 위치하는 각 원소를 노드의 링크 필드로 연결한다. 연결리스트는 헤드와 노드로 구성되어 있으며 Head는 Link만 존재하며 첫 노드에 대한 참조값을 가지고 있다. Node는 원소값을 가지는 DATA 필드와 다음 노의 참조값을 가지는 LINK 필드로 이루어져 있다. 만약 노드의 링크 필드가 null이라면 해당 연결리스트의 마지막 원소라고 볼 수 있다. 노드를 중간에 삽입할 경우 유의할 사항 A와 C로 이루어진 연결 리스트 중간에 새로운 노드 B를 추가할 때, A 링크 필드에는 B의 주소값이 들어가고 B의 링크에는 C의 주소값을 넣어줘야 하는데 후자를 먼저..

Stack(스택) 선형의 자료구조로서 후입선출(LIFO)의 특징을 가진다. 자료의 삽입: push / 자료의 삭제: pop / 가장 상단의 값: top / 가장 상단 값 반환: peek / 스택의 크기: size Stack stk = new Stack(); 라이브러리가 존재하여 다른 자료구조로 구현할 필요가 없음 Queue(큐) 선형의 자료구조로서 선입선출(FIFO)의 특징을 가진다. 중간에 원소삽입이 불가하며 뒤쪽으로 순서대로 자료를 삽입할 수 있다. LinkedList로 구현한다. 자료의 삽입: offer / 자료의 삭제: poll / 제일 마지막 값 반환: peek / 스택의 크기: size ** 큐의 매서드 add, remove, element는 예외를 발생시킴 offer, poll, peek은 ..

멱집합(PowerSet)의 수 = 2^n 아래는 부분집합을 구하는 알고리즘 문제이다. 1) 부분집합 * 순열(중복 순열 아님) import java.util.Arrays; import java.util.Scanner; public class Main { static int n, m; static int[] arr, selected; static boolean[] used; static StringBuilder sb; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); arr = new int[n + 1]; selected = new int[m + 1]; ..

순서 X 중복 X 서로 다른 n개의 원소 중 r개의 순서없이 골라낸 것 import java.util.Scanner; public class Main { static int n, m; static int[] arr; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); arr = new int[m + 1]; rec(1); sc.close(); } private static void rec(int idx) { // 기저조건 if (idx == m + 1) { for (int a = 1; a < arr.length; a++) { System.out.print(..

순서 O 중복 X 서로 다른 것들 중 몇 개를 뽑아서 나열하는 것 import java.util.Scanner; public class Main { static int n, m; static int[] selected; static boolean[] used; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); selected = new int[m + 1]; used = new boolean[n + 1]; rec(1); sc.close(); } private static void rec(int idx) { // 기저조건 if (idx == m + 1) {..

완전 검색이란 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법으로서 상대적으로 빠른 시간 내에 알고리즘 설계가 가능하다. 경우의 수가 적을 때 유용하며, 모든 경우의 수를 생성한 후 테스트하기 때문에 수행속도는 느리지만 해답을 찾지 못할 가능성이 현저히 낮다. ** 완전 검색을 이용한 Baby-gin 1) 6개의 숫자로 만들 수 있는 모든 경우의 수를 나열한다 => 중복을 포함한 순열 2) 앞 3개의 숫자, 뒤 3개의 숫자를 구분하여 run(연속된 수) 또는 triplet(동일한 수) 여부를 판단한다. 완전 검색은 전형적으로 순열, 조합, 부분집합과 같은 조합적 문제와 연관되어 있다. ** 검색 기법 https://rileylee.tistory.com/5 검색 검색이란 저장된 ..