문제) 숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다. 단, 게임의 룰은 아래와 같다. 1. 숫자가 쓰인 카드들이 N x M 형태로 놓여 있다. 이 때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다. 2. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다. 3. 그 다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다. 4. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다. 입력 조건) 1. 첫째 줄에 숫자 카드들이 놓인 행의 개수 N과 열의 개수 M이 공백을 기준으로 하여 각각 자연수로 ..
All Categories
문제) 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만든다. 단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없다. 예를 들어 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때, M=8, K=3 이라면 주어진 규칙대로 가장 큰 수를 만드는 방법은 6+6+6+5+6+6+6+5가 되고 결과는 46이 된다. 입력 조건) 1. 첫째 줄에 N (2≤N≤1,000), M (1≤M≤10,000), K (1≤K≤10,000)의 자연수가 주어지며, 각 자연수는 공백으로 구분한다. 2. 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 단, 각각의 자연수는 1이상 10,000이하의 수로 주어진다. 3. 입력으로 주어지는 K는 ..
그리디 알고리즘은 말 그대로 탐욕적인 알고리즘이라는 뜻을 내포한다. 그리디 알고리즘에서는 현재 상황에서 최적의 방법을 선택한다. 매 순간 가장 좋아보이는 방법을 선택하며 추후에 미칠 영향은 생각하지 않는 것이다. 코딩 테스트에서 만나게 될 그리디 알고리즘의 문제 유형은 사전에 암기하고 있지 않아도 풀 수 있는 가능성이 높은 유형이다. 그리디 알고리즘의 출제 유형은 매우 폭넓으므로 특이 케이스를 제외하고는 단순 암기를 통한 문제 해결은 힘들다. 이 유형은 '창의력'을 요구한다. 문제가 단순히 현재 상황에서 최적의 선택만을 해서 해결 가능한 문제인지를 파악할 수 있어야 한다. 코딩 테스트에서 그리디 알고리즘의 문제는 '가장 큰 (작은) 순서대로' 등과 같은 조건을 은밀히 제시한다. 따라서 그리디 알고리즘은 ..
앞선 포스트에서 시간복잡도와 공간복잡도에 대한 개념에 대해 알아보았다. 복잡도란 언급했듯이 특정한 알고리즘이 계산적으로 얼마나 복잡한지를 나타내는 것이다. 파이썬에서는 실제로 프로그램 수행 시간과 메모리 사용량을 측정할 수 있다. 시간복잡도의 개념에서 프로그램의 수행 시간을 측정하는 것은 해당 알고리즘이 복잡도 측면에서 얼마나 효율적인 지를 측정하는 것과 같다고 할 수 있다. 파이썬에서 수행 시간을 측정하는 소스코드는 아래와 같다. import time start_time = time.time() # 시간 측정 시작 #프로그램 소스코드 end_time = time.time() # 시간 측정 완료 print("time : ", end_time - start_time) # 수행시간 (시작 시간 - 완료 시간..
공간복잡도란 쉽게 말해 소스코드에서 메모리를 사용하는 양이라고 할 수 있다. 공간복잡도 또한 시간복잡도와 마찬가지로 빅오 표기법을 사용하여 표기한다. 즉 O(N), O(log N)등과 같이 표기하는 것이다. 코딩 테스트에서 아래와 같은 문제 조건을 볼 수 있는데 이는 시간복잡도와 공간복잡도에 제한을 두기 위해서이다. '시간 제한 1초, 메모리 제한 128MB' C언어에서 기본자료형의 메모리 크기는 아래와 같다. 자료형 키워드 메모리 크기 문자형 char 1 Bytes 정수형 short 2 Bytes int 4 Bytes long 4 Bytes 부호없는 문자형 unsigned char 1 Bytes 부호없는 정수형 unsigned short 2 Bytes unsigned int 4 Bytes unsigne..
복잡도란 알고리즘의 성능을 나타내는 척도이며 시간복잡도(Time complexity)는 특정한 크기의 입력에 대해 알고리즘이 시간을 얼마나 소요하는지를 나타낸다. 시간복잡도를 표현할 때는 일반적으로 빅오표기법을 사용한다. 알고리즘 문제를 풀 때 단순히 '복잡도'라고 한다면 시간복잡도를 의미한다. 코딩 테스트에서의 시간제한은 시간내에 문제를 풀어야 한다는 제한보다는 작성한 프로그램이 모든 입력을 받아서 이를 실행하고 결과를 출력하는 데 까지 소요되는 시간의 제한을 의미한다. 시간복잡도를 계산할 때 N개의 데이터에 대한 연산의 횟수에 의존하는 경우가 많다. 아래의 예시들을 통해서 시간복잡도를 이해해본다. 더보기 예시1) 위의 예시는 N=5의 데이터의 총합을 계산하는 코드이다. 이 때 연산횟수는 데이터의 개수..
복잡도란 알고리즘의 성능을 나타내는 척도이다. 복잡도에는 시간복잡도(Time Complexity)와 공간복잡도(Space Complexity)가 있다. 시간복잡도는 특정한 크기의 입력에 대해 알고리즘이 시간을 얼마나 소요하는지를 나타내고 공간복잡도는 특정한 크기의 입력에 대해 알고리즘이 메모리를 얼마나 차지하는지를 나타낸다. 일반적으로 적은 시간을 소요하고, 적은 메모리를 차지하는 것이 좋은 알고리즘이라는 것은 자명한 사실이다. 복잡도를 표기하는 방법에는 여러가지 방법이 있다. 빅오(Big-O)표기법 빅오메가(Ω)표기법 빅세타(Θ)표기법 빅오(Big-O)표기법 먼저 빅오(Big-O)표기법이란 쉽게 말해 함수의 상한(upper-bound)만을 고려하는 표기법이다. 즉, 가장 빠르게 증가하는 항만을 고려하는..
