안드로이드 개발자 이직 공부 #02
알고리즘[Android]
2. 이직 공부
- 알고리즘
어떠한 문제를 해결하기 위한 여러 동작들의 모임이다.
유한성을 가지며, 언젠가는 끝나야 하는 속성을 가지고 있다.
면접에서 제일 어려워하는 손 코딩이 주로 알고리즘 문제들이죠.
실상 개발할 때는 API들을 이용하거나 오픈소스들을 활용하기 때문에 접할 일이 드물어요.
하지만 물어보니... 공부해야죠..ㅠ
1부터 10까지의 합을 구하는 코드를 작성해 보세요.
이 질문을 받으면 머릿속이 복잡해져요.
이 쉬운걸 왜 물어보지?
그냥 for문으로 구하면 안 될 거 같은데..
숨은 의도가 뭐지?
public int getSum(int [] N) {
int sum = 0;
int n = N.length;
for (int i = 0; i < n; i++) {
sum += N [i];
}
return sum;
}
작성하신 코드의 시간 복잡도는 어떻게 되나요?
for loop를 배열 N의 자료의 수 n번만큼 수행하기 때문에
시간 복잡도는 O(n)입니다.
좀 더 개선시킬 수는 없나요?
public int getSum(int [] N) {
int lastNum = N(N.length);
int sum = (lastNum * (lastNum + 1)) / 2;
return sum;
}
간단한 공식을 이용했기 때문에 알고리즘이라 하기 애매하지만 어쨌든 O(n)의 시간 복잡도를 O(1)로 대폭 단축시켰어요.
알고리즘은 단순히 문제 해결뿐만 아니라 시간이나 공간적인 측면에서도 더 효율적인 해결 방법을 찾아내야 하기 때문에, 기본기가 부족하거나 단순히 구글링으로 문제를 해결하시던 분들에겐 많이 버거 울 거예요.
(저도 버겁네요ㅠ)
알고리즘에 대해 알아봅시다.
알고리즘은 다음의 조건을 만족해야 한다.
입력 : 외부에서 제공되는 자료가 0개 이상 존재한다.
출력 : 적어도 2개 이상의 서로 다른 결과를 내어야 한다.(즉 모든 입력에 하나의 출력이 나오면 안 됨)
명확성 : 수행 과정은 명확하고 모호하지 않은 명령어로 구성되어야 한다.
유한성(종결 성) : 유한 번의 명령어를 수행 후(유한 시간 내)에 종료한다.
효율성 : 모든 과정은 명백하게 실행 가능(검증 가능) 한 것이어야 한다.
Android 코딩을 하다 보면 예상치 못한 상황이나 잘못된 코드로 인해 Exception이나 Error가 발생하거나,
의도하지 않은 엉뚱한 결과들이 도출되는데 알고리즘도 마찬가지예요.
문제를 해결하는 데 있어서 기본 조건이니 개념을 확실히 이해하고 알고리즘을 작성합시다.
기본 조건을 들 모두 만족시키면 원하는 결과값을 얻지만 끝이 아니네요.
얼마나 효율적으로 결과값을 얻는지 판단하는 두 가지 기준이 있습니다.
시간 복잡도(time complexity)
실제 시간을 측정하기엔 개발 환경에 따라 차이가 날 수 있기 때문에 입력 자료 크기 N에 비례한 수행 시간을 통해 구합니다.
- O(1) : 입력 자료의 수에 관계없이 일정한 실행 시간을 갖는 알고리즘
- O(log N) : 입력 자료의 크기가 N일 경우 log2N 번만큼의 수행 시간을 가진다.
- O(N) : 입력 자료의 크기가 N일 경우 N 번만큼의 수행 시간을 가진다.
- O(N log N) : 입력 자료의 크기가 N일 경우 N*(log2N) 번만큼의 수행 시간을 가진다.
- O(N2) : 입력 자료의 크기가 N일 경우 N2번만큼의 수행 시간을 가진다.
- O(2n) : 입력 자료의 크기가 N일 경우 2N 번만큼의 수행 시간을 가진다.
- O(n!) : 입력 자료의 크기가 N일 경우 n*(n-1)*(n-2)... * 1(n!) 번만큼의 수행 시간을 가진다.
공간 복잡도(space complexity)
메모리 공간 복잡도인데 알고리즘을 수행함에 있어 별도의 공간이 필요한 경우가 있습니다. (ex MergeSort)
보통은 공간 복잡도까지 안 물어보는데 Dynamic programming(동적 계획법)의 경우 고려해야 하니 개념은 알아둡시다.
알고리즘 문제들을 정말 많지만 저는 일단 정렬 알고리즘과 탐색 알고리즘에 대해서만 글을 쓸려고요.
1. 정렬 알고리즘(버블, 선택, 삽입)
package java.util;
...
public class Arrays {
...
/**
* Sorts the specified array in ascending numerical order.
*
* @param array
* the {@code int} array to be sorted.
*/
public static void sort(int[] array) {
DualPivotQuicksort.sort(array);
}
Java에서는 Arrays.sort() API를 통해 한 줄로 정렬할 수 있네요.
그런데 왜 내가 직접 짜야하지...ㅠ
버블(Bubble), 선택(Selection), 삽입(Insertion) 정렬은 O(n2)의 시간 복잡도를 가지는 정렬 알고리즘입니다.
구현하기 제일 쉽지만 시간 복잡도 측면에서는 안 좋죠.
정렬 알고리즘 작성하라고 할 때 이 3가지는 하지 맙시다.
버블 정렬(Bubble sort) : 서로 이웃한 원소들을 비교하며 정렬하는 방식.
* 최악, 최선, 평균이 항상 O(N2)
(브런치는 코드 쓰기엔 안 좋네요...)
BubbleSort(A[], n) {
// A[0...n]
for last = n down 2 {
// last가 2가 될 때까지 for loop n-1번 반복
for i = 1 to (last - 1) {
// for loop는 n-1, n-2, n-3 ... 2, 1
if(A[i] > A[i+1]) then swap A[i] and A[i+1];
}
}
}
// T(n) = (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2 = O(n2)
선택 정렬(Selection sort) : 정렬되지 않은 원소들에 대해 가장 큰 원소를 찾아 가장 뒤의 원소와 교환해나가는 방식.
* 최악, 최선, 평균이 항상 O(N2)
SelectionSort(A[], n) {
// A[0...n]
for last = n down 2 {
// last가 2가 될 때까지 for loop n-1번 반복
A[1...last] 중 가장 큰 수 A[k]를 찾는다.;
// 가장 큰 수를 찾기 위해 비교 횟수 : n-1, n-2...1
swap A[k] and A[last];
}
}
// T(n) = (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2 = O(n2)
삽입 정렬(Insertion sort) : 아직 정렬되지 않은 임의의 원소를 이미 정렬된 부분의 적절한 위치에 삽입해 가며 정렬하는 방식
* 최선 : 이미 정렬된 경우 O(N)
* 평균 : O(N2)
InsertionSort(A[], n) {
// A[0...n]
for i = 2 to n {
// for loop n-1번 반복
A[1...i]의 적당한 자리에 A[i]를 삽입한다.
// 최악의 경우 i-1번 비교, 최선의 경우 1번 비교
}
}
// T(n) = (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2 = O(n2)
권오흠 교수님의 강의가 많은 도움이 되었네요.
2. 정렬 알고리즘(합병, 퀵, 힙)
난해한 것들 나왔습니다ㅠ
합병 정렬(Merge sort) : 분할 정복법을 사용하는 정렬 알고리즘.
- 분할 : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할.
- 정복 : 각각의 작은 문제를 순환적으로 해결.
- 합병 : 작은 문제의 해를 합하여 원래 문제에 대한 해를 구함.
* 최악, 최선, 평균이 항상 O(Nlog2N)
MergeSort(A[], p, r) {
// A[p...r]
if(p < r) {
// 반대일 경우는 item이 1개인 경우 (정렬 X)
q = (p+r) / 2;
// p와 r의 중간지점
MergeSort(A, p, q);
// 전반부 분할
MergeSort(A, q+1, r);
// 후반부 분할
Merge(A, p, q, r);
// 합병
}
}
Merge(A[], p, q, r) {
정렬되어 있는 두 배열 A[p...q] 와 A[q+1...r]을 합하여 정렬된 하나의 배열 A[p...r]을 만든다.
}
수도 코드로 작성하니 간단하네요.
결국 item이 1개가 될 때까지 분할하고 정복하며 합병하는 말은 참 쉬운 개념입니다.
아래 권오흠 교수님의 강의를 여러 번 듣다 보면 이해가 가실 거예요.
T(n) = T([n/2]) + T([n/2]) + n
- T([n/2]) : 전반부 분할
- T([n/2]) : 후반부 분할
- n : 합병
T(n) = 2T(n/2) + n = O(nlog2n)
결국 시간 복잡도는 O(nlog2 n)입니다.
최악, 최선, 평균이 항상 같네요.
MergeSort는 다른 두개의 정렬과 다르게 별도의 메모리 공간이 필요해요.
공간 복잡도 측면에서는 좋은 편이 아니네요.
https://www.youtube.com/watch?v=2YvFRAC8UTM
퀵 정렬(Quick sort) : 분할 정복법을 사용하는 정렬 알고리즘.
- 분할 : 하나의 item을 pivot으로 설정해 pivot보다 작으면 앞으로, 크면 뒤로 오도록 분할.
- 정복 : 각 부분을 재귀적으로 반복해 정렬.
- 합병 : -
* 최악 : 정렬된 경우 / 처음 item을 pivot으로 설정한 경우 O(N2)
* 최악 : 반대로 정렬된 경우 / 마지막 item을 pivot으로 설정한 경우 O(N2)
* 평균 : O(Nlog2N)
QuickSort(A[], p, r) {
// A[p...r]
if(p < r) {
// 반대일 경우는 item이 1개인 경우 (정렬 X)
q = Partition(A, p, r);
// 분할
QuickSort(A, p, q);
// 전반부 정렬
QuickSort(A, q+1, r);
// 후반부 정렬
}
}
Partition(A[], p, r) {
A[p...r]의 원소들을 A[r]을 기준으로 양쪽으로 재배치하고
A[r]이 자리한 위치를 return 한다.
// pivot
}
수도 코드로 작성하니 quick sort도 간단하지만 전 merge sort을 선호합니다.
pivot위치에 따라 시간 복잡도가 달라지네요.
Java에서는 DualPivotQuicksort를 통해 정렬하는데 quick sort도 종류가 여러 개인가 봐요.
퀵 소트도 아래 권오흠 교수님의 강의를 여러 번 들어봅시다.
https://www.youtube.com/watch?v=hq4dpyuX4Uw
힙 정렬(Heap sort) : 힙 트리를 이용한 정렬 알고리즘.
Heap은 완전 이진트리이면서 Heap property를 만족하는 트리입니다.
1. 주어진 데이터를 Heap으로 만듦
2. Heap에서 최댓값(Root)을 가장 마지막 값과 바꿈
3. Heap의 크기가 1 줄어든 것으로 간주
4. Root 노드에 대해서 HEAPIFY 한다.
5. 2~4번 반복
- 완전 이진트리(complete binary tree) : 마지막 레벨을 제외하면 완전히 꽉 차있고 마지막 레벨에서 가장 오른쪽에서부터 연속된 몇 개의 노드가 비어있을 수 있음.
- Heap property : 부모는 자식보다 크거나 같다(MAX). 부모는 자식보다 작거나 같다(MIN).
- HEAPIFY : Heap property 만족하게 하기.
* 최악, 최선, 평균이 항상 O(Nlog2N)
Heap sort는... 직접 짜려고 하니...
뭐가 뭔지 모르겠네요.
네 모르겠어요.
손 코딩시키면 포기합시다.....
https://www.youtube.com/watch?v=ihyg2OR8IR0
3. 정렬 알고리즘(기타)
이 외에도 시간 복잡도가 O(n)인 기수 정렬이나 카운팅 정렬이 있어요.
약간의 제약사항이 있지만 성능면에선 좋네요.
물어본 적은 없었지만 관심 있으시면 한 번 찾아보세요.
4. 탐색 알고리즘(순차, 이진)
배열에서 특정 값을 찾는 코드를 작성해 보세요.
탐색 알고리즘은 크게 순차 탐색, 이진 탐색으로 나눌 수 있죠.
만약 배열이 정렬되어 있지 않다면 흔히 아는 for loop를 이용해 순차 탐색을 해야 해요.
이 경우엔 최악의 경우 O(n)의 시간 복잡도를 가지네요.
public int searchValue(int [] N, int value) {
int n = N.length;
for (int i = 0; i < n; i++) {
if (N[i] == value) {
return value;
}
}
return -1;
}
하지만 정렬되어 있는 경우엔 이진 탐색을 합니다.
이 경우엔 최악의 경우 O(log2n)의 시간 복잡도를 가지네요.
public int search(int[] arr, int target) {
int first = 0;
int last = arr.length;
int mid;
while (first <= last) {
mid = (first + last) / 2;
if (target == arr[mid]) {
return mid;
} else {
if (target < arr[mid]) last = mid - 1;
else first = mid + 1;
}
}
return -1;
}
https://www.youtube.com/watch?v=4RmfHRZasoY
알고리즘은 공부해보니 요령이 없어요.
이해할 때까지 공부하고 직접 손 코딩해서 익숙해져야죠.
