언젠가 꽃이 될 개발자

fun main() { val n = 5 val coins = mutableListOf(3, 2, 1, 1, 9) coins.sort() var target = 1 for (i in 0.. target) break target += coins[i] } println("target = $target")} 처음에는 완전 탐색으로 접근해야하나? 라는 생각이 들었다.(물론 책 카테고리가 그리디 알고리즘이지만 내가 문제를 보고 제일 먼저 드는 생각은 완전 탐색이었다.)target이 1씩 증가하면서 최솟값을 찾아야겠다는 생각 때문에 근데 완전 탐색의 경우N개의 동전으로 만들 수 있는 모든 부분집합을 고려하면 부분집합 개수는 2^N 개N이 최대 1,000개면 최악의 ..

🤔 복잡도(Complexity) ✔ 알고리즘의 성능을 나타내는 척도 이름 특징 시간 복잡도 알고리즘을 위해 필요한 연산 횟수 공간 복잡도 알고리즘을 위해 필요한 메모리 양 🤔 빅오 표기법(Big-O) 가장 빠르게 증가하는 항만을 고려하는 표기법 빅오 표기법 명칭 $$O(1)$$ 상수 시간(Constant time) $$O(logN)$$ 로그 시간(Log time) $$O(N)$$ 선형 시간 $$O(NlogN)$$ 로그 선형 시간 $$O(n^2)$$ 이차 시간 $$O(n^3)$$ 삼차 시간 $$O(2^n)$$ 지수 시간

나동빈 저자의 '이것이 취업을 위한 코딩 테스트다' 책의 내용을 미래의 코테 직전의 내가 참고할 수 있는 요약본으로 정리하려 한다. 그 첫 번째 오늘은 '그리디 알고리즘'에 대해 공부하자. 바로 시작해보자. 그리디 알고리즘이란? 그리디 알고리즘은 '탐욕법'이라는 말로 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'을 의미한다. 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 그리디 알고리즘은 기준에 따라 좋은 것을 선태하는 알고리즘이므로 문제에서 '가장 큰 순서대로' 등의 기준을 티나지 않게 제시해준다! 대체로 정렬과 같이 사용하였을 때 만족시킬 수 있으므로 정렬 알고리즘과 짝을 이뤄 출제된다! 그럼 이제 그리디 알고리즘에 대해 학습했으니 다음 ..