알고리즘/그리디
-
백준 2437번 : 저울 - 파이썬 (python)알고리즘/그리디 2021. 4. 3. 18:21
www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net - 유사 문제 ssssol.tistory.com/50?category=956078 그리디 알고리즘 : 곱하기 혹은 더하기 - 파이썬 (python) - 입력 조건 첫째 줄에 여러 개의 숫자로 구성된 하나의 문자열 S가 주어집니다. (1= x (=1) 이므로 target = target + x = 1 + 1 = 2 ② target (=2) >= x (=1) 이므로 target = target + x = 2 + 1 = 3 ③..
-
백준 2217번 : 로프 - 파이썬 (python)알고리즘/그리디 2021. 4. 2. 01:02
www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net * 방법1 - 아이디어 문제가 이해가 안가는데 테스트케이스도 하나밖에 없어서 질문 게시판에서 반례 예시를 참고했다. (1) 입력받은 데이터를 내림차순으로 정렬한다. (2) data[0] / data[0], data[1] / data[0], data[1], data[2] / data[0], data[1], data[2],data[3] / data[0], data[1], data[2], data[3], d..
-
백준 11047번 : 동전 0 - 파이썬 (python)알고리즘/그리디 2021. 4. 1. 23:49
www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net * 방법1 - 아이디어 (1) 입력받은 동전의 가치를 내림차순으로 정렬한다. (2) 가치의 합 K 보다 작거나 같은 값의 인덱스를 찾는다. (3) K를 coin[i] (가치의 합 K 보다 작거나 같은 값)으로 나눈 몫을 result에 더한다. (4) K 값을 K - ((k // coin[i]) * coin[i]) 로 변경한다. - 테스트케이스 1 ..
-
백준 2839번 : 설탕 배달 - 파이썬 (python)알고리즘/그리디 2021. 3. 30. 00:55
www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net * 방법 1 아이디어: N을 5로 나누어 5kg 설탕의 최대 수를 계산하고 나머지 ( N - 5kg 설탕 수 * 5) 이 3으로 나누어 떨어지는지 확인한다. 나누어 떨어지지 않으면 5kg 설탕의 수를 1만큼 줄이고 과정을 반복한다. 5kg 설탕 수가 -1이 되면 이는 만들 수 없는 설탕의 무게이므로 -1을 출력한다. n = int(input()) # 배달해야 하는 설탕의 무게 result = 0 count3 = 0 # 3..
-
백준 4889번 : 안정적인 문자열 - 파이썬 (python)알고리즘/그리디 2021. 3. 25. 23:47
www.acmicpc.net/problem/4889 4889번: 안정적인 문자열 입력은 여러 개의 데이터 세트로 이루어져 있다. 각 데이터 세트는 한 줄로 이루어져 있다. 줄에는 여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 문자열의 길이가 2000을 넘는 경우 www.acmicpc.net * 방법1 → X 아이디어: '{' 가 있으면 다음에 '}' 가 존재하는 것이 최소값이라고 가정한다. 0부터 시작해서 짝수 인덱스가 '{' 가 아니면 result 값을 1 증가시키고 홀수 인덱스가 '}' 가 아니면 result 값을 1 증가시키는 방법을 처음 생각했다. ⑴ }{ 인 경우 : 인덱스 0번의 경우 {가 아니므로 result+1 인덱스 1번의 경우 }가 아니므로 result+1 ⑵ {}{}인 경우..
-
백준 16953번 : A → B - 파이썬 (python)알고리즘/그리디 2021. 3. 25. 20:34
www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net * 아이디어 B에서 A로 가는 방법을 생각한다. 2 → 4 → 8 → 81 → 162 의 경우 162를 2로 나누었을 때 나머지가 0이다. 나머지가 0인 경우 b를 2로 나누고 그 값을 b에 저장하고 result += 1을 수행한다. (문제에 따라 result의 초기값은 1) 81을 2로 나눈 경우 나머지는 1이다. 나머지가 1이면 81를 10으로 나눈 몫인 8을 b에 저장하고 result += 1을 수행한다. 8을 2로 나누면 나머지가 0이므로 8을 2로 나눈 값을 b에 저장하고 result += 1을 수행한다. 4 (= 8//2) ..
-
그리디 알고리즘 : 무지의 먹방 라이브 - 파이썬 (python)알고리즘/그리디 2021. 3. 23. 23:14
programmers.co.kr/learn/courses/30/lessons/42891 코딩테스트 연습 - 무지의 먹방 라이브 programmers.co.kr * 힙 설명 - 힙 자료구조는 우선순위 큐를 구현하기 위하여 사용하는 자료구조 중 하나 - 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다는 점이 특징 자료구조 추출되는 데이터 스택(Stack) 가장 나중에 삽입된 데이터 큐(Queue) 가장 먼저 삽입된 데이터 우선순위 큐(Priority Queue) 가장 우선순위가 높은 데이터 - 우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 떄 사용 ex) 여러 개의 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건 데이터부터 꺼내서 확인해야 하는 경우 - 대부분의 프로그래밍 언어에서..