알고리즘/그리디
-
그리디 알고리즘 : 문자열 뒤집기 - 파이썬 (python)알고리즘/그리디 2021. 3. 20. 17:50
- 입력 조건 첫째 줄에 0과 1로만 이루어진 문자열 S가 주어집니다. S의 길이는 100만보다 작습니다. - 출력 조건 첫째 줄에 다솜이가 해야 하는 행동의 최소 횟수를 출력합니다. 테스트케이스) 0001100 -> 1 * 방법1 아이디어: 전부 0으로 바꾸는 경우와 전부 1로 바꾸는 경우 중에서 더 적은 횟수를 가지는 경우를 계산한다. 예를 들어 문자열이 "0001100"이라고 가정하면 '모두 0으로 바꾸는 경우'의 횟수는 1이고 '모두 1으로 바꾸는 경우'의 횟수는 2이다. 두 값 중 적은 횟수인 1을 출력하면 된다. data = input() count0 = 0 #전부 0으로 바꾸는 경우 count1 = 0 #전부 1로 바꾸는 경우 #첫 번째 원소에 대해서 처리 if data[0] == '1': ..
-
그리디 알고리즘 : 곱하기 혹은 더하기 - 파이썬 (python)알고리즘/그리디 2021. 3. 20. 15:04
- 입력 조건 첫째 줄에 여러 개의 숫자로 구성된 하나의 문자열 S가 주어집니다. (1 210 * 방법1 아이디어: 숫자를 사용자로부터 입력받아 리스트로 변경한다. 초기 result 값을 0으로 설정하고 result 값이 0이거나 i 값이 0 또는 1이면 덧셈 연산을 수행한다. (어떤 숫자에 0이나 1을 곱한 값보다 0이나 1을 더한 값이 더 크기 때문) 이 경우가 아니라면 곱셈의 결과가 더 크기 때문에 곱셈을 수행한다. s = list(input()) # s = input() 도 가능 result = 0 for i in s: if result == 0: result += int(i) elif int(i) == 1: result += int(i) elif int(i) == 0: result += int(..
-
그리디 알고리즘 : 모험가 길드 - 파이썬 (python)알고리즘/그리디 2021. 3. 17. 17:26
* 방법1 (내림차순 정렬) → 오답 아이디어: 카드를 큰 수 부터 정렬한 후 그 숫자만큼씩 묶으면 된다고 생각했다. 예를 들어 N이 5이고 공포도가 2 3 1 2 2인 경우, 2 3 1 2 2를 내림차순으로 정렬하고 -> 3 2 2 2 1 3 2 2 / 2 1 3 2 2 를 그룹1로 묶어주고 2 1 을 그룹2로 묶어준다. 그룹1은 그룹 1에서 가장 큰 수인 3만큼 묶어주고 그룹2는 그룹 1을 제외한 리스트에서 가장 큰 수인 2만큼 묶어주었다. 직접 풀이한 방식이며 돌려본 테스트 케이스로는 방법2와 결과값이 모두 동일하게 나왔다. (수정) N=6이고 공포도가 4 3 3 3 3 2 인 경우 내림차순 정렬 4 3 3 3 / 3 2 -> result는 1인데 오름차순 정렬 2 3 / 3 3 3 / 4 -> r..