Learn to share,Share to learn

그리디 알고리즘을 잘 풀기 위한 방법: 문제의 규칙 파악: 문제의 기본 규칙과 조건을 정확히 이해하는 것이 중요합니다. 이 경우에는 각 숫자가 $1$ 이상 $641$ 이하라는 점에 주목해야 합니다. 단순한 해결법부터 시작: 복잡하게 생각하기 전에, 가장 단순한 해결책부터 생각해보세요. 이 경우에는 수를 최대한 크게 만들면서 $641$을 넘지 않도록 하는 것입니다. 지역적 최적화: 각 단계에서 최적의 선택을 하세요. 그리디 알고리즘은 각 단계에서의 지역적 최적화가 전체적으로도 최적의 해답을 이끌어낼 수 있다는 점에 기반합니다. 카운터 예제: 자신의 해결법이 올바른지 확인하기 위해 카운터 예제를 만들어보세요. 이는 당신의 접근 방법이 모든 경우에 대해 올바르게 작동하는지 검증하는 데 도움이 됩니다. 그러니까..

https://www.acmicpc.net/problem/1049 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net 브레인스토밍 N,M = map(int,input().split()) list = [] for _ in range(M): a,b=map(int,input().split()) list.append((a,b)) list.sort(key=lambda x:x[0]) sum_min = list[0] list.sort(key=lambda x:x[1]) each_min = list[1] print(min(s..

1. count 함수를 이용해 원소의 개수 세는법을 알아두자 N = input() changes = [] # 첫 번째 문자를 리스트에 추가 changes.append(N[0]) # 문자열의 두 번째 문자부터 마지막 문자까지 확인 for i in range(1, len(N)): # 이전 문자와 다를 때만 리스트에 추가 if N[i] != N[i-1]: changes.append(N[i]) # 0과 1의 개수 세기 sum_zero = changes.count('0') sum_one = changes.count('1') # 더 적은 개수 출력 print(min(sum_zero, sum_one)) 2. Python에서 * 연산자는 컬렉션의 요소를 개별적으로 출력하는 데 사용된다. 이를 "unpacking"이라고..

https://www.acmicpc.net/problem/10610 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net 브레인스토밍 N = input() sum = 0 for i in range(int(N)): sum += int(N[i]) if (sum % 3 == 0): #3의배수 순서대로 비교후 break else: print(-1) 3의 배수가 아니라 30의 배수인데 잘못작성했다. 실제 코드 N = input() # 3의 배수 확인을 위한 합계 계산 sum_of_digits = sum(int(digit) fo..

부분합.. DP와 비슷한 부분이 있다. memoization을 해서 사용한다는 점에서 닮았다. 기본개념은, 미리 각 값까지의 합을 구한다음 저장하고, 그 값을 이용한다는것이다. https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 문제를 보자. 새로운 리스트를 만들고, 리스트의 원소값에, 해당 인덱스까지의 합을 담는다. 그리고 각 부분합을 구하기 위해서 빼주면되는데, 예를들어 2부터 5까지라 함은, sum(5)-sum(1)이 ..

https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net N = int(input()) A = list(map(int, input().split())) M = int(input()) X = list(map(int, input().split())) 이렇게만 평소에 입력 받아서 몰랐는데, list = [] list.extend(map(int,input().split())) 과 같이 같은경우, extend를 이..

https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 흠.. 사실 중복을 제거해야되는부분을 못보고 리스트로 할생각이였다. 내가 궁금했던건, 리스트를 len(요소)에 따라 sort가 가능한가? 였는데 파이썬은 물론 가능했다. N = int(input()) words = set() for _ in range(N): words.add(input().strip()) # 길이가 짧은 것부터, 길이가 같으면 사전 순으로 정렬 sorted_words ..

알고리즘의 꽃 그래프이론까지 왔다. https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net from collections import deque N, M, V = map(int, input().split()) # 입력 받기 graph = [[] for _ in range(N + 1)] # 그래프를 인접 리스트로 표현 visited = [False] * (N + 1) # 방문 처리 배열 for _ in range(M..