코딩처럼

순열(permutation) 요소 N개 중에 M개를 선택하여 순서에 상관있게 뽑는 경우의 수 카드 뽑기 A, B, C, D, E로 이뤄진 5장의 카드 순서를 생각하며 3장을 선택할 때 경우의 수 모든 카드를 1장씩 나열하면서, 나열된 카드가 3장에 도달하면 카드의 나열을 중지한다. 첫 번째 나열하는 카드를 선택하는 방법에는 다섯 가지가 있다. 첫번째 카드를 나열하고 난 다음, 두 번째 카드를 선택하는 방법에는 네 가지가 있다. 두번째 카드를 나열하고 난 다음, 세 번째 카드를 선택하는 방법에는 세 가지가 있다. 따라서 5 X 4 X 3 = 60 가지의 방법이 있다. 이렇게 n개 중에서 일부만을 선택하여 나열하는 것을 순열이라고 한다. 순열은 순서를 지키며 나열해야 한다. 5장에서 3장을 선택하는 모든 순..

탐욕 알고리즘(Greedy Algorithm)이란? 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다. 탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법이다. 탐욕 알고리즘은 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 탐욕 알고리즘으로 문제를 해결하는 방법 선택 절차 (Selection Procedure) : 현재 상태에서의 최적의 해답을 선택한다. 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사한다. 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로..

시간 복잡도 문제를 해결하기 위해 알고리즘의 로직을 코드로 구현할 때 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가를 의미한다. 시간 복잡도 표기법 Big - O (빅 - 오) Big - Ω (빅 - 오메가) Big - θ (빅 - 세타) 위 세 가지 표기법은 각각 최악, 최선, 평균의 경우에 대하여 나타내는 방법이다. 이 중 Big - O 표기법이 가장 자주 사용된다. Big - O 표기법은 최악의 경우를 고려하기 때문에 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있다. O(1) Constant complexity라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않는다. 입력값의 크기와 상관없이, 즉시 출력값을 얻어낼 수 있다는 의미이다. pu..