초코레

어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적이라고 한다. 재귀는 병합 정렬과 퀵 정렬, 이진검색트리 등에 사용된다. 재귀의 사용 예로 양의 정수의 팩토리얼 (n!)을 들 수 있다. 예를 들어 10의 팩토리얼인 10!은 10 * 9!로 구할 수 있고 그 우변에서 사용되는 식 9!은 9 * 8!로 구할 수 있다. 메서드가 자신을 다시 호출하는 방식을 재귀 호출(recursive call)이라고 한다. 직접 재귀 : 자신과 같은 메서드를 내부에서 다시 호출하는 것 간접 재귀 : 다른 메서드를 통해 자기 자신과 같은 메서드를 호출하는 것 a()에서 b() 호출 → b()에서 a() 호출 → a()에서 b() 호출 1 2 3 4 5 6 7 8 9 10 11 //팩토리얼을 재귀적으..

데이터를 일시적으로 쌓아 두기 위한 자료구조 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO, First In First Out) 큐의 예로는 은행 창구에서 차례를 기다리는 대기열이나 마트에서 계산을 기다리는 대기열이 있다. 데이터를 넣는 작업을 인큐(enqueue)라 하고, 꺼내는 작업을 디큐(dequeue)라고 한다. 데이터를 꺼내는 쪽은 프런트(front)라 하고, 넣는 쪽을 리어(rear)라고 한다. 배열로 큐를 구현할 때 디큐 시 요소를 꺼낸 후 다음 두 번째 이후의 요소를 모두 맨 앞으로 옮기는 구현 방식의 처리 복잡도는 O(n)이다. 링 버퍼(ring buffer, 배열의 처음이 끝과 연결되었다고 보는 자료구조)를 이용한다. 논리적으로 변수 프런트(front)와 리어(rear)의..

데이터를 일시적으로 저장하기 위해 사용하는 자료구조 데이터의 입력과 출력 순서는 후입선출(LIFO, Last In First Out) 스택에 데이터를 넣는 작업을 푸시(push), 꺼내는 작업을 팝(pop)이라고 한다. 푸시와 팝을 하는 위치를 꼭대기(top)라고 하고, 스택의 가장 아랫부분을 바닥(bottom)이라고 한다. JAVA 프로그램에서 메서드를 호출하고 실행할 때 프로그램 내부에서는 스택을 사용한다. (Call Stack) 메서드를 호출할 때는 푸시하고 메서드가 실행을 종료하고 호출한 원래의 메서드로 돌아갈 때는 종료할 메서드를 팝한다. 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 32 3..

오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘 이진 검색을 한 단계씩 진행할 때마다 검색 범위가 절반이 되므로 검색에 필요한 비교 횟수의 평균값은 log n 이다. 알고리즘의 복잡도는 O(log n) 이다. 복잡도의 대소 관계 : 1 < log n < n < n log n < n^2 < n^3 < n^k < 2^n JAVA는 배열에서 이진 검색을 하는 java.util.Arrays 클래스의 binarySearch 메서드로 제공한다. 모든 자료형 배열에서 이진 검색을 할 수 있도록 오버로딩되어 있다. [검색 성공] : 넘긴 값과 일치하는 요소의 인덱스를 반환한다. 일치하는 요소가 여러 개라면 무작위의 인덱스를 반환한다. [검색 실패] : 삽입 포인트를 x라고 할 때 -x - 1을 반환한다. ..

선형 검색(linear search) 또는 순차 검색(sequential search) 배열에서 원하는 값을 가진 요소를 찾을 때까지 맨 앞에서부터 순서대로 요소를 검색하는 알고리즘 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 32 33 34 35 36 //선형 검색 public class SeqSearchFor { //길이가 n인 배열 a에서 key와 같은 요소를 선형 검색하여 그 요소의 인덱스를 반환한다 private static int seqSearch(int[] a, int n, int key) { for (int i = 0; i

배열의 요소나 클래스의 필드는 초깃값으로 초기화가 되지만 메서드 안에서 선언한 지역 변수는 초깃값으로 초기화되지 않는다. 배열의 길이는 프로그램을 컴파일할 때가 아니라 실행할(runtime) 때 결정된다. 난수 생성에 사용할 수 있는 java.util.Random 클래스와 java.lang.Math 클래스 배열 안의 두 요소를 교환하는 것은 자주 사용하므로 독립적인 메서드로 구현하자. 소수 구하기 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 public class PrimeNumber2 { //소수 구하기 public static void main(String[] args) { int counter ..

키보드로 숫자와 문자열 입력하기 1 2 3 4 5 6 7 8 9 import java.util.Scanner; public class A { public static void main(String[] args) { //System.in은 키보드와 연결된 표준 입력 스트림(standard input stream) Scanner scanner = new Scanner(System.in); int i = scanner.nextInt(); } Colored by Color Scripter cs 메서드 자료형 nextBoolean() boolean nextByte() byte nextShort() short nextInt() int nextLong() long nextFloat() float nextDouble(..

선택 정렬보다 훨씬 빠른 정렬 알고리즘 분할 정복 전략 기본단계 : 원소의 개수가 0이거나 1 기준원소 : 배열에서 원소하나를 고른다. 분할 : 모든 원소를 기준원소보다 작은 숫자로 이루어진 배열, 기준원소보다 큰 숫자들로 이루어진 배열로 나눈다. 두 개의 하위 배열에 대해 재귀적으로 퀵 정렬을 호출하고 그 결과를 합치면 전체 배열이 정렬된다. def quicksort(array): if len(array) < 2: return array # 기본단계 else: pivot = array[0] # 기준원소 # 분할 less = [i for i in array[1:] if i pivot] return quicksort(less) + [pivot] + quicksort(greater) def main(): p..

함수가 자기 자신을 호출하는 것 재귀 함수는 기본 단계와 재귀 단계로 나누어져 있다. 기본 단계 : 무한 반복으로 빠져들지 않게 하는 부분 재귀 단계 : 자기 자신을 호출하는 부분 상자 안에서 열쇠를 찾는 코드를 의사코드로 나타내기 ※ 의사코드 : 문제와 풀이 방법을 간단한 코드 형태로 설명한 것 while 반복문을 사용한 경우 def look_for_key(main_box): pile = main_box.make_a_pile_to_look_through() while pile is not empty: box = pile.grab_a_box() for item in box: if item.is_a_box(): pile.append(item) elif item.is_a_key(): print "열쇠를 찾았..

O(n) 실행시간이 걸리는 연산을 n번 수행하는 것 주어진 리스트 중에 최소값을 찾아 맨 앞에 위치한 값과 교체하고 맨 앞의 값을 제외한 나머지를 같은 방법으로 교체하여 최종적으로 리스트를 정렬시킨다 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있다 # 배열에서 가장 작은 원소 값의 인덱스를 찾는다 def findSmallest(arr): smallest = arr[0] # 가장 작은 값 smallest_index = 0 # 가장 작은 값의 인덱스 for i in range(1, len(arr)): if arr[i] < smallest: smallest = arr[i] smallest_index = i return smallest_index # 배열을 정렬한다 def selectionSort(arr..