기본적인 단계
1. 문제를 확실히 이해한다.
2. 일단 문제를 이해하고 나면 몇가지 예를 시도해 본다.
3. 문제 풀이에 사용할 알고리즘에 초점을 맞춘다.
4. 알고리즘과 구현 방법을 알아내고 나면 인터뷰어에게 풀이를 설명한다.
5. 코딩을 할 때도 뭘하고 있는지 설명한다.
6. 필요하다면 질문을 한다.
7. 코드를 완성하고 나면 몇가지 예를 시도해 보고 맞는지 확인한다.
8. 모든 오류 및 특별 케이스 , 특히 경계 조건을 확인한다.
문제를 풀다가 막히는 경우
1. 예를 다시 따져본다.
2. 다른 자료 구조를 사용해 시도해 본다.
3. 언어에스 그리 많이 쓰이지 않는 기능 또는 고급 기능을 고려해 본다.
풀이 분석
문제에 대한 답을 내혹고 구현의 효율성에 대한 질문이 나오는 경우가 많다.
ex) 지원자가 구현한 풀이 방법과 다른 풀이 방법을 제시하고 그 둘의 장단점을 비교하라고 하거나 풀이 방법과 다른 풀이 방법을 제시하고 그 둘의 장단점을 비교하라고 하거나 어떤 상황에서 어떤 구현 방법이 더 유리할지를 물어보는 경우를 많이 접하게 될 것이다.
빅 오 분석법을 제대로 이해하고 있다면 더욱 좋은 평가를 받을수 있다.
빅오 분석법은 입력 값의 개수에 따라 알고리즘이 수행되는 데 걸리는 시간을 바탕으로 알고리즘의 효율성을 평가하는 실행 시간 분석법.
두가지예의 분석시
ex) 배열에서 최대값을 구하는 함수를 구현.
첫번째 방법
배열(크기는 n)의 모든 원소를 하나씩 확인하면서 가장 큰 수를 계속 기록한 다음, 확인이 끝나고 나면 그 값을 반환하는 방법.
int CompareToMax(int array[], int n )
{
int curMax , i ;
int ( n <= 0 )
return -1;
curMax = array[0];
for( i = 0 ; i < n ; i++ )
{
if( array[i] > curMax )
{
curMax = array[i];
}
}
return curMax;
}
두번째 방법
각 값을 다른 모든 값과 비교하는 방법이다. 다른 모든 값이 주어진 값 이하라면 그 값이 최대값이 되는 구현.
int CompareToAill(int array[] , int n)
{
int i,j ;
bool isMax ;
if(n <= 0)
return -1;
for( i = n-1 ;i > 0 ; i--) {
isMax = true;
for( j = 0 ; j < n ; j++) {
if( array[j] > array[i])
isMax = false;
}
if(isMax)
break;
}
}
빅 오 분석법을 통한 분석
빅 오 분석법의 경우 입력 값의 크기를 n이라고 가정한다. 위의 예에서는 배열에 있는 원소의 개수가 바로 n이 된다. 문제에 따라 n이 연결 리스트의 노드 개수를 나타낼 수도 있고, 특정 자료형의 비트 수 일 수도 있고, 해시 테이블에 들어있는 항목의 개수일 수도 있는 등 다양한 값들이 입력 값의 크기 n으로 쓰일 수 있다.
CompareToMax 에서는 각 배열 원소와 최대값을 한 번씩 비교했다. 따라서 n개의 입력된 항목이 각각 한번씩 확인되기 때문에 총 n번의 확인 작업이 수행된다. 이런 상황을 O(n) 이라고 표현하며 "선형 시간" 내에 수행된다고 말하기도 한다.
# 빅 오 분석을 할 떄는 최 고차항 즉, n이 매우 커질 때 가장 큰 항만 남기고 다른 항은 다 무시한다.
지금 다루고 있는 예에서는 n이 최고차항이기 때문에 CompareToMax 함수는 O(n) 이 된다.
CompareToAll의 경우 약간 복잡하나 배열의 어느 위치에 가장 큰 수가 있는지를 가정해 봐야한다. 최대 원소가 배열의 맨 뒤에 있다고 가정할 경우, 이런 경우에는 n개의 원소를 n개의 다른 원소와 비교해야 한다.
따라서 O(n^2) 알고리즘이다.
최선, 평균, 최악 케이스
CompareToAll을 분석할 때 최대값이 맨 뒤에 있다고 가정했기 떄문에 불공평한 것이 아닐까 하는 생각을 해볼수 있다. 실제로도 그러하며 이런 문제 때문에 최선, 평균, 최악 케이스의 실행 시간을 따져봐야 하는 문제가 생긴다.
CompareToAll을 테스트 할 때, 최대값이 가운데 있는 경우를 생각해 보자. 최대값이 중간에 있다면 절반만 n번씩 확인해 보면 된다. 그러면 n(n/2)번만 확인하면 된다. 각 값을 실제로 확인하는데 걸리는 시간은 코드에 의해 생성되는 기계어와 CPU에서 그러한 명령들을 수행하는데 걸리는 시간에 의해 크게 좌우된다. 따라서 1/2이라는 숫자가 그런 큰 의미를 가진다고 볼 수는 없다.(?) 빅 오 분석법에서는 모든 상수 인자들을 빼버리기 때문에 CompareToAll의 평균 케이스도 최악의 케이스와 별로 다를 바가 없다.
빅 오 분석법을 적용하는 방법
일반적으로 빅 오 실행시간분석은 다음과 같은 방법으로 하면된다.
1. 입력 값이 무엇인지 확인하고 어떤 것을 n으로 놓아야 할지 결정한다.
2. 알고리즘에서 수행해야 할 연산 횟수를 n의 식으로 표현한다.
3. 차수가 제일 높은 항만 남긴다.
4. 모든 상수 인수를 없앤다.
최적화와 빅 오 분석법
알고리즘을 최적화한다고 해서 반드시 전체 실행 시간이 빨라지는 것은 아니다.
CompareToAll을 다음과 같이 최적화 한다고 생각해 보자. 각 수를 다른 모든 수와 비교하는 대신 배열에서 그 수보다 뒤에 있는 수하고만 비교한다고 해 보자. 그 수 앞에 있는 수는 전부 지금 기준이 되는 수와 비교해 본적이 있기 때문이다. 따라서 현재 비교하고자 하는 수보다 뒤에 있는 원소들하고만 비교해도 알고리즘은 정확하게 작동한다.
이렇게 하고나면 최악의 실행시간은 어떻게 될까?
이 알고리즘에서 최악 케이스의 실행 시간도 여전히 O(n^2)에 머무른다.
입력 개수가 많아지면 이런 식으로 알고리즘을 최적화 한다고 해서 실행 시간이 크게 빨라지지 않는다는 것이다.
요약
문제를 풀 때는 인터뷰어와 의사소통을 최대한 활발하게 하도록 하자.
문제를 분석하고 답을 코딩하는 각 단계에서 자신이 무슨 생각을 하고 있는지 인터뷰어에게 알릴 수 있어야 한다.
PROGRAMMING INTERVIEWS EXPOSED 발췌.!
1. 문제를 확실히 이해한다.
2. 일단 문제를 이해하고 나면 몇가지 예를 시도해 본다.
3. 문제 풀이에 사용할 알고리즘에 초점을 맞춘다.
4. 알고리즘과 구현 방법을 알아내고 나면 인터뷰어에게 풀이를 설명한다.
5. 코딩을 할 때도 뭘하고 있는지 설명한다.
6. 필요하다면 질문을 한다.
7. 코드를 완성하고 나면 몇가지 예를 시도해 보고 맞는지 확인한다.
8. 모든 오류 및 특별 케이스 , 특히 경계 조건을 확인한다.
문제를 풀다가 막히는 경우
1. 예를 다시 따져본다.
2. 다른 자료 구조를 사용해 시도해 본다.
3. 언어에스 그리 많이 쓰이지 않는 기능 또는 고급 기능을 고려해 본다.
풀이 분석
문제에 대한 답을 내혹고 구현의 효율성에 대한 질문이 나오는 경우가 많다.
ex) 지원자가 구현한 풀이 방법과 다른 풀이 방법을 제시하고 그 둘의 장단점을 비교하라고 하거나 풀이 방법과 다른 풀이 방법을 제시하고 그 둘의 장단점을 비교하라고 하거나 어떤 상황에서 어떤 구현 방법이 더 유리할지를 물어보는 경우를 많이 접하게 될 것이다.
빅 오 분석법을 제대로 이해하고 있다면 더욱 좋은 평가를 받을수 있다.
빅오 분석법은 입력 값의 개수에 따라 알고리즘이 수행되는 데 걸리는 시간을 바탕으로 알고리즘의 효율성을 평가하는 실행 시간 분석법.
두가지예의 분석시
ex) 배열에서 최대값을 구하는 함수를 구현.
첫번째 방법
배열(크기는 n)의 모든 원소를 하나씩 확인하면서 가장 큰 수를 계속 기록한 다음, 확인이 끝나고 나면 그 값을 반환하는 방법.
int CompareToMax(int array[], int n )
{
int curMax , i ;
int ( n <= 0 )
return -1;
curMax = array[0];
for( i = 0 ; i < n ; i++ )
{
if( array[i] > curMax )
{
curMax = array[i];
}
}
return curMax;
}
두번째 방법
각 값을 다른 모든 값과 비교하는 방법이다. 다른 모든 값이 주어진 값 이하라면 그 값이 최대값이 되는 구현.
int CompareToAill(int array[] , int n)
{
int i,j ;
bool isMax ;
if(n <= 0)
return -1;
for( i = n-1 ;i > 0 ; i--) {
isMax = true;
for( j = 0 ; j < n ; j++) {
if( array[j] > array[i])
isMax = false;
}
if(isMax)
break;
}
}
빅 오 분석법을 통한 분석
빅 오 분석법의 경우 입력 값의 크기를 n이라고 가정한다. 위의 예에서는 배열에 있는 원소의 개수가 바로 n이 된다. 문제에 따라 n이 연결 리스트의 노드 개수를 나타낼 수도 있고, 특정 자료형의 비트 수 일 수도 있고, 해시 테이블에 들어있는 항목의 개수일 수도 있는 등 다양한 값들이 입력 값의 크기 n으로 쓰일 수 있다.
CompareToMax 에서는 각 배열 원소와 최대값을 한 번씩 비교했다. 따라서 n개의 입력된 항목이 각각 한번씩 확인되기 때문에 총 n번의 확인 작업이 수행된다. 이런 상황을 O(n) 이라고 표현하며 "선형 시간" 내에 수행된다고 말하기도 한다.
# 빅 오 분석을 할 떄는 최 고차항 즉, n이 매우 커질 때 가장 큰 항만 남기고 다른 항은 다 무시한다.
지금 다루고 있는 예에서는 n이 최고차항이기 때문에 CompareToMax 함수는 O(n) 이 된다.
CompareToAll의 경우 약간 복잡하나 배열의 어느 위치에 가장 큰 수가 있는지를 가정해 봐야한다. 최대 원소가 배열의 맨 뒤에 있다고 가정할 경우, 이런 경우에는 n개의 원소를 n개의 다른 원소와 비교해야 한다.
따라서 O(n^2) 알고리즘이다.
최선, 평균, 최악 케이스
CompareToAll을 분석할 때 최대값이 맨 뒤에 있다고 가정했기 떄문에 불공평한 것이 아닐까 하는 생각을 해볼수 있다. 실제로도 그러하며 이런 문제 때문에 최선, 평균, 최악 케이스의 실행 시간을 따져봐야 하는 문제가 생긴다.
CompareToAll을 테스트 할 때, 최대값이 가운데 있는 경우를 생각해 보자. 최대값이 중간에 있다면 절반만 n번씩 확인해 보면 된다. 그러면 n(n/2)번만 확인하면 된다. 각 값을 실제로 확인하는데 걸리는 시간은 코드에 의해 생성되는 기계어와 CPU에서 그러한 명령들을 수행하는데 걸리는 시간에 의해 크게 좌우된다. 따라서 1/2이라는 숫자가 그런 큰 의미를 가진다고 볼 수는 없다.(?) 빅 오 분석법에서는 모든 상수 인자들을 빼버리기 때문에 CompareToAll의 평균 케이스도 최악의 케이스와 별로 다를 바가 없다.
빅 오 분석법을 적용하는 방법
일반적으로 빅 오 실행시간분석은 다음과 같은 방법으로 하면된다.
1. 입력 값이 무엇인지 확인하고 어떤 것을 n으로 놓아야 할지 결정한다.
2. 알고리즘에서 수행해야 할 연산 횟수를 n의 식으로 표현한다.
3. 차수가 제일 높은 항만 남긴다.
4. 모든 상수 인수를 없앤다.
최적화와 빅 오 분석법
알고리즘을 최적화한다고 해서 반드시 전체 실행 시간이 빨라지는 것은 아니다.
CompareToAll을 다음과 같이 최적화 한다고 생각해 보자. 각 수를 다른 모든 수와 비교하는 대신 배열에서 그 수보다 뒤에 있는 수하고만 비교한다고 해 보자. 그 수 앞에 있는 수는 전부 지금 기준이 되는 수와 비교해 본적이 있기 때문이다. 따라서 현재 비교하고자 하는 수보다 뒤에 있는 원소들하고만 비교해도 알고리즘은 정확하게 작동한다.
이렇게 하고나면 최악의 실행시간은 어떻게 될까?
이 알고리즘에서 최악 케이스의 실행 시간도 여전히 O(n^2)에 머무른다.
입력 개수가 많아지면 이런 식으로 알고리즘을 최적화 한다고 해서 실행 시간이 크게 빨라지지 않는다는 것이다.
요약
문제를 풀 때는 인터뷰어와 의사소통을 최대한 활발하게 하도록 하자.
문제를 분석하고 답을 코딩하는 각 단계에서 자신이 무슨 생각을 하고 있는지 인터뷰어에게 알릴 수 있어야 한다.
PROGRAMMING INTERVIEWS EXPOSED 발췌.!
