1. 분할 정복법 분할 정복법은 거의 대부분 재귀호출을 이용하여 해결하는 경우가 많다. 문제를 소문제로 분할 (합병 정렬, 퀵 정렬) 각각의 소문제를 해결 소문제의 해결 결과를 이용하여 전체 문제를 해결 2. 연속 부분 최대합 연속된 부분을 선택하여 그 합이 최대가 되게 하는 방법 (단, n은 1이상 100000이하) 2 1 -2 5 -10 3 2 5 -3 7 9 -10 문제 이해) 완전 탐색법으로 가능한 모든 경우의 수를 고려, 전체 시간은 O(n^3) 걸리기에 완전 탐색법은 불가능 분할 정복법으로 접근 알고리즘 개발) 우선 절반으로 나누어 각 소문제의 최대합을 찾아서 문제를 해결한다. [소문제 1] 최대합은 6 2 1 -2 5 -10 3 [소문제 2] 최대합은 20 2 5 -3 7 9 -10 [자른 ..

1. 문제 해결 절차 문제 이해 문제를 해결하는 알고리즘 개발 알고리즘이 문제를 해결함을 증명 알고리즘이 제한시간(시간복잡도) 내에 동작함을 확인 알고리즘을 코드로 작성 한번에 통과 2. 연속 부분 최대합 연속된 부분을 선택하여 그 합이 최대가 되게 하는 방법 1 2 -4 5 3 -2 9 10 문제 이해) 문제 해결을 위해 고려해야 하는 모든 경우를 파악 (탐색 공간) 연속된 구간이 1개씩, 2개씩 3개씩 ... 7개씩 전부 28개의 경우가 된다. n개가 있을 경우, n(n+1)/2 O(n^2) 알고리즘 개발) 가능한 모든 경우를 다 해보고 그 중 최대가 되는 것을 선택 start와 end로 구간 지정 코드 레벨로 구현 for(int start = 0; start < n; start++) -- O(n) ..

1. 자료구조 1) 자료구조 자료를 저장하기 위한 구조이다. 목적에 맞는 구조를 디자인하는 것이 가장 중요하다. 변수도 자료구조이다. 배열은 특정 위치의 원소를 바로 알 수 있지만 원소의 추가 및 삭제가 불편하다는 점이 있다. Linked List는 원소의 삽입과 삭제가 빠르지만 특정 위치의 원소를 알기 쉽지 않다. 2) 캡슐화, 구조체 자료구조를 사용하는 사람은 자료구조가 어떻게 동작하는지 알 필요가 없고 알아서도 안된다. 즉, 내부가 감쳐져있다. 반면 구조체는 캡슐화를 구현하기 위한 문법으로 실체가 보이지 않는다. 하나의 값을 가지는 타입을 정의를 하며, Java에서는 클래스를 이용한다. 2. 기초 자료구조 1) 스택 (LIFO) 선형 자료로 Last In First Out, 가장 최근에 삽입한 원소..

1. 이진 탐색 1) 이진 탐색이란 ? 일반적으로 n개의 숫자 중 특정 숫자를 찾을 경우 모든 원소를 확인하기 때문에 시간 복잡도는 O(n)이 된다. 이진 탐색은 정렬되어 있는 숫자들 중에서 특정 숫자를 찾는 방법이기에 O(n)의 시간복잡도보다 더 빠르다. 정렬되어 있는 수 중 중간 값을 찾음 중간 값이 찾고자 하는 값보다 클 경우 오른쪽, 작을 경우 왼쪽 과정 반복 2) 시간 복잡도 이진 탐색은 숫자를 절반씩 지워나가면서 찾기 때문에 n을 몇번을 2로 나누어야 1이 되는지가 시간복잡도이다. 즉, O(log n)이다. 하지만 결국 정렬을 해야하기 때문에 O(n logn)이다. 그럼에도 효율적으로 사용되는 상황은 다음과 같다. 이미 배열이 정렬되어 있을 경우 숫자 찾기가 많을 경우 3) 이진 탐색 재귀 디..

1. 기본 정렬 선택 정렬 삽입 정렬 버블 정렬 모두 시간 복잡도는 O(n^2)이다. 2. 고급 정렬 시간 복잡도를 O(n logn)으로 정렬하는 방법은 다음과 같다. 합병 정렬 퀵 정렬 힙 정렬 합병과 퀵 정렬은 재귀호출 혹은 재귀적인 구조를 이용한 정렬이다. 로그는 지수함수의 역함수이다. 컴퓨터 공학에서 log를 사용하는 경우 그 밑이 2이므로 보통 밑을 생략한다. 3. 합병 정렬 1) 합병 정렬이란 ? 매번 배열을 절반으로 나누고 각각 정렬한 뒤 합치는 방법이다. T(n)은 n개의 숫자를 합병정렬 할 때의 시간 복잡도로 O(n logn)과 동일하다. 2) 시간 복잡도 T(n)은 n개의 숫자를 합병 정렬로 정렬하는데 걸리는 시간이다. 왼쪽 합병 정렬은 T(n/2)의 시간복잡도 오른쪽 합병 정렬은 T(..

1. 재귀함수 일반적으로 두 가지 계산 방법이 존재한다. 순차적 계산 방법 귀납적 계산 방법 순차적 계산 방법은 차례차례로 계산 하는 것으로 가장 기본적인 방법이다. 반면 귀납적 계산은 "나"를 계산하기 위해 또 다시 "나"를 활용하는 방법이다. 귀납적 방법은 수많은 가정을 하다 가장 마지막에는 정해진 규칙에 의해 정확한 값을 통해 성립하는 것을 확인한다. 5^4 = 5^3 x 5 // 5^3은 5를 세번 곱한다는 가정 5^3 = 5^2 x 5 // 5^2은 5를 두번 곱한다는 가정 5^2 = 5^1 x 5 // 5^1은 5를 한번 곱한다는 가정 5^1 = 5^0 x 5 // 5^0은 1이라는 규칙이 있기에 모든 과정이 성립 즉, 재귀함수는 자기 자신을 호출하여 계산하는 방식이다. 재귀함수 디자인은 3가..