✅ 한 것들
- 코딩 인터뷰 완전 분석
- 백준
- Project FDS
📖 코딩 인터뷰 완전 분석
VII 기술적 문제
알고 있어야 할 것들
2의 승수 표
| 지수 x | 2^x 값 | 근사치 | 메모리 요구량 (1바이트 기준) |
|---|---|---|---|
| 10 | 1,024 | ≈ 1천 | ≈ 1 KB |
| 16 | 65,536 | ≈ 64 KB | |
| 20 | 1,048,576 | ≈ 100만 (1M) | ≈ 1 MB |
| 30 | 1,073,741,824 | ≈ 10억 (1G) | ≈ 1 GB |
| 32 | 4,294,967,296 | ≈ 4 GB | |
| 40 | 1,099,511,627,776 | ≈ 1조 (1T) | ≈ 1 TB |
실제 문제 살펴보기
- 경청하기
- 주어진 정보를 기억해두거나 써둬라
- 예제를 직접 그려보기
- 문제 듣자마자 화이트보드에 그려라
- 명확하고 일반적인 예제를 만들어라
- 일단 브루트포스로 시도해보라
- 너무 뻔하더라도 일단 시간 및 공간복잡도 설명한 뒤 개선해라
- 최적화
- 간과한 정보가 있는지 찾아보자
- 새로운 예제를 만들어보자
- 시간과 공간의 실익을 따져 보고 균형을 맞추라
- 필요한 정보를 미리 계산해두라
- 해시테이블을 사용하라
- 최선의 수행 시간이 무엇인지 생각하라
- 검토하기
- 최적 알고리즘 완성해도 바로 코딩하지 마라
- 화이트보드 코딩은 오래 걸리니까 가능하면 완벽하게 만들고 코딩해라
- 어떤 변수를 사용하여 언제 값을 변경할 건지 등 세세한 부분도 미리 정해라
- 코드 작성하기
- 화이트보드에 작성할 때 각 줄이 비스듬해지지 않게 조심하라
- 모듈화된 코드를 사용하라
- 에러를 검증하라
- 필요한 경우 다른 클래스나 구조체를 사용하라. 그 클래스의 세부사항은 시간 남을 때.
- 좋은 변수명을 사용하라. 변수명이 반복되면 앞으론 줄여서 쓰겠다고 면접관에게 설명한다.
- 리팩토링할 부분을 발견하면, 면접관에게 설명 후 시간을 들일지 판단하여 리팩토링 여부 결정한다.
- 테스트
- 손으로 직접 테스트하면 느리다
- 개념적 테스트부터 시작하라: 코드를 한 줄 한 줄 읽어나가며 어떤 일을 수행하는지 분석하라
- 코드에서 평소와 다르게 돌아가는 부분을 살펴보라: x=length-2, i=1부터 시작하는 for문 등
- 버그가 자주 발생하는 부분을 살펴보라: 재귀함수 base case, 정수 나눗셈, 이진 트리 null 노드, 연결리스트 시작 끝 등
- 작은 규모 테스트 돌려보라: 너무 큰 크기 테케 쓰지 마라
- 특별한 경우 테스트하라: null, 단일 원소, 극단적 입력 등
최적화 및 문제풀이 기술 #1: BUD를 찾으라
병목 현상
- big-O가 가장 큰 곳을 파악하고 줄이려 해본다
- 검색 여러 번 하는 것처럼 반복 수행하는 부분 줄이려 해본다
예제: 서로 다른 정수로 이루어진 배열이 있을 때 두 정수의 차이가 k인 쌍의 개수를 세라.
- 무식한 방법: 배열 원소 for문 2번 돌린다
- 정렬 후 탐색: 정렬할 때 O(NlogN), 이진탐색으로 x-k 또는 x+k 찾으려면 O(logN)을 N번. 결국 O(NlogN).
- 해시테이블: 모든 원소를 해시테이블에 넣은 뒤 x+k 또는 x-k가 있는지 확인하면 O(N)
⚔️ 백준
11049 행렬 곱셈 순서
ll MinMult(int stt, int end, vvl& dp, vp& mat)
{
if (stt == end) return 0;
if (dp[stt][end] != -1) return dp[stt][end];
int sttF = mat[stt].first;
int sttE = mat[stt].second;
int endF = mat[end].first;
int endE = mat[end].second;
ll minMult = sttF*sttE*endE + MinMult(stt+1,end,dp,mat);
minMult = min(minMult, sttF*endF*endE + MinMult(stt,end-1,dp,mat));
for (int i = stt+1; i < end-1; i++)
{
ll base = MinMult(stt, i-1, dp, mat) + MinMult(i + 1, end, dp, mat);
int iF = mat[i].first;
int iE = mat[i].second;
ll c1 = base + sttF * iF * iE + sttF * iE * endE;
ll c2 = base + iF * iE * endE + sttF * iF * endE;
minMult = min(minMult, c1);
minMult = min(minMult, c2);
}
dp[stt][end] = minMult;
return minMult;
}A(중간)B → (A중간)B or A(중간B)인 하향식으로 풀어봤는데,
예제 + 질게 반례 다 통과하는데 제출하면 1% 틀림.
답지 보니까 그냥 A/B로 나누고 상향식으로 풀면 훨씬 간단.
ll MinMult(int stt, int end, vvl& dp, vp& mat)
{
if (stt == end) return 0;
if (stt + 1 == end) return mat[stt].first * mat[stt].second * mat[end].second;
if (dp[stt][end] != -1) return dp[stt][end];
ll minMult = numeric_limits<ll>::max();
for (int i = stt; i < end; i++)
{
minMult = min(minMult,
MinMult(stt,i,dp,mat)+MinMult(i+1,end,dp,mat)
+ mat[stt].first * mat[i].second * mat[end].second);
}
dp[stt][end] = minMult;
return minMult;
}하향식은 유지하고 A/B로 나누니까 맞긴 했는데,
3개로 나누면 틀렸던 이유가 궁금해서 GPT에게 물어보니,
가운데가 무조건 단일 행렬이어야 할 이유가 없다고 함. 반례 존재.
당장 A(BCD)E면 불가능.
🎮 Project FDS
생각해보니 굳이 이전 프로젝트에서 다시 시작할 이유가 없다.
프로젝트 수정 사항과 깃허브 롤백 및 새 프로젝트 생성.
쿼터뷰 이동 구현
- 참고 : www.youtube.com/watch?v=z3dequX5g_E
- 물체랑 직접 상호작용하게 하려면 CharacterController 말고 Rigidbody 써라
- Rigidbody,linearVelocity 직접 조작하지 마라. 물리 파괴함.
- AddForce를 써라
- ForceMode.VelocityChange 써라. 물제 질량에 관계 없어진다.
- 미끄러지는 이동 막으려면 linear damping을 조절해야 하는데, 이대로는 느리게 낙하한다.
- GrondCheck로 damping value를 조절해야 함
- raycast를 쏘면 모서리 걸을 때 공중 판정 된다
- sphere collider로 판단하면 벽에 붙었을 때도 바닥 판정 된다
- 해결 1 : 모든 바닥에 별도 Layer 설정
- 해결 2 : 플레이어 down 벡터와 땅 normal 벡터를 비교하여 일정 각도 이하면 땅이라고 간주
- sphere collider의 크기를 플레이어 collider보다 줄이면 여러 edge cases 생김
- 경사 미끄러짐 막기
- 벡터 분해해서 상쇄 벡터 계산해줘야 함.
- 계단 오르기
- 해결 1 : 모델링은 계단처럼, 콜라이더는 경사로로 만든다
- 해결 2 : 계단에 부딪힐 때마다 위로 살짝 텔레포트시킨다
- 텔레포트엔 Rigidbody.MovePosition()을 사용하라
- 1인칭이라면 Rigidbody Interpolate 설정을 Interpolate로 설정하라
- CharacterController를 사용해도 된다
- 위의 모든 구현이 이미 되어있다
- Rigidbody 상호작용만 직접 적용하면 된다
- 사실 웬만하면 CharacterController 쓰는게 좋다
결론은 허무하게도 CharacterController 쓰라는 말. 내일 구현하기.
너 정말 **핵심**을 찔렀어