이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 듣고 정리한 내용입니다. Merge Sort(병합 정렬)분할 정복법(Merge Sort, Quick Sort)분할 : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할정복 : 각각의 작은 문제를 순환적으로 해결합병 : 작은 문제의 해를 합하여(Merge) 원래 문제에 대한 해를 구함 1. 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우2. 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.3. 각 부분의 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.4. 두 부분의 리스트를 다시 하나의 정렬된 리스트로 합병한다. 의사코드 Merge Sort(A[], p, r) { // 배열 A[p...
이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 듣고 정리한 내용입니다. Bubble Sort(거품 정렬)거품 정렬은 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 로 상당히 느리지만,코드가 단순하기 때문에 자주 사용된다. 출처 : 위키 백과 예제[4, 54, 2, 8, 63, 7, 55, 56] [4, 2, 8, 54, 7, 55, 56, 63] [2, 4, 8, 7, 54, 55, 56, 63] [4, 2, 54, 8, 63, 7, 55, 56] [2, 4, 8, 54, 7, 55, 56, 63] [2, 4, 7, 8, 54, 55, 56, 63]pass3[4, 2, 8, 54, 63, 7, 55, 56] [2, 4, 8, 7, 54, 55, 56, 63]pass 2[4, 2..
이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 듣고 정리한 내용입니다. Selection Sort(선택 정렬)선택 정렬은 제자리 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.1. 주어진 리스트 중에 최솟값 or 최대값을 찾는다.2. 그 값을 맨 앞 or 맨 뒤에 위치한 값과 교체한다.3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. 비교하는 것이 상수 시간에 이루어진다는 가정 아래, n 개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는 Θ(n2) 만큼의 시간이 걸린다. 출처 : 위키 백과 예제 [4, 54, 2, 8, 63, 7, 55, 56] -> initial array [4, 54, 2, 8, 56, 7, 55, 63] -> after 1st swap [4,..
문제 2016년 1월 1일은 금요일입니다.2016년 A월 B일은 무슨 요일일까요?두 수 A,B를 입력받아 A월 B일이 무슨 요일인지 출력하는 getDayName 함수를 완성하세요.요일의 이름은 일요일부터 토요일까지 각각 SUN, MON, TUE, WED, THU, FRI, SAT 를 출력해주면 됩니다. 예를 들어 A=5, B=24가 입력된다면 5월 24일은 화요일이므로 TUE를 반환하면 됩니다. 풀이(Java) class TryHelloWorld { public String getDayName(int a, int b) { String answer = ""; String[] week = {"FRI","SAT","SUN","MON","TUE","WED","THU"}; int[] month = {31,29,3..