When they go low, We go high

합병정렬- 여러 개의 정렬된 자료의 집합을 결합하여 한 개의 정렬된 집합으로 만드는 방법- 분할 정복(Divide and Conquer)방식으로 설계된 알고리즘- 문제를 반으로 쪼개 문제를 해결해 나가는 방식 , 분할은 배열의 크기가 1보다 작거나 같을 때 까지 반복한다- 시간복잡도 : O(nlogn) 정렬 방법분할- 현재 배열을 반으로 쪼갠다- 배열 시작 위치와 종료위치를 입력받아 둘을 더한 후 2를 나눠 그 위치를 기준으로 나눈다- 쪼갠 배열의 크기가 0이거나 1 일때 까지 반복한다 합병- 두 배열 A,B의 크기를 비교한다- 두 배열의 시작 인덱스를 저장한다- 두 배열의 맨 앞의 값을 비교하여 이 중 작은 값(오름 차순일 경우)을 새 배열에 저장하고 작은값을 추출한 배열의 인덱스를 증가시켜 준다- 이..

버블정렬 - 인접한 두 수를 비교해서 큰 수를 뒤로 보내는 방식- 시간 복잡도 : O(n^2)- 코드가 단순해 자주 사용된다- n개의 원소에 대하여 n개의메모리 사용- 최선의 경우 : 자료가 이미 정렬되어 있는 경우 , 최선의 경우에도 계속해서 반복하지 않도록 정렬되어 있는 경우 다음 패스를 수행하지 않도록 수정할 수 있다- 최악의 경우 : 자료가 역순으로 정렬되어 있는 경우 정렬 방법- 배열의 첫번째 값과 두번째 값의 크기를 비교한다- 더 큰 값을 뒤로 보낸다- 비교하는 배열의 위치를 하나씩 증가하며 위 항목을 반복한다- 배열의 끝까지 비교 했다면 처음 부터 위 작업을 반복하되 비교했던 요소중 제일 마지막 값은 제외 한다 ex) 사진 예시 ex 2ex 1 Java로 구현한 버블정렬

선택정렬- 기준 위치에 맞는 원소를 선택해 자리교환 하는 방식- 시간 복잡도 : O(n^2)- 어떤 상태여도 비교횟수가 같으므로 최악이나 최선이나 시간 복잡도가 같다(물론 평균도 같겠죠)- 데이터 양이 적을 때 좋은 성능을 나타냄- 작은 값을 선택하기 위해서 비교는 여러번 수행되지만 교환 횟수가 적다- 데이터 양이 많을 때 급격히 속도가 떨어진다 정렬 방법- 주어진 데이터(정렬되지 않은 데이터들) 중 최소값을 찾음- 선택된 최소값과 맨앞에 있는 값을 교환(선택된 최소값을 맨앞으로 보냄)- 정렬된 데이터를 제외한 나머지 데이터를 같은 방법으로 정렬 ex) 사진 예시 ex 1 ex 2 Java로 구현한 선택정렬

시간복잡도(Time Complexity)- 프로그램을 실행시켜 완료하는데 걸리는 시간- 어떤 프로그램의 실행시간을 추정하기 위해서는 모든 기본 명령문의 실행 빈도수(frequency count)를 알아야한다 여기서 기본 명령문은 지정문,조건문,반복문 속의 제어문 그리고 stop, return등을 포함한다- 추정을 목적으로 하기 때문에 프로그램 문맥상 하나의 연산 단위를 하나의 단계로 계산하면 의도한 목적 달성에 충분하다- 시간 복잡도의 계산은 정밀하지 않다 예를 들어 N+100의 제곱은 N^2+200N+10000이 되고 N^2으로 간단히 표현한다 Big O 표기법- 빅오 표기법(Big - O Notation)- 알고리즘의 복잡도 또는 성능을 표현하기 위해 사용된다- 최악의 상황을 고려한 시간 복잡도를 표..

자료구조(Data Structure) 자료(Data)현실 세계로부터 수집한 사실이나 개념의 값 또는 이들의 집합을 의미한다흔히 가공되지 않은 형태의 데이터를 자료라고 하며 특정한 용도로 사용하기 위하여 자료를 처리/가공한 형태의 데이터를 정보(Information) 이라고 한다 자료구조(Data Structure)자료의 집합을 의미각 원소들 사이의 관계가 논리적으로 정의된 일정한 규칙에 의하여 나열되며 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 조직적, 체계적으로 구분하여 표현한 것을 말한다 자료구조의 선택기준작업의 효율성, 추상화, 재사용성을 증가시키기 위하여 상황에 따른 자료구조를 선택하여 사용해야 한다자료의 처리를 더 효율적으로 하기 위하여 아래의 사항을 고려해야한다- 자료의 처리시간-..