코딩인터뷰 퀘스천"메모" 프로그래밍 기초, 알고리즘, 연결 리스트, 스택

.

.

책 읽으면서 메모했던 내용들 옮겨봅니다.

---

챕터1 프로그래밍 기초 / 12, 13 프로그래밍 테크닉, 기초 문제

-네임 맹글링(Name mangling)

C컴파일러는 언더바’_’ 를 붙여 함수나 심볼을 연결.

main() 함수는 _main() 심볼명, int counter; 는 _counter 심볼명에 링크.

C++ 컴파일러는 함수 오버로딩 메커니즘. 단순 언더바를 붙이지 않고, 링커가 ‘맹글링’을 사용.

네임 맹글링 : C++ 컴파일러가 동일한 이름의 함수, 변수들을 라인 식별자, 인자 크기 등의 확장 정보들을 가진 어떤 명칭(유일 심볼명)으로 변경, 연결하기 위한 메커니즘.

​

함수명 맹글링 : <function index><function name>@<argument size>

변수명 맹글링 : <variable name>@@<UNIQUE ID>

ex) int Test(int a, int b) => _1add@8

ex) int Test(int a, int b, int c) => _2add@12

​

- C++ 가상함수(Virtual Function), 가상테이블(Virtual Table, 혹은 가상 함수 테이블) 개념

컴파일 -> 베이스 클래스에 *__vptr 숨은 포인터 추가. 가상 테이블 가리키도록 자동설정. 가상함수테이블은 인덱스 배열. 가상함수를 가진 클래스를 상속받을 때 적절한 포인터를 담도록 설정.

​

- 추상클래스와 인터페이스 개념과 차이 = 순수추상클래스

​

챕터2 알고리즘, Big-O 표기법, 점근적 표기, 점근 분석

알고리즘 분석의 목표.

실행 시간뿐 아니라, 메모리, 개발자의 노력, 관리비용 등을 포함해서 알고리즘(또는 솔루션)을 비교하는 것.

​

점근적 표기 (Asymptotic Notation)

f(n) = n^2 + 500, 최악의 경우

f(n) = n + 100n + 500, 최선의 경우

알고리즘의 최선, 평균, 최악 / 세 경우에 대해 상한계, 하한계 정의 필요.

​

Big-O 표기법 (Big-O Notation)

상한계 표기 제공. f(n) = O(g(n)) 으로표현. n이 큰 수일 때, f(n) 의 상한계는 g(n).

ex) f(n) = n^4 = 100n^2 + 50 일 때 n^4 가 g(n). n이 큰 수일 때 g(n)은 f(n)에 대한 최대 성장률

정의,

O(g(n)) = {f(n): 모든 n >= n0 에 대해, 0 <= f(n) <= cg(n)을 만족하는 양의 상수 c와 n0이 존재한다}

​

Omega-빅오메가 표기법

하한계를 제공

​

Theta-빅세타 표기법

상한계, 하햔계 동일한지 아닌지 결정.

​

왜 점근 분석이라고 불리는가(Asymptotic Analysis)

n값이 증가할 때 f(n)에 근사하는 함수 g(n) 을 알아내려고 하는것. g(n)은 n값이 증가할 때 f(n)의 근사 곡선을 가짐. 점근 곡선이라고 함. (Asymptotic curve). 즉, g(n) 은 f(n)에 대한 점근 곡선. = 점근 분석.

​

알고리즘 분석 너무 어려운데

​

챕터4 연결 리스트

연결리스트, 배열, 동적배열

연결리스트 = 시작 위치 삽입/삭제가 O(1) 나머진 모두 O(n)

배열 = 인덱싱 O(1), 마지막 위치 삽입/삭제 O(1), 메모리낭비 0

동적배열 = 인덱싱 O(1), 마지막 위치 삽입/삭제 O(1), 단 공간이 꽉 찼을 때 마지막 삽입은 O(n), 메모리낭비 O(n)

​

문제: 연결리스트의 끈에서 n번째 노드 찾기.

Brute-Force 접근 방식. 시간 복잡도 향상은 해시 테이블 이용해서 향상.

key = index, value = pointer

​

한 번의 탐색으로 참조 가능한가?

pNthNode, pTemp 두 개의 포인터를 활용. pTemp가 n번 이동한 뒤에 pNthNode 가 따라 움직이게하고, pTemp가 끝에 다다르며 pNthNode 가 마지막에서 n 번째 노드가 됨. O(n), O(1)

​

문제 : 주어진 연결 리스트가 순환하는지 검사하시오.

해시 테이블에 노드를 하나하나 넣고 해시충돌이 발생하는지 검사.

시간 복잡도 : O(n)

공간 복잡도 : O(n)

​

O(n)에 풀기위한 솔루션 = 서로 다른 속도로 움직이는 두 개의 포인터로 탐색을 돌리고, 두 포인터가 어느 순간 만난다면 순환구조가 있는 것.

= 플로이드 순환 찾기 알고리즘 (Floyd cycle finding algorithm)

​

문제 : 연결 리스트의 가운데를 구하는 방법.

두 개의 포인터를 출발시키는데, 두 번째 포인터는 두 배의 속도로 이동. 두 번째 포인터가 끝에 도달했을 때 처 번째 포인터의 위치가 중간 노드.

​

챕터5 스택

컴파일러 파서 문자열 파싱 알고리즘에 쓰임.

중위, 전위, 후위 표기법.

중위표기 A, A+B, (A+B)+(C-D)

전위표기 A, +AB, ++AB-CD

후위표기 A, AB+, AB+CD-+

​

GetMnimum()이 O(1) 인 스택 설계.

main 스택에 push/pop 할 때 같이 관리한 min 스택을 추가/관리.

.

.

.