알고리즘

[이코테] 구현

구현 코딩 테스트에서 구현이란 '머리속에 있는 알고리즘을 소스코드로 바꾸는 과정' 문제 해결 분야에서 구현 유형의 문제는 '풀이는 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제'를 의미 문제가 구현하기 어려운 문제는 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제, 특정 소수점 자리까지 출력해야 하는 문제, 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야(파싱) 하는 문제, 적절한 라이브러리를 찾아서 사용해야 하는 문제 등이 있음 [이코테] 책에선 완전 탐색, 시뮬레이션 유형을 모두 '구현' 유형으로 묶어서 다룸. 완전탐색은 모든 경우의 수를 주저 없이 다 계산하는 해결 방법을 의미, 시뮬레이션은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형..

[이코테] 그리디 알고리즘

그리디 알고리즘 (탐욕법) 어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘 현재 상황에서 지금 당장 좋은 것만 고르는 방법 기준에 따라 좋은 것을 선택하는 알고리즘으로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 제시함 [ 예제 3-1 ] 거스름돈 당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원 일 때 거슬러 줘야할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10배수이다. 문제 접근 '가장 큰 화폐 단위부터' 돈을 거슬러 주는 것이 아이디어의 핵심 예를 들어 N원을 거슬러 준다고 할 때, 500원으로..