남남이루의 고군분투 🌳

이코테 : 이것이 취업을 위한 코딩테스트다 책의 예제문제 풀이 문제 배열의 수들을 m번 합해서 가장 큰 수를 만들어야 한다. 다만, 같은 수가 연속으로 k번을 초과해서 더해질 수 없다. 예를 들어 [2,4,5,4,6] 배열에, m = 8, k = 3 이라면 6+6+6+5+6+6+6+5 = 46 이 답이 된다. 인덱스가 다르면 수가 같아도 별도의 횟수로 센다. 문제 조건 1 res 필요 즉, first 숫자는 m을 (k+1)만큼 나눈 몫 x 한 사이클당 최대등장횟수 k 만큼 등장한다. 그리고 딱 떨어지지 않는 숫자 동안은 무조건 first 숫자로 더해줘야하기 때문에 m을 (k+1)로 나눈 나머지에 횟수만큼 first 로 합해준다. 따라서, (first 곱하기 cycle 곱하기 k) + (first 곱하기 ..

이코테 : 이것이 취업을 위한 코딩테스트다 책의 예제문제 풀이 문제 10의 배수로 주어지는 거스름돈을 돌려주려고 할 때, 최소 몇 개의 동전으로 거슬러 줄 수 있는가? 백준의 유사 문제인 11047 동전 포스팅 해설 가장 큰 동전으로 거슬러 줄 수 있는 금액부터 제거해줘야 최소 개수가 보장된다. 딕셔너리를 활용해봤다. 엊그제 해본 dic.items()의 sum도 써봤다. 코드 coins = [500, 100, 50, 10] coins.sort(reverse=True) n = int(input()) # 거스름돈 # 줄 동전의 최소 개수 cnt = 0 dic = {} for c in coins: dic[c] = n//c n -= dic[c]*c # print(n) print(sum(v for i,v in d..

백준 10610번 30의 배수를 찾는 문제(그리디)에서, pycharm과 달리 자꾸만 런타임에러가 났다. pypy, python도 바꾸고, 코드도 바꿔서 돌렸으나 계속 런타임 에러가 났다. import sys input = sys.stdin.readline 을 제거했더니, 정답처리가 되었다. 다른 문제의 경우 input 입력값을 바로 int나 str으로 변환해서 받아서 sys.stdin.readline에서 삽입되는 개행문자로 인한 오류가 생길 일이 없어서 문제가 안 생겼었는데, 이 문제에서는 input 입력값을 그대로 사용하기 때문에 문제가 생겼다. (파이참 터미널에서는 개행문자가 확인되지 않았다.) 따라서, sys.stdin.readline 을 사용하고 싶다면, input().rstrip() 으로 개행..

그리디와 이분탐색 왜 이분 탐색 다음에 그리디 알고리즘이 나왔느냐- 둘다 분할 정복, 재귀함수를 사용한다는 공통점이 있어 결이 비슷하기 때문이다. 그리디란? 그리디 알고리즘의 경우, 가장 좋은 해부터 찾아내고 나머지는 쪼개는 방식으로 진행한다. 밥먹을 때 제일 맛있는 반찬부터 먹는 욕심쟁이를 닮은 알고리즘 이랄까. 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법으로, 이것이 전체로 봤을 때도 최선이길 바라는 알고리즘이다. 따라서 적용할 수 있는 문제의 조건이 조금 까다로운 편이다. 비슷해 보여도 그리디를 쓸 수 있는 문제가 있고, 아닌 게 있다. 예를 들어, 동전을 사용해 어떤 금액을 표현하는 문제는 그리디로 풀리는데, 동전의 단위가 배수-약수관계가 아니면 그리디 알고리즘을 쓸 수 없다...