코딩테스트 그리디/구현

코딩테스트 그리디/구현

 

그리디(greedy) 알고리즘(탐욕법)

 

• 현재 상황에서 가장 좋은 것만 고르는 방법
• 최소한의 아이디어를 떠올릴 수 있는 능력 필요
• 정당성 분석 중요 : 단순히 좋아 보이는 것을 반복선택해도 최적의 해를 구할 수 있는지 검토

 

 

구현

 

• 생각한 알고리즘을 소스코드로 바꾸는 과정
• 코테에서는 풀이를 떠올리기 쉽지만 소스코드로 옮기기 어려운 문제를 말한다

1. 알고리즘은 간단하지만 코드는 지나치게 긴 문제
2. 실수 연산을 다루고 특정 소수점 자리까지 출력해야 하는 문제
3. 문자열을 특정한 기준에 따라서 끊어 처리하는 문제
4. 적절한 라이브러리를 찾아서 사용해야 하는 문제

• 일반적으로 알고리즘 문제의 2차원 공간은 행렬(Matrix)를 의미
• 완전 탐색 문제에서 2차원 공간에서의 방향 벡터 자주 활용