일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- MySQL
- 백트래킹
- 이분탐색
- 그래프
- Sort
- 알고리즘
- 자료구조
- 프로그래머스
- algorithm
- 자바
- 반효경교수님
- 해시맵
- SQL
- Recursion
- 정렬
- Mendix
- 멘딕스
- git
- 집합
- 가중치없는그래프
- 완전탐색
- dfs
- 재귀
- Bruteforce
- 매개변수 탐색
- domain model
- lcap
- 스택
- microflow
- 트리
- Today
- Total
목록알고리즘 (89)
mondegreen
모든 선택에서 현재 당장 최적인 답("부분 최적해")을 선택해 최종 결과를 도출하는 알고리즘이다. 백트래킹을 하지 않고 현재 조건에서 선택을 했다면 더 이상 다른 선택 가능한 경우는 검증하지 않는다. 그리디 알고리즘의 한계는 각 단계에서는 최적이었을 수 있으나 결과론적으로 전체의 최적이 되지 않을 수 있다는 것! 그럼에도 그리디 알고리즘을 사용하는 이유는 속도가 빠르기 때문이며 어느 정도 최적 해에 근사한 값을 구할 수 있기 때문이다. 그리디 알고리즘을 사용해서 답을 도출할 수 있으려면 탐욕 선택 속성(이전의 선택이 이후에 영향을 주지 않음)과 최적 부분 구조(부분 문제의 최적 결과가 전체에도 그대로 적용)를 충족해야 한다. 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 검색 검색이란 저장된 ..
재귀는 주어진 문제의 해를 구하기 위해 동일하면서 더 작은 문제의 해를 이용한다. 하나의 큰 문제를 해결하기 위해 다소 해결하기 쉬운 작은 문제의 결과를 조합한다. 재귀함수(Recursive Function)함수 내부에서 자기 자신을 호출하는 함수로서기저 부분(basis part)와 유도부분(inductive part)으로 이루어져 있다. 함수 호출은 프로그램의 메모리 구조 중 스택을 사용한다. 반복적으로 스택을 사용하기 때문에 메모리 및 속도에서 성능 저하가 발생한다. 함수 호출 시 기저 부분이 작동하지 않으면 자기 자신을 무한 호출하여 stackoveflow 발생 // n!에 대한 재귀함수int fact(int n){ if(n** 반복과의 비교n이 커질수록 재귀가 반복보다 메모리와 연산속도 효..