1일1코딩

알고리즘/그리디

[그리디] 1이 될 때까지

난이도 ●○○ / 시간 제한 1초 / 메모리제한 128MB / 기출 2018 E 기업 알고리즘 대회 어떤 수 N이 1이 될때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두 번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있다. N에서 1을 뺀다. N을 K로 나눈다. 예를 들어, N이 17, K가 4라고 가정하자. 이 때 1번의 과정을 한 번 수행하면 N은 16이 된다. 이후 2번의 과정을 두 번 수행하면 N은 1이 된다. 결과적으로 전체 과정을 실행한 횟수는 3이 된다. 이는 N을 1로 만드는 최소 횟수이다. N과 K가 주어질 때 N이 1이 될 때 까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하시오. 입력 조건 첫째 줄에 N 과 K가 ..

알고리즘/그리디

[그리디] 숫자 카드 게임

난이도 ●○○ / 시간 제한 1초 / 메모리제한 128MB / 기출 2019 국가 교육기관 코딩 테스트 숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다. 단, 게임의 룰을 지키며 카드를 뽑아야 하고 룰은 다음과 같다. 숫자가 쓰인 카드들이 N x M 형태로 놓여있다. 이때 N은 행의 개수를 의미하여 M은 열의 개수를 의미한다. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다. 그 다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다. 따라서, 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다. 여기서 카드를..

알고리즘/그리디

[그리디] 큰 수의 법칙

난이도 ●○○ / 풀이시간 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번까지 실제 연산의 횟수..