그리디 알고리즘 연습하기2 -잃어버린 괄호-

1. 문제 1541번: 잃어버린 괄호 (acmicpc.net) 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 수식에 괄호를 쳐서 결과를 최소로 만드는 문제 2. 풀이 수식에 +,-만 나온다는 점을 생각하면.. 이 수식이 최소가 될려면?? +를 먼저 계산해서, 각 항을 최대로 만들어줘야한다. 그래야 -에 의해 최소가 되겠지 그래서 -로 수식을 split해주고... split된 리스트를 순회해서... 각 원소를 int()로 바꿔본다. int()로 바꿀때 에러가 나거나 나지 않거나 둘중 하나다. 에러가 나지..

• format_list_bulleted 그리디 알고리즘
• · 2023. 1. 19.
• textsms

탐욕적으로 생각하기 연습 -소인수분해 말고 인수분해하기-

1. 문제 2777번: 숫자 놀이 (acmicpc.net) 2777번: 숫자 놀이 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 양의 정수 N이 주어진다. (1 7: print(-1) continue else: prime[n] += 1 a,b = divmod(prime[2],3) if b == 2: b = 1 elif a == 2 and b == 0: a = 1 c,d = divmod(prime[3],2) answer = a+b+c+d+prime[5]+prime[7] print(answer) 2와 3의 경우에 2를 3번 곱한 8까지 압축시켜야하고 3의 경우 2번 곱한 9까지 압축시켜야하고 5,7은 그대로 두면 되고 근데 또 압축이 가능한 경우가 2*..

• format_list_bulleted 그리디 알고리즘
• · 2023. 1. 19.
• textsms

union find 응용문제 풀어보면서 분리집합 개념 재활하기

1. 문제 16562번: 친구비 (acmicpc.net) 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10, www.acmicpc.net 2. 풀이 어렵게 생각하지 말고.. 먼저 union find 함수를 작성하자 먼저 parent를 찾는 find함수 def find_parent(x,parent): if x != parent[x]: parent[x] = find_parent(parent[x],parent) return parent[x] 다음 union을 수행하는 함수 def ..

• format_list_bulleted 그래프 이론 정복기
• · 2023. 1. 9.
• textsms

다익스트라 알고리즘 응용하기 - 특정 조건에 맞는 길이를 가진 최단 경로를 구하는 방법

1. 문제 8347번: Bug (acmicpc.net) 8347번: Bug The first line of input contains two integers n and m (2 ≤ n ≤ 200 000, 0 ≤ m ≤ 500 000), separated by a single space and denoting the number of cities and the number of roads in Byteland. The cities are numbered from 1 to n; Bytetown has number www.acmicpc.net 2. 풀이 목적지까지 최단경로를 구해야하는데 문제는 홀수길이를 가지는 최단 경로를 구해야한다 그냥 사용하면 2를 답을 내는데.. 문제에서 원하는건 7로 가는 경로이다 쉬..

• format_list_bulleted 최단거리 알고리즘
• · 2023. 1. 8.
• textsms

탐욕적인 사람 되기 -정수 a를 k로 만들기 문제-

1. 문제 25418번: 정수 a를 k로 만들기 (acmicpc.net) 25418번: 정수 a를 k로 만들기 7(A), 8(연산 1), 9(연산 1), 18(연산 2), 19(연산 1), 38(연산 2), 76(연산 2), 77(연산 1)이 최소 연산이므로 정답은 7이다. www.acmicpc.net 정수 a에 1을 더하거나 2를 곱해서 k를 만들때, 연산 횟수의 최솟값을 구하는 문제 2. 풀이1(BFS) 이 문제의 기본은 BFS로 푸는 것이다 정수 a에서 시작해서, delta 배열은 1,2가 있고 1이 나오면 a + 1에 가서 범위를 벗어난건지, 이미 방문했는지 검사 2가 나오면 2a에 가서 범위를 벗어난건지, 이미 방문했는지 검사 from collections import deque def bfs(..

• format_list_bulleted 그리디 알고리즘
• · 2023. 1. 5.
• textsms

탐욕적으로 생각하기 연습 -팩토리얼 분해-

1. 문제 2057번: 팩토리얼 분해 (acmicpc.net) 2057번: 팩토리얼 분해 음 아닌 정수 N이 주어졌을 때, 이 수를 서로 다른 정수 M(M ≥ 1)개의 팩토리얼의 합으로 나타낼 수 있는지 알아내는 프로그램을 작성하시오. 예를 들어 2=0!+1!로 나타낼 수 있지만, 5는 이와 같은 www.acmicpc.net 주어진 정수가 여러개의 팩토리얼의 합으로 나뉠 수 있는지 검사하는 문제 2. 풀이1 실버 5인데 왤케 어렵냐... 그리디 알고리즘이 확실히 경험이 없긴한가봐 내 해법은 일단.. 어떤 정수 N을 팩토리얼로 분해한다고 하면... 당연히 팩토리얼 값은 N보다 작아야 할 것이다 그래서 N보다 작은 팩토리얼을 일단 모두 구해놓는다 from sys import stdin n = int(stdi..

• format_list_bulleted 그리디 알고리즘
• · 2023. 1. 5.
• textsms