알고리즘 문제 접근 및 최적화 방법

알고리즘 문제 접근 순서

1. 듣기 : 문제 설명과 관련된 것이라면 어떤 정보든지 집중해서 듣는다. 최적 알고리즘을 설계하기 위해선 모든 정보가 필요하다.
   
   
2. 예제 : 대부분의 예제들은 크기가 아주 작거나 특별한 사계인 경우가 많다. 직접 예제를 만들어서 디버깅하자. 직접 만든 예제가 특별한 경우인지 충분히 큰 입력인지 고려한다.
   
   
3. 무식하게 풀기 : 무식한 방법으로 풀어보자. 알고리즘의 효율을 생각하지 말고 단순한 알고리즘과 시간 복잡도를 먼저 생각한 다음 최적화를 시도한다. (아직 코딩 금지)
   
   
4. 최적화 : 무식한 방법을 개선해 나간다. 
   
   • 문제에서 언급된 정보를 모두 사용했는가?
   • 예제를 손으로 풀어본뒤 어떻게 풀었는지 과정을 다시 생각해본다.
   • '잘못된'방법으로 풀어본뒤 왜 알고리즘이 틀렸는지 생각해 본다. 
   • 시간과 공간의 이익 관계를 고려한다. 
5. 검토 : 최적의 해법을 찾았으면 코드로 구현하기전 검토해 본다.
   
   
6. 구현 : 코드를 모듈화 시키고 아름답지 못한 부분은 리팩토링하여 아름다운? 코드를 완성해 나간다!
   
   
7. 테스트 : 테스트도 순서가 있다.
   1. 개념적 테스트 : 코드리뷰하듯이 훑어본다.
   2. 산술연산이나 null 같은 부분이 있는지 본다.
   3. 작은 크기, 큰 크기의 테스트를 검증해본다
   4. 극단적이거나 특이한 입력을 테스트 한다.

 

*해시테이블(HashTable) 굉장히 중요하다고 한다. 짚고 넘어가자.

해시테이블은 연관 배열 구조를 이용하여 키(key)에 값(value)를 저장하는 자료구조이다. 

자세히 설명된 글을 링크한다.

Hash, Hashing, Hash Table(해시, 해싱 해시테이블) 자료구조의 이해

병목현상

알고리즘 최적화? BUD를 해결하라.

• Bottlenecks : 병목현상
• Unnecessary work : 불필요한 작업
• Duplicated work : 중복되는 작업

병목현상

알고리즘에서 전체 수행시간을 잡아먹는 부분을 뜻한다.

--> 코드에서 O(NlogN) 과 O(N)이 소요되는 두가지 부분이 있다. 여기서 O(N)을 O(1)로 줄이더라고 여전히 시간은 O(NlogN)일 것이다.

예제 : 서로 다른 정수로 이루어진 배열이 있을 때 두 정수의 차이가 k인 쌍의 개수를 세라.
예를 들어 주어진 배열이 {1,7,5,9,2,12,3} 이고 k=2 면 
두 정수의 차이가 2인 쌍은 다음과 같이 4개가 존재한다.
(1,3) (3,5) (5,7) (7,9)

방법은

1) 정렬한 뒤 이진탐색을 통해 답을 찾는다. O(NlogN) + O(NlogN)

2) 정렬하지 말고 찾아본다. --> 해시테이블을 이용한다. 배열의 모든 원소를 해시테이블에 넣은 뒤 조건을 만족하는 쌍이 있는지 확인한다. O(N)

1) 정렬한 뒤 이진탐색을 통해 답을 찾는다. O(NlogN) + O(NlogN)

2) 정렬하지 말고 찾아본다. --> 해시테이블을 이용한다. 배열의 모든 원소를 해시테이블에 넣은 뒤 조건을 만족하는 쌍이 있는지 확인한다. O(N)

이다.

 

불필요한 작업

예제 : a, b, c, d가 1에서 1000사이에 있는 정수 값 중 하나일 때 
a^3+b^3+c^3+d^3을 만족하는 모든 자연수를 출력하시오

방법은

 1) 4중루프 돌린다 O(N^4)

 2) d에 대한 식을 통해 a, b, c만 구한다 O(N^3)

 3) 문제는 근본적으로 모든 (a,b) 쌍에 대해 수식을 만족하는 (c,d)쌍을 찾는 것과 동일하다. 

    --> c,d를 키로 a,b를 value로 갖는 해시 테이블을 만든 뒤 필요한 경우 키값을 이용하여 가능한 모든 (c,d)쌍을 구한다. O(N^2)

 1) 4중루프 돌린다 O(N^4)

 2) d에 대한 식을 통해 a, b, c만 구한다 O(N^3)

 3) 문제는 근본적으로 모든 (a,b) 쌍에 대해 수식을 만족하는 (c,d)쌍을 찾는 것과 동일하다. 

    --> c,d를 키로 a,b를 value로 갖는 해시 테이블을 만든 뒤 필요한 경우 키값을 이용하여 가능한 모든 (c,d)쌍을 구한다. O(N^2)

이다.

 

해시테이블이 중요한것 같다.

 

 

 

 

 

 

 

[참고] 

CRACKING the CODING INTERVIEW