728x90 Algorithm/Greedy7 [이것이 코딩 테스트다] 만들 수 없는 금액 - Python 개인적으로 지금의 나에게 좀 어려웠다. (어려웠다기보다는 어떻게 풀어야 하는지를 모르곘다는게 맞는거일수도..) 이문제를 어려워하면 아직 그리디 문제를 많이 접하지 않는거라고 하는데.. 그런거 같다. 이 문제는 target을 1로 두고 target이 입력값을 정렬했을때 첫번째 부터 시작해서 모든 값들과 비교를 한다 만약 target값이 작으면 바로 반복문을 끝낸 후에 target을 출력하면 된다. 만약 target이 크다면 해당 값에 비교한 리스트의 값을 더해준다. (target은 해당 값 -1까지 만들 수 있다는 말이다) 1,2,3 입력값이 주어졌을때 1 2 3 4 ( 1 + 3) 5 ( 2 + 3) 6 ( 1 + 2 + 3) 까지 만들 수 있다. 이때 target 값은 처음은 항상 1이고 이후 1+1.. 2023. 8. 24. [이것이 코딩 테스트다] 문자열 뒤집기 - Python 이 문제같은 경우 나는 값이 0에서 1로 변하든 1 에서 0으로 변하든 몇번 변하는지 횟수를 알아낸 다음 그 횟수에 + 1 한 후에 2로 나눠서 답을 구했다. 왜 위처럼 생각을 했냐면, 같은 숫자들이 반복해있는 묶음들의 개수를 구한다. 이 묶음의 개수를 구하려면 변하는 지점마다 +1을 해줘야 하고 마지막 으로 +1을 해야지 마지막으로 변하고 이후 끝나는 지점의 묶음의 개수도 구할 수 있다. s = input() result = 0 com_val = s[0] cnt = 0 for i in range(1,len(s)): if com_val != s[i]: cnt += 1 com_val = s[i] # print(cnt) cnt = cnt + 1 result = cnt // 2 print(result) 내가 .. 2023. 8. 24. [이것이 코딩 테스트다]곱하기 혹은 더하기 일단 result라는 변수에 문자열 맨 앞글자를 대입한다(대입할때 문자열이니까 다시 int로 변환해서 대입한다) 그 후에 반목문을 이용해서 입력받은 문자열의 2번째 인덱스부터 확인을 해야한다. 잘 생각해보면 다음값이 0이면 곱했을경우 0이 되니까 곱하면 안된다 무조건 +를 해야한다. 또한 1 일경우에도 곱했을경우 자기 자신이 나오므로 + 하는 경우가 더 값이 크다. 그러므로 해당 값들이 0으로 적혀있는지 1로 적혀 있는지 확인한다. 또한 처음 result에 넣은 값 역시 확인을 안했으므로 한번은 확인을 해줘야 한다 0 or 1일경우 result에 더하고 아닌경우 result에 곱해서 그 값을 다시 result 에 저장한다. s = input() result = int(s[0]) for i in range.. 2023. 8. 24. [이것이 코딩 테스트다] 모험가 길드 일단 리스트를 입력받았을때 정렬을 시켜야 한다 오름차순으로 정렬하면 맨 마지막 값이 가장 큰 값이 나오는데 이 값을 pop 한 후 변수에 저장하고그 값만큼 popleft를 한다(deque를 이용했다) deque 길이가 0이 될때 까지 이 행위를 반복한다. from collections import deque as dq n = int(input()) L = list(map(int,input().split())) L.sort() D=dq(L) result = 0 while len(D) != 0: a = L.pop() for i in range(a): if len(D) == 0: break D.popleft() result += 1 print(result) 교재는 다른 방식으로 풀었는데 교재 풀이가 더 나은거.. 2023. 8. 24. 창고 정리(그리디) - python 창고에 상자가 가로방향으로 일렬로 쌓여 있습니다. 만약 가로의 길이가 7이라면 1열은 높이가 6으로 6개의 상자가 쌓여 있고, 2열은 3개의 상자, 3열은 9개의 상자가 쌓여 있 으며 높이는 9라고 읽는다. 창고 높이 조정은 가장 높은 곳에 상자를 가장 낮은 곳으로 이동하는 것을 말한다. 가장 높은 곳이나 가장 낮은 곳이 여러곳이면 그 중 아무거나 선택하면 된다. 위에 그림을 1회 높이 조정을 하면 다음과 같아진다. 창고의 가로 길이와 각 열의 상자 높이가 주어집니다. m회의 높이 조정을 한 후 가장 높은 곳 과 가장 낮은 곳의 차이를 출력하는 프로그램을 작성하세요. ▣ 입력설명 첫 번째 줄에 창고 가로의 길이인 자연수 L(1 2023. 7. 29. 씨름 선수(그리디) - python 현수는 씨름 감독입니다. 현수는 씨름 선수를 선발공고를 냈고, N명의 지원자가 지원을 했습 니다. 현수는 각 지원자의 키와 몸무게 정보를 알고 있습니다. 현수는 씨름 선수 선발 원칙을 다음과 같이 정했습니다. “다른 모든 지원자와 일대일 비교하여 키와 몸무게 중 적어도 하나는 크거나, 무거운 지원자 만 뽑기로 했습니다.” 만약 A라는 지원자보다 키도 크고 몸무게도 무거운 지원자가 존재한다면 A지원자는 탈락입니다. ▣ 입력설명 첫째 줄에 지원자의 수 N(5 2023. 7. 29. 회의실 배전(그리디) - python 한 개의 회의실이 있는데 이를 사용하고자 하는 n개의 회의들에 대하여 회의실 사용표를 만들 려고 한다. 각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하 면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중 단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. ▣ 입력설명 첫째 줄에 회의의 수 n(1 2023. 7. 29. 이전 1 다음 728x90
