정의 - 그래프는 실제 세계의 현상이나 사물을 정점(Vertex) 또는 노드(Node) 와 간선(Edge)로 표현하기 위해 사용 - 예) 집에서 회사로 가는 경로를 그래프로 표현할 때 용어 - 노드(Node) : 위치를 말함, 정점(Vertex) 라고 함 - 간선(Edge) : 위치 간의 관계를 표시한 선으로 노드를 연결한 선이라고 보면 됨 (link 또는 branch) 라고도 한다 - 인접 정점(Adiacent Vertex) : 간선으로 직접 연결된 정점 (또는 노드) - 참고용어 - 정점의 차수(Degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 - 진입 차수(In Degree) : 방향 그래프에서 외부에서 오는 간선의 수 - 진출 차수(Out Degree) : 방향 그래프에서 외부로..
정의 - 데이터가 담겨있는 리스트를 앞에서부터 하나씩 비교해서 원하는 데이터를 찾는 방법 분석 - 최악의 경우 리스트 길이가 n 일 때 n 번 비교해야 한다 (찾는 값이 맨 마지막에 있을 경우) - O(n) 순차 탐색 (Sequential Search) public class SequentialSearch { public static void main(String[] args) { int[] arr = new Random().ints(10, 0, 30).toArray();; int index = sequential(arr, 10); System.out.println("arr = " + Arrays.toString(arr)); System.out.println("index = " + index); } pr..
08. 동적 계획법 (Dynamic Programing) 과 분할정복 (Divide and Conquer)
2021.09.21
동적 계획법 (Dynamic Programing, DP) - 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분문제의 해를 재활용해서 보다 큰 크기의 부분문제를 해결 최종적으로 전체 문제를 해결하는 알고리즘 - 상향식 접근법으로 가장 최하위의 해답을 구한 후 이를 저장하고, 해당 결과값을 이용해서 상위문제를 풀어나가는 방식 - Memorization (메모제이션) 이란 프로그램 실행 시 이전에 계산한 값을 저장하여 다시 계산하지 않도록 하여 전체 실행속도를 빠르게 하는 기술 - 문제를 잘게 쪼갤 때, 부분문제는 중복되는 경우 재활용 된다 - 예) 피보나치 수열 * 요약 1. 작은 문제 부터 먼저 해결하여 값을 저장한다. 2. 점차 큰 크기의 문제 부분을 해결하는 데 중복된 작은 문제는 계산하지 않고 ..
📌 배열 (Array) 정의 데이터를 나열하고, 각 데이터를 인덱스에 대응하도록 구상한 데이터 구조 배열이 왜 필요할까 ? - 같은 종류의 데이터를 효율적으로 관리하기 위해 사용 - 같은 종류의 데이터를 순차적으로 저장 (인덱스가 존재) - 문자열과 같은 경우 순차적으로 저장되어 있어야 효율적으로 관리 될 수 있다 - 인덱스를 통해서 연결된 데이터의 일부분을 바로 접근할 수 있다 장점 빠른 접근 가능 : 배열의 첫번째 위치만 알면 인덱스를 통해 몇번째 만큼 떨어진 곳으로 바로 접근 가능 단점 추가 / 삭제가 쉽지 않다 삭제하는 경우 필요없는 공간을 가지고 있어야 한다 미리 최대의 길이를 지정해야 한다 고정된 길이 가변적 `JAVA` 라는 문자열을 저장하기 위해 미리 4정도의 크기를 갖는 배열을 생성해놓아..
병합정렬 (Merge Sort) public class MergeSort { public static void main(String[] args) { int[] numArr = {4, 1, 7, 3, 2, 8, 6}; int[] results = mergeSplit(numArr); System.out.println(Arrays.toString(results)); } private static int[] mergeSplit(int[] arr) { // 길이가 1개 이하 인 경우 return arr if (arr.length lp && right.length > rp) { // 왼쪽 배열의 크기 보다 lp 가 작은 경우 and 오른쪽 배열 크기 보다 rp 가 작은 경우 if (left[lp] > right[..
정의 - 정렬 알고리즘의 꽃 - 기준점(Pivot) 을 정해서, 기준점보다 작은 데이터는 왼쪽(left) 큰 데이터는 오른쪽(right)으로 모으는 함수 - 각 왼쪽 (left), 오른쪽 (right) 는 재귀용법을 사용해서 다시 동일함수를 호출하여 위 작업을 반복한다 - 함수는 왼쪽 (left) + 기준점 (pivot) + 오른쪽 (right) 을 리턴한다 - 왼쪽 퀵 정렬 일 때 0번째가 가장 작은 수 일 경우 최악의 성능이 나옴 (빠르긴 하나, 상황에 따라 성능이 차이가 날 수 있기 때문에 안정적이지 않은 편이다. 그 에 비해 같은 분할정복의 정렬 중 병합 정렬은 항상 동일한 성능을 가지고 있어 안정적이고 퀵 정렬보다는 아니지만 그에 준수 한 속도를 가지고 있다) 분석 - 병합정렬 (Merge So..
재귀 함수 정수 n 이 입력으로 주어졌을 때 n을 1,2,3 의 합으로 나타낼 수 있는 방법의 수 구하기 public class RecursiveCall5 { public static void main(String[] args) { int num = 4; int numberOfCases = recursiveSum(num); System.out.println(numberOfCases); } private static int recursiveSum(int num) { if (num == 1) return 1; else if (num == 2) return 2; else if (num == 3) return 4; return recursiveSum(num - 1) + recursiveSum(num - 2) +..
재귀함수 (Recursive Call) 정수 n에 대해 n 이 홀수이면 3 * n + 1 을 하고, n 이 짝수이면 n 을 2로 나눕니다 이렇게 계속 진행해서 n 이 결국 1 이 될 때 까지 반복하고 이렇게 정수 n 을 입력받아, 위 알고리즘에 의해 1이 되는 과정을 모두 출력하는 함수를 작성하세요 public class RecursiveCall4 { public static void main(String[] args) { int num = 3; int result = EvenOddRe(num); } private static int EvenOddRe(int num) { System.out.println(num); if (num
회문 (Palindrome) 순서를 거꾸로 읽어도 같은 단어인 회문인지 판단하는 코드 작성 (재귀함수) 예) `LEVEL` 은 거꾸로 읽어도 `LEVEL` 이기 때문에 true, `MOTOR` 는 거꾸로 읽으면 `ROTMO` 이기 때문에 false public class Palindrome { public static void main(String[] args) { String name = "level"; char[] chars = name.toCharArray(); boolean isPalindrome = isPalindrome(chars); System.out.println(isPalindrome); } private static boolean isPalindrome(char[] name) { if ..
정의 재귀용법(=재귀함수) 란? - 함수 안에서 동일한 함수를 호출하는 형태 - 재귀 호출은 스택의 전형적인 예이다 - 함수는 내부적으로 스택처럼 관리된다 TIP 고급 정렬 알고리즘에서 재귀용법을 사용하므로 고급 정렬 알고리즘을 익히기 전에 재귀용법을 먼저 익히는 것이 좋다 재귀 용법의 이해 (예시 - 팩토리얼) - factorial(num) 은 서번의 factorial 함수를 호출해서 곱셈을 한다 - 일종의 num - 1 번의 반복문을 호출한 것과 동일하다 - factorial () 함수를 호출할 때 마다 지역변수 num 이 생성된다 - 시간 복잡도 O(num-1) , 공간 복잡도 O(num) 이므로 둘 다 O(n) 이다 재귀함수 (Recursive Call) public class RecursiveC..
정의 - 삽입 정렬은 두 번째 인덱스 부터 시작한다 - 해당 인덱스 (key 값) 앞에 있는 데이터 (B) 부터 비교해서 key 값이 더 작으면 B 값을 뒤 인덱스로 복사한다 - 이를 key 값이 더 큰 데이터를 만날 때 까지 반복하고, 큰 데이터를 만난 위치 바로 뒤에 Key 값을 이동 버블정렬이 조금 비효율적인 면이 있기에 비교횟수를 효율적으로 줄이기 위해서 고안된 방법이 삽입정렬입니다. 삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 정렬 방법입니다. 버블정렬은 비교대상의 메모리 값이 정렬되어 있음에도 불구하고 비교연산을 하는 부분이 있는데 삽입정렬은 기본적으로 버블정렬의 비교횟수를 줄이고 크기가 적은 데이..