[Book] 프로그래밍 면접 이렇게 준비한다

책을 읽으며 따로 정리하면 좋을 내용만 작성하였다.
기술 면접을 준비하는 사람에게 전체적으로 다시 복습하기 좋은 책인 것 같다. 추천!

 

---

1. 빅 오 분석법

입력 값의 개수에 따라 알고리즘이 수행되는데 걸리는 시간을 바탕으로 알고리즘 효율성을 평가하는 실행 시간 분석법이다.

• n이 매우 큰 경우를 가정하기 때문에 점근적인 실행 시간만 따진다. 즉 최고차항만 표시한다.
• 입력 값의 개수를 n개로 가정하고 n개의 입력 값을 몇 번이나 확인해야 하는지를 n의 식으로 표현한다.
  • O(1): 상수 시간 내에 수행된다는 뜻으로 입력의 개수와 무관하게 항상 일정한 시간 안에 실행이 완료된다.
  • O(n): 선형 시간 내에 수행된다는 뜻으로 알고리즘을 실행시키는데 걸리는 시간이 입력된 항목의 개수에 선형적으로 비례하여 증가한다.

종류

 

---

2. 정렬

1) 정렬 알고리즘을 선택할 때 고려해야 할 점

• 정렬할 데이터 양: 데이터가 적을 때는 실행 시간이 거의 똑같기 때문에 어떤 알고리즘을 쓰든 상관이 없다.
• 데이터와 메모리: 데이터가 너무 많아 메모리에 다 올릴 수 없다면 조금씩 잘라서 정렬을 하고 잘라진 각 조각을 합쳐서 전체 정렬된 데이터를 만들어야 한다.
• 데이터가 정렬된 정도: 알고리즘에 따라 기존 데이터의 정렬에 따라 효율이 달라질 수 있다.
• 필요한 추가 메모리의 양: 추가적인 공간을 사용하지 않는 정렬을 제자리 정렬이라 부른다.
• 상대 위치 보존 여부: 원소들의 상대적인 위치가 그대로 유지되는 정렬을 안정(stable) 정렬이라 부른다.

 

	시간 복잡도		정렬된 정도 영향	제자리 정렬	안정 정렬
선택 정렬	O(n²)		X	O	X
삽입 정렬	최선 O(n), 평균 최악 O(n²)		O	O	O
퀵 정렬	최선 평균 O(nlogn), 최악 O(n²)		X	X (log n~n)	X
병합 정렬	O(nlogn)		X	X (n)	O

 

2) 정렬 알고리즘의 특징

1. 선택 정렬
   • 데이터를 맞바꾸는 횟수가 최대 n-1번이기 때문에 원소를 바꾸는 작업이 비싸거나 복사 연산이 매우 느린 경우 사용하면 좋다.
2. 삽입 정렬
   • 이미 정렬된 리스트에 새 원소를 추가할 때 매우 효율적이다.
   • 소량의 데이터 집합을 처리할 때 좋기 때문에 다른 더 복잡한 알고리즘을 만드는 기본 단위로도 쓰인다.
3. 퀵 정렬
   • 어떤 피벗 값을 고르는지에 따라 성능이 결정된다. 보통 중간 값을 선택한다.
   • 데이터에 대한 정보가 없을 경우 선택한다.
4. 병합 정렬
   • 데이터 집합이 메모리에 한 번에 올리기 너무 클 때 사용하기 좋다.
   • 시간 복잡도가 모두 일정하기 때문에 시간의 상한을 철저하게 지켜야 할 때 좋다.

 

https://tech-interview.tistory.com/19?category=812259

[C++] 정렬(Sort)

 

---

3. 동시성

스레드와 공유 자원 사이의 상호작용을 제어할 때는 스레드 동기화가 필요하다.

 

1) 모니터

• 상호 배제 자물쇠로 보호되는 루틴의 집합
• 스레드는 자물쇠를 획득하기 전까지는 모니터에 속한 루틴을 하나도 실행할 수 없다.
• 한 모니터 내에는 한 스레드씩 실행되고 다른 스레드는 전부 지금 실행 중인 스레드에서 그 자물쇠를 놓아줄 때까지 기다려야 한다.
• 필요한 자물쇠를 자동으로 획득하고 해제한다.

 

2) 세마포어

• 상호 배제 세마포어(뮤텍스): 기본적인 방식으로 스레드에서 공유 자원을 이용하려면 자물쇠를 획득해야 한다.
• 카운팅 세마포어: 최대 n개의 스레드가 동시에 자원에 접근할 수 있다.
• 각 스레드에서 획득한 자물쇠를 해제하는 작업을 일일이 챙겨야 한다.

 

3) 바쁜 대기

• 대기 중인 스레드가 여전히 활성 상태긴 하지만 실제로는 아무 일도 하지 않는 것
• 스레드에서 두 번째 스레드가 끝날 때까지 대기하는 것 외에는 아무 일도 하지 않음에도 불구하고 프로세서는 여전히 이 스레드를 실행시키기 때문에 바쁜 대기라고 부른다.
• 모니터나 세마포어를 이용해 피할 수 있다.

 

---

4. 객체지향 프로그래밍

1) 가상 함수

• 함수를 실제로 호출하는 객체가 어떤 클래스인지에 따라 구현이 결정되는 함수이다.
• C#과 C++에서는 virtual 키워드를 써서 선언한다.
• 다형성을 활용할 때 유용하지만 룩업이 필요하기 때문에 오버헤드가 발생할 수 있다.
• 순수 가상 함수: 선언은 되지만 정의는 되지 않는 함수로 이 함수가 들어있는 클래스는 추상 클래스이다.

 

2) 인터페이스

• 클래스와 별도로 일련의 연관된 함수를 선언한다. 이때 몸체가 없는 함수의 원형(순수 가상 함수)만 정의한다.
• 클래스 계층 구조와는 독립적으로 애플리케이션 프로그래밍 인터페이스를 정의하는 역할이다.
• 어떤 클래스에 특정 인터페이스의 모든 함수가가 있다면 그 클래스는 해당 인터페이스를 구현한다라고 표현한다.
• 서로 관련이 없는 클래스에서 개념적으로 연관된 기능을 작동시킬 수 있는 공통적인 방식이 필요하지만 그 기능을 구현하는 방법이 다른 경우에 쓰기 좋다.
• 인스턴스를 만들 수 없다.

 

3) 추상 클래스

• 함수를 선언하지만 모든 함수를 정의하지 않는다.
• 데이터 멤버를 추가하거나 다른 클래스의 서브 클래스로 만들 수 있다. 그러나 구상 클래스와 달리 함수 중 일부는 정의하지 않고 서브 클래스에서 정의해서 쓰도록 남겨둔다.
• 베이스 클래스로 상속해서 더 구체적인 클래스를 만들어서 쓰는 경우에 쓰기 좋다.
• 인스턴스를 만들 수 없다.

 

---

5. 비트 조작

1) 2의 보수 이진 표기법

컴퓨터 내부에서는 숫자를 보통 2의 보수 이진 표기법으로 표현한다.

• 첫 번째 비트는 부호 비트이다. 0이면 양수 1이면 음수를 뜻한다.
• 양수의 경우엔 이진수 표기법과 동일하고 음수의 경우엔 각 비트를 전부 뒤집고 1을 더하는 규칙을 적용한다.

 

2) 시프트 연산을 이용한 최적화

오른쪽으로 1비트 시프트 시키는 것은 2로 나누는 것과 같고 왼쪽으로 1비트 시프트 시키는 것은 1을 곱하는 것과 같다.