동빈이는 N개의 동전을 가지고 있다. 이 때 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성해라. 예를 들어 N=5이고, 각 동전이 각각 3, 2, 1, 1, 9원이라고 하면 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 8원이다. 문제의 시간제한이 1초이고, 동전의 개수가 1000개 이하이므로 O(N^2)도 되겠구나 라는 생각을 했다. 그리고 동전의 단위도 1,000,000이하의 자연수라서 동전의 단위로 반복문을 돈다면 O(NlogN)도 가능하겠다는 생각을 했다. 처음에는 동전들을 오름차순 정렬해서 1부터 가장 큰 동전의 값까지 반복문을 돌려서 1 ~ 동전의 최댓값까지 동전을 만들 수 있는 경우를 확인해보려고 했다. 하지만 그럴 경우 동전의 단위가 서로 나..
알고리즘
03_문자열 뒤집기 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 happenundo.tistory.com
1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 입력받는 문자열 s의 길이가 100만보다 작은데 시간 제한은 2초였다. 2초라면 파이썬의 경우 약 4,000만 번의 계산이 가능한 시간이므로 O(NlogN)의 시간까지도 가능하다고 생각했다. 물론 O(N)도 가능하다. 그러므로 그냥 반복문을 통해 문자열을 돌면서 뒤집는 횟수의 최솟값을 구하면 된다고 생각했다. 그래서 단순히 생각해서 1을 뒤집는 경우와 0을 뒤집는 경우 모두 for문을 돌려서 두 결과값 중 작은 값이 답이 된다. for문을 2번 돌리는 것이라서 ..
02_곱하기 혹은 더하기 각 자리가 숫자(0부터 9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 숫자를 확인하여 숫자 사이에 곱하기 혹은 더하기 연산자를 넣어서 만들어질 수 있는 가장 큰 수를 구하는 프로그램이 happenundo.tistory.com 위 문제를 풀다가 잠시 헷갈렸던 점을 정리해보자. 위 문제에서 import.sys input = sys.stdin.readline 을 통해서 입력을 받았다. 이렇게 입력을 받을 경우 한 줄 모두 입력받으므로 numbers라는 변수 끝에 개행 문자까지 들어가게 된다. 예를 들어, '33445'를 입력하면 '33445\n'이 들어간다. input().rstrip()을 통해 개행 문자를 없앨 수 있다. rstrip은 문자열의 오른쪽 공백을 삭제하고, lst..
각 자리가 숫자(0부터 9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 숫자를 확인하여 숫자 사이에 곱하기 혹은 더하기 연산자를 넣어서 만들어질 수 있는 가장 큰 수를 구하는 프로그램이다. 문제를 읽어봤을 때, 바로 0이 떠올랐다. 어떤 수에 0을 곱하면 0이 되니까 0이 나오는 경우 무조건 더해야 한다는 점이다. 그리고 이 문제에서는 일반적인 연산 순서와는 달리, 모든 연산을 왼쪽에서부터 순서대로 한다고 가정한다. 그러므로 입력받는 문자열 S를 앞에서부터 확인하면서 이전 수까지 연산한 값에다가 곱하기를 한 값 혹은 더하기를 한 값 중 더 큰 값을 현재까지의 연산값으로 바꿔주면 된다. 그러므로 현재 가장 이상적인 것을 고르므로 그리디 알고리즘이라고 할 수 있다. 내 코드 # Q_02_곱하기 혹은 더..
처음에 문제를 잘못 읽고 여행을 떠날 수 있는 그룹 수의 최솟값을 구했다가 틀렸다. 알고보니 최댓값을 구해야 하는 문제였다. 일단 입력받은 공포도 값 리스트를 내림차순으로 정렬한 후, 큰 숫자의 공포도를 가진 리스트부터 먼저 그룹을 만들어줬다. 그리고 그룹 하나를 만든 후에는 start를 높여서 그룹에 포함된 공포도들을 제외한 리스트의 값들 중의 최댓값을 통해 또 다시 그룹을 만들어줬다. 만약, start값이 end값보다 커지는 경우 더 이상의 그룹 생성은 불가능하다고 할 수 있다. 단, 남은 공포도 값 중 1이 있는 경우에는 혼자 그룹 생성이 가능하므로 남은 리스트 중 1의 개수를 세줘서 그룹 수에 더해줬다. 내 풀이 # Q_01_모험가 길드 n = int(input()) # 모험가의 수 arr = l..
1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 파이썬 itertools 라이브러리의 combinations를 써서 풀었다. 통과는 했으나 4중 for문까지 들어가므로 성능이 별로라고 생각한다. 자음이 2개 이상 들어가야 한다는 조건을 빼먹어서 틀렸다. 고치니 바로 정답! 내 풀이 # 기타 알고리즘_B_2_암호 만들기 import itertools l,c = map(int, input().split()) temp_list = list(input().split()) # 알파벳 종류 ㅣㅇㅂ력받기 consonants =..
파이썬 (Python) - 깊은 복사 (Deep Copy) 파이썬 (Python) - 깊은 복사 (Deep Copy) 알고리즘을 풀다 보면 원본배열의 보존을 위해 배열을 복사할 필요를 느낄때가 많다. 객체를 무작정 복사해서 사용하면 원본 객체가 핸들링되어 데이터가 변 crackerjacks.tistory.com 이해하기 쉬운 개념이지만, 놓칠 경우 큰 문제가 발생할 수 있는 개념이다.
