✅ 한 것들

---

• 코딩 인터뷰 완전 분석

📖 코딩 인터뷰 완전 분석

---

불필요한 작업

예제 : a,b,c,d가 1<, <1000일 때 a^3+b^3=c^3+d^3 만족하는 모든 자연수 출력

• 무식한 방법 : 4중 루프
  • d for문은 찾았을 때 break하면 최적화
• 아예 for문 안 돌리고 수식으로 있는지 확인 가능
  • O(n^4)에서 O(n^3)으로 줄어든다

중복되는 작업

위의 예제 다시 살펴보기

• 근본적으로 모든 (a,b) 쌍에 대해 수식 만족 (c,d) 찾는 것
• 그런데 왜 모든 (a,b)에 대해 가능한 모든 (c,d)를 찾는 건가?
• 그냥 해시테이블에 (c,d) 리스트를 만들어두고, (a,b) 쌍에 대해 대응되는 (c,d)를 리스트에서 찾아보면 된다
  • (c,d) 쌍은 (a,b) 쌍과 사실상 같으므로 (a,b) 쌍을 따로 for문 돌릴 필요도 없이 해시테이블에 저장한 리스트의 중복조합 하면 된다
  • O(n^2)으로 줄어든다

최적화 및 문제풀이 기술 #2: 스스로 풀어보라

일단 컴퓨터가 아니라 직관적으로 문제를 풀어봐라.

예제: 짧은 문자열 s와 긴 문자열 b가 주어졌을 때, 문자열 b 안에 존재하는 문자열 s의 모든 순열을 찾는 알고리즘

• s의 모든 순열 찾고 그걸 b에서 찾으면 O(S!*B)가 된다
• 컴퓨터 대신 직접 세려 하면 훨씬 간단한 방법으로 셀 것이다
  • 방법 1: b를 s의 개수로 끊어서 차례로 살펴본 뒤 s의 순열을 만족하는지 확인한다
  • 방법 2: b를 순회하면서 s에 속한 문자가 있으면 거기서부터 s의 순열 만족하는지 확인한다
  • O(B*S), O(B*SlogS), O(B*S^2) 중 하나가 된다. 최적은 사실 O(B)지만, 처음보단 나아졌다.

최적화 및 문제풀이 기술 #3: 단순화, 일반화하라

• 단계 1: 자료형 같은 제약조건을 단순화하거나 변형시킨다
• 단계 2: 단순화된 버전의 문제를 푼다
• 단계 3: 단순화 알고리즘 완성되면 복잡한 형태로 다듬는다

예제: 문자열에서 잘라낸 단어들로 특정 문자열을 만들 수 있는지 확인

• 글자 하나씩 잘라내는 걸로 단순화해보자
  • 특정 문자열에서 각 문자가 출현한 횟수를 세서 배열에 저장한 다음,
  • 참조 문자열에 출현한 문자 수보다 같거나 많은지 확인한다
• 일반화해도 비슷하다. 단어를 key로 하는 해시테이블 이용하면 된다

최적화 및 문제풀이 기술 #4: 초기 사례(base case)로부터 확장

초기 사례 (n=1같은 문제) 를 푼 뒤, 해법을 확장해나간다.

예제: 문자열 모든 순열 구하라 (모든 문자는 고유하게 등장)

• a의 순열을 구하고, ab의 순열을 구해본다, abc의 순열은?
• ab의 가능한 모든 자리에 c를 우겨넣어본다

최적화 및 문제풀이 기술 #5: 자료구조 브레인스토밍

일련의 자료구조를 차례차례 살펴보며 하나씩 적용해본다.
"트리를 써 보자"라는 결심만으로 문제가 자연스럽게 풀리는 경우가 있다.

가능한 최선의 수행 시간 (Best Conceivable Runtime(BCR))

최선 수행 시간이 무엇일지 생각하는 것만으로 힌트 발견 가능

예제: 정렬된 배열 2개가 주어졌을 때 공통으로 들어있는 원소 개수 찾아라.
두 배열의 길이는 같고, 하나의 배열 안에서 동일한 원소는 하나만 존재한다.

• brute force는 A의 각 원소가 B에 존재하는지 찾아보는 것. O(N^2)이 걸린다.
• 이 문제의 BCR은 O(N)이다. 모든 원소를 적어도 한 번씩 살펴봐야 하기 때문이다.
  • 보장은 못하지만 O(N)까지 개선할 수도 있는 가능성이 있다는 것
• 탐색하는 부분 때문에 두번째 O(N)이 나왔다. O(N)보다 빠르게 탐색 가능한가?
  • 이진 탐색을 이용하면 O(logN)에 원소 찾기 가능
• BCR이 O(N)이므로 그 이하인 건 자유롭게 시도해봐도 된다
  • B의 원소를 해시테이블에 모두 넣어놓는건 O(N)안에 할 수 있고, 검색은 O(1)이다
  • 전체 수행 시간은 O(N)으로 줄어든다
• 더 개선할 수 있을까? BCR보다 작아질 순 없으므로 공간 복잡도를 개선해야 한다
  • 가능하면 O(1) 공간에 동작했으면 좋겠다
  • 가능하면 O(N) 시간에 동작했으면 좋겠다
  • 배열이 정렬됐다는 조건을 사용하자
• 현재까지 최선 알고리즘 중 추가 공간 사용하지 않는 건 이진 탐색이다
  • 배열이 정렬돼있으므로, 이진 탐색할 때 이전 위치에서 시작하면 된다
  • 사실 이진 탐색할 필요도 없다. 선형 탐색하면서 이전 위치에서 시작하면 된다.
  • O(N) 시간과 O(1) 공간에 동작한다