퀵정렬(Quick Sort) 정렬 알고리즘 중 가장 효율적이고 빠른방식 입니다. 동작방식(아이디어)은 아래와 같습니다. 1. 기준점이 되는 pivot을 구한다. 2. pivot을 기준으로 left(pviot보다 작은 값) 리스트와 right(pivot 보다 큰 값)리스트를 구합니다. 3. 나눠진 left와 right 리스트를 정렬이될 때까지 분할처리 합니다. => 재귀사용(자기자신을 호출) (설명 및 그림참고 : 네이버 지식백과(퀵정렬)) 퀵정렬은 버블 정렬이나 삽입 정렬보다 훨씬 더 효율적인 성능을 발휘합니다. 퀵정렬의 평균 시간복잡도는 O(nlogn)이며, 최악의 경우에는 여전히 O(n^2)의 시간복잡도를 갖습니다. 이 성능차이는 pivot의 선택에 따라 좌우되게 되는데, 아래코드와 같이 가장앞에 있..
프로그래밍 노트/알고리즘
#7 주어진 string 에 모든 단어를 거꾸로 하시오. 예제)Input: “abc 123 apple”Output: “cba 321 elppa” Input의 문자열을 문자단위로 나눈 후, 각 단어를 거꾸로 만들어서 새로운 문자열에 추가하면 쉽게 풀 수 있다.코딩테스트시 제공되는 편리한 API(함수) 사용이 제한이 될 수 있다하여, split와 문자열을 거꾸로 출력하는 reverse를 별도로 구현하여 만들었다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152package everyProgramming; import java.util.ArrayList; public class Ch07 ..
#6 간격(interval)로 이루어진 배열이 주어지면, 겹치는 간격 원소들을 합친 새로운 배열을 만드시오. 간격은 시작과 끝으로 이루어져 있으며 시작은 끝보다 작거나 같습니다. 예제)Input: {{2,4}, {1,5}, {7,9}}Output: {{1,5}, {7,9}} Input: {{3,6}, {1,3}, {2,4}}Output: {{1,6}} 리스트안에 리스트가 존재하여 어떻게 풀지 고민을 많이했었는데, 시작과 끝으로 구성된 클래스를 하나 구현해서 사용하니 쉽게 풀렸다.풀이법은 이렇다.1. 우선 {시작, 끝} 을 표현할 수 있는 Interval 클래스를 생성한다.2. List에 들어있는 Interval들을 {시작, 끝} 시작크기순으로 정렬한다. {{2,4}, {1,5}, {7,9}} => {{1..
#5정수 배열과 타겟 숫자가 주어지면, 합이 타겟값이 되는 두 원소의 인덱스를 찾으시오.단, 시간복잡도 O(n) 여야 합니다. 예제)Input: [2, 5, 6, 1, 10], 타겟 8Output: [0, 2] // 배열[0] + 배열[2] = 8 for문을 두번 돌려서 간단하게 풀려 하였으나, 시간복잡도가 O(n)이다. 하긴 중첩 for문 처럼 쉬운 문제는 나오지 않겠지.... 어떻게 할까 고민하다가 Map을 사용하기로 하였다.Map의 key에는 value(숫자) 값을 담고, value 에는 index 값을 담아서, value(숫자)에 해당하는 index를 추출하는 방식이다. Map(value, index)for문을 돌면서 target 값에서 해당 value(숫자)를 뺀 후, 그 값이 Map에 존재하면..
#4 정수(int)가 주어지면, 팰린드롬(palindrome)인지 알아내시오. 팰린드롬이란, 앞에서부터 읽으나 뒤에서부터 읽으나 같은 단어를 말합니다. 단, 정수를 문자열로 바꾸면 안됩니다. 예제) Input: 12345 Output: False Input: -101 Output: False Input: 11111 Output: True Input: 12421 Output: True 코딩끄적끄적 게시판에 작성했던 팰린드롬 관련 알고리즘문제가 나왔다. 이 팰린드롬문제는 전에 포스팅했던 팰린드롬문제의 심화버전인 것 같다. 전 버전은 String(문자열)으로 되었기 때문에, 관련 메소드를 사용하여 손쉽게 풀었지만, 이번 문제는 int(정수)형 이기 때문에 관련 메소드를 사용할 수가 없다. (length 길이조..
삽입정렬(Insertion Sort)삽입정렬은 아직 정렬되지 않은 임의의 데이터를 이미 정렬된 부분의 적절한 위치에 삽입해 가며 정렬하는 방식입니다.삽입정렬 또한 앞의 두 알고리즘과 같이 시간복잡도O(n^2)를 갖습니다. (for문이 2번 있기 때문입니다. )왼쪽원소부터 정렬되며 오른쪽 원소들을 왼쪽 정렬된 원소들과 비교하며 적절한 위치에 삽입합니다.123456789101112131415161718192021//삽입정렬(insertion sort) public void insertionSort(int[] array) { int size = array.length; for(int i=1; i = 0; j--) { if(array[k] temp)) { a[j] = a[j - 1]; j--; } a[j] = ..
#3정수 n이 주어지면, n개의 여는 괄호 "("와 n개의 닫는 괄호 ")"로 만들 수 있는 괄호 조합을 모두 구하시오. (시간 복잡도 제한 없습니다). 예제)Input: 1Output: ["()"] Input: 2Output: ["(())", "()()"] Input: 3Output: ["((()))", "(()())", "()(())", "(())()", "()()()"] 문제3은 재귀함수와 관련된 문제이다. 세번째 문제인데 벌써부터 슬슬 한계가 오는 것 같다. 혼자 풀어보려했지만, 도저히 풀 수 없어서 답안을 참고했다. 답안지에서는 주로 답의 양이 많거나 조합을 구하는 경우는 재귀함수를 사용하면 된다고 나와있다. '누워서 읽는 알고리즘'에서 재귀함수는 세련된 기법이라고 하였다. (저자가 재귀함수를 ..
버블정렬(Bubble Sort)버블정렬은 인접한 두개의 원소를 비교하여 가장 큰 원소가 마지막자리로 오게해서 숫자를 정렬하는 방법입니다.원소를 두개씩 교환하면서 마지막원소까지 오는 모습이 거품이 물에서 올라오는 것과 비슷하다. 라고 생각하여 버블정렬이라는 이름을 갖게되었답니다..시간복잡도는 선택정렬과 같이 O(n^2)입니다.비교횟수가 선택정렬과 똑같기 때문입니다.1단계 => n 2단계 => n-1...n + (n-1) + (n-2) + ....12345678910111213141516171819202122// 버블정렬public void bubbleSort(int[] array) { int size = array.length; for(int i=0; i O(n) 의 시간복잡도를 갖게됩니다.최악의 경우에는..
선택정렬(Selection Sort)선택정렬은 배열중에 가장 작은 원소들을 왼쪽부터 채워나가면서 숫자를 정렬하는 방법입니다.최소원소를 찾은 후 => 최소원소를 맨 왼쪽원소와 교환(즉, 왼쪽부터 정렬된 원소로 채워집니다.)=> 왼쪽원소를 제외하고 원소가 하나남을때 까지 이단계를 반복(그림 참고) 선택정렬의 비교횟수를 구해보면1단계 => n개의 원소 비교2단계 => n-1 개의 원소 비교3단계 => n-2 개의 원소 비교....를 하여 비교 횟수는n(n-1) /2 가 됩니다.즉, 시간복잡도는 O(n^2)이 됩니다. // 선택정렬 public void selectionSort(int[] array) { int size = array.length; int i, j, min; for(i = 0; i < size-..
참고 : [JAVA] 피보나치 수열 코딩 #2 피보나치 배열은 0과 1로 시작하며, 다음 피보나치 수는 바로 앞의 두 피보나치 수의 합이 된다. 정수 N이 주어지면, N보다 작은 모든 짝수 피보나치 수의 합을 구하여라. 예제) Input: N = 12 Output: 10 // 0, 1, 2, 3, 5, 8 중 짝수인 2 + 8 = 10. public static int solution(int num) { // 피보나치 수열 ( 1+1+2+3+5+8+13 ...) int last1 = 1, last2 = 1, next = 0, sum = 0; next = last1 + last2; while(next < num) { if(next % 2 == 0) { sum += next; } last1 = last2; ..
