코딩 테스트 준비
익일, 翌日
명사＝이튿날순화어는 `이튿날', `다음날'.
1️⃣ 알고리즘
문제를 해결하는 최선의 선택.
대부분의 코딩 테스트에서는 문제의 설명, 입출력 예시, 제한사항, 주의사항 등으로 문제를 구성합니다.
알고리즘 문제는 개발자의 사고방식을 연습하는데 도움이 된다.
의사코드(pseudo code)
프로그래밍 언어로 코드를 작성하기 전에 우리가 쓰는 일상 언어로 프로그램이 작동하는 논리를 먼저 작성하는 것. 논리적이고 구체적인 작성이 중요.
- 시간이 단축된다
- 디버깅에 용이하다
- 프로그래밍 언어를 모르는 사람과 소통할 수 있다.
자연어 / 자연어+프로그램 언어
인풋과 아웃풋을 정리 ➡ 한글로 옮긴다 ➡ 코드로 옮긴다
2️⃣ 시간 복잡도(Time Complexity)
코드의 효율적인 방법을 고민한다는 것은 시간 복잡도를 고민한다는 것.
입력값의 변화에 따라 연산을 실행할 떄, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?
- Big-O(빅-오)
- Big-Ω(빅-오메가)
- Big-θ(빅-세타)
시간 복잡도를 최악, 최선, 중간(평균)의 경우에 대하여 나타내는 방법이다. 빅오 표기법을 주로 쓴다. 최악의 경우도 고려하여 대비하는 것이 대응에 바람직하기 때문.
✅ O(1)
constant complexity
입력값이 증가하더라도 시간이 늘어나지 않는다. 입력값의 크기와 관계없이, 즉시 출력값을 얻어낼 수 있다.
✅ O(n)
linear complexity
입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것.
✅ O(log n)
logarithmic complexity
이진 탐색 트리, Up & Down 게임 등. 경우의 수가 절반으로 줄어드는 경우.
✅ O(n^2)
quadratic complexity
입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것.
✅ O(2^n)
exponential complexity
가장 느린 시간 복잡도. 재귀로 구현한 피보나치 수열이 대표적이다.
전공책 다시 살펴볼 것! 블로깅 알차게 하기
결국 실전에서 적용이 제일 중요
3️⃣ 탐욕 알고리즘(Greedy)
Greedy
"탐욕스러운, 욕심 많은"
Greedy Algorithm
선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫒아 최종적인 해답에 도달하는 방법. 아래의 세 단계
- 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택합니다.
- 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사합니다.
- 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복합니다.
탐욕 알고리즘을 적용하려면 문제가 다음의 2가지 조건을 성립해야한다.
- 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않습니다.
- 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성됩니다.