알고리즘/그리디
[그리디] 큰 수의 법칙
난이도 ●○○ / 풀이시간 30분 / 시간 제한 1초 / 메모리제한 128MB / 기출 2019 국가 교육기관 코딩 테스트 동분이는 본인만의 방식으로 '큰 수의 법칙'을 다르게 사용하고 있다. 동빈이는 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다. 예를 들어 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때 M이 8이고, K가 3이라고 가정하자. 이 경우 특정한 인덱스의 수가 연속해서 세 번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는 6 + 6 + 6 + 5 + 6 + 6+ 6 + 5 인 46이 된다..
알고리즘/그리디
[알고리즘 기초] 그리디
현재 상황에서 지금 당장 좋은 것만 고르는 방법. 매 순간 가장 좋아 보이는 것을 선택하고 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않음. 코테에서 그리디 알고리즘 문제 유형은 사전에 외우고 있지 않아도 풀 수 있는 가능성이 높음. (다익스트라 알고리즘 제외) 따라서 많은 유형을 접해보고 문제를 풀어보며 훈련을 해야 함. 보통 창의력(문제를 풀기위한 최소한의 아이디어를 떠올릴 수 있는 능력)을 요구. 단순히 현재 상황에서 가장 좋아 보이는 것만을 선택해도 문제를 풀 수 있는지를 파악할 수 있어야 함. 기준에 따라 좋은 것을 선택하는 알고리즘 이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해 줌. 대체로 이 기준은 정렬 알고리즘을 사용했을 때 만족시..
알고리즘
[알고리즘 기초] 복잡도
[1] 시간 복잡도 일반적으로 코딩 테스트 환경에서는 O(n^3)을 넘어가면 문제풀이에서 사용하기 어려움. CPU 기반의 개인 컴퓨터나 채점용 컴퓨터에서는 연산 횟수가 10억을 넘어가면 1초 이상의 시간이 소요. N의 크기가 5,000이 넘는다면 족히 10초 이상의 시간이 걸리고 파이썬은 더욱 오래 걸림. 보통 코테의 시간 제한은 1~5초 가량. 따라서 연산횟수가 10억을 넘어가면 오답 판정을 받을 수 있음. N이 1000일 때 연산 횟수 O(N) 1,000 O(NlogN) 10,000 O(N^2) 1,000,000 O(N^3) 1,000,000,000 O(NlogN)인 알고리즘은 시간복잡도가 동일하더라도 내부 로직 및 차수가 낮은 항의 영향에 따라 10,000번에서 100,000번까지 실제 연산의 횟수..
