알고리즘/이것이 코딩테스트다

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 프로그래머스에 있는 문제다. 시간 제한이 1초이므로 2,000만 번 정도의 연산이 가능하다고 생각할 수 있다. 주어진 food_times 리스트의 길이가 정확성 테스트의 경우 1 이상 2,000 이하이고, 효율성 테스트의 경우 1이상 200,000 이하이다. 정확성 테스트만 보고 O(N^2)도 가능하겠다고 생각했지만 효율성 테스트를 보고 O(NlogN)이상은 안되겠다는 생각이 들었다. 그리고 K의 범위도 정확성 테스트의 경우 1 이상 2,000,000 이하이고 효율성 테스트의 경우 2 X 10^13개였다. 그..

주어진 볼링공의 개수(N)이 1,000 이하고, 시간 제한은 1초였다. 그러므로 O(N^2)의 시간복잡도로 충분히 풀 수 있다. 그래서 처음에는 단순하게 1번~N번의 볼링공까지 for문을 돌면서 자기 다음 번호 ~ N번까지의 공들을 확인해서 자기 자신과 같은 값 빼고 +1을 해주면 답이 나온다고 생각했다. 좀 더 생각해보니 더 간단한 로직이 있었다. 각 볼링공 무게를 인덱스로 하는 리스트를 만들어서 볼링공 무게마다 볼링공이 몇개 있는지 저장한다. 그 후 특정 볼링공 무게에 해당하는 볼링공의 개수가 0이 아닌 경우, 특정 볼링공 무게의 볼링공 개수 개수 * (전체 볼링공 개수 - 특정 볼링공 무게의 볼링공 개수) 를 무게마다 구해서 더해준 다음에 2로 나눠주면 답이 나온다. 내 풀이 # Q_05_볼링공 고..

동빈이는 N개의 동전을 가지고 있다. 이 때 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성해라. 예를 들어 N=5이고, 각 동전이 각각 3, 2, 1, 1, 9원이라고 하면 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 8원이다. 문제의 시간제한이 1초이고, 동전의 개수가 1000개 이하이므로 O(N^2)도 되겠구나 라는 생각을 했다. 그리고 동전의 단위도 1,000,000이하의 자연수라서 동전의 단위로 반복문을 돈다면 O(NlogN)도 가능하겠다는 생각을 했다. 처음에는 동전들을 오름차순 정렬해서 1부터 가장 큰 동전의 값까지 반복문을 돌려서 1 ~ 동전의 최댓값까지 동전을 만들 수 있는 경우를 확인해보려고 했다. 하지만 그럴 경우 동전의 단위가 서로 나..

1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 입력받는 문자열 s의 길이가 100만보다 작은데 시간 제한은 2초였다. 2초라면 파이썬의 경우 약 4,000만 번의 계산이 가능한 시간이므로 O(NlogN)의 시간까지도 가능하다고 생각했다. 물론 O(N)도 가능하다. 그러므로 그냥 반복문을 통해 문자열을 돌면서 뒤집는 횟수의 최솟값을 구하면 된다고 생각했다. 그래서 단순히 생각해서 1을 뒤집는 경우와 0을 뒤집는 경우 모두 for문을 돌려서 두 결과값 중 작은 값이 답이 된다. for문을 2번 돌리는 것이라서 ..

각 자리가 숫자(0부터 9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 숫자를 확인하여 숫자 사이에 곱하기 혹은 더하기 연산자를 넣어서 만들어질 수 있는 가장 큰 수를 구하는 프로그램이다. 문제를 읽어봤을 때, 바로 0이 떠올랐다. 어떤 수에 0을 곱하면 0이 되니까 0이 나오는 경우 무조건 더해야 한다는 점이다. 그리고 이 문제에서는 일반적인 연산 순서와는 달리, 모든 연산을 왼쪽에서부터 순서대로 한다고 가정한다. 그러므로 입력받는 문자열 S를 앞에서부터 확인하면서 이전 수까지 연산한 값에다가 곱하기를 한 값 혹은 더하기를 한 값 중 더 큰 값을 현재까지의 연산값으로 바꿔주면 된다. 그러므로 현재 가장 이상적인 것을 고르므로 그리디 알고리즘이라고 할 수 있다. 내 코드 # Q_02_곱하기 혹은 더..

처음에 문제를 잘못 읽고 여행을 떠날 수 있는 그룹 수의 최솟값을 구했다가 틀렸다. 알고보니 최댓값을 구해야 하는 문제였다. 일단 입력받은 공포도 값 리스트를 내림차순으로 정렬한 후, 큰 숫자의 공포도를 가진 리스트부터 먼저 그룹을 만들어줬다. 그리고 그룹 하나를 만든 후에는 start를 높여서 그룹에 포함된 공포도들을 제외한 리스트의 값들 중의 최댓값을 통해 또 다시 그룹을 만들어줬다. 만약, start값이 end값보다 커지는 경우 더 이상의 그룹 생성은 불가능하다고 할 수 있다. 단, 남은 공포도 값 중 1이 있는 경우에는 혼자 그룹 생성이 가능하므로 남은 리스트 중 1의 개수를 세줘서 그룹 수에 더해줬다. 내 풀이 # Q_01_모험가 길드 n = int(input()) # 모험가의 수 arr = l..