728x90 Algorithm 썸네일형 리스트형 [백준알고리즘] 2609번: 최대공약수와 최소공배수 -Python [백준알고리즘] 2609번: 최대공약수와 최소공배수 -Python https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를,둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 최대공약수(GCD : Greatest Common Divisor)와 최소공배수(LCM : Least Common Multiple)를 구하는 문제다. 이 문제는 유클리드 호제법을 알고 있으면 쉽게 풀 수 있는 문제이다. 유클리드 호제법은 GCD를 쉽게 구할 수 있는 알고리즘 중의 하나이다. 이 알고리즘은 식을 간결하게 해주는 특징이 있다. 두 수 a와 b (a > b)가 있다고 할 때, a와 b의 최대.. 더보기 [백준알고리즘] 11653번: 소인수분해 -Python [백준알고리즘] 11653번: 소인수분해 -Python https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 소인수 분해 문제이다. 그냥 인수만 구하라고 한다면 2부터 sqrt(N)까지 반복하면서 나누어 떨어지는지 확인을 하면서 리스트에 넣으면 된다. 여기서 적용한다면 for i in range(2, sqrt(N)+1) 일 것이다. 파이썬에서 sqrt()는 math 모듈을 import해야한다. 그런데 그냥 소인수들을 구하라고 했기 때문에 N을 직접 나눠가면서 print 하도록 했다. import sys N = int(sys.stdin.readline()) while N.. 더보기 [백준알고리즘] 5086번: 배수와 약수 -Python [백준알고리즘] 5086번: 배수와 약수 -Python https://www.acmicpc.net/problem/5086 5086번: 배수와 약수 문제 4 × 3 = 12이다. 이 식을 통해 다음과 같은 사실을 알 수 있다. 3은 12의 약수이고, 12는 3의 배수이다. 4도 12의 약수이고, 12는 4의 배수이다. 두 수가 주어졌을 때, 다음 3가지 중 어떤 관계인지 구하는 프로그램을 작성하시오. 첫 번째 숫자가 두 번째 숫자의 약수이다. 첫 번째 숫자가 두 번째 숫자의 배수이다. 첫 번째 숫자가 두 번째 숫자의 약수와 배수 모두 아니다. 입력 입력은 여러 테스트 케이스로 이루어져 있다. 각 테스 www.acmicpc.net 단계별로 문제풀기 수학3의 첫 문제이다. 정수론과 조합론....이라고 한다.... 더보기 [백준알고리즘] 1541번: 잃어버린 괄호 -Python [백준알고리즘] 1541번: 잃어버린 괄호 -Python https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. www.acmicpc.net 단계별로 풀어보기에서 그리디 알고리즘의 마지막 문제이다. 이 문제는 괄호를 '+'와 '-'들 사이에 아무 데나 넣어도 된다는 점이 중요하다. 1+2+3-3+4+5 = 12 이지만 괄호를 다음과 같이 넣으면 결과가 달라진다. 1+2+3-(3+4+5) = -6의 결과가 나온다. 이.. 더보기 [백준알고리즘] 2217번: 로프 -C [백준알고리즘] 2217번: 로프 -C https://www.acmicpc.net/problem/2217 2217번: 로프 N(1≤N≤100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다. 각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 www.acmicpc.net Greedy Algorithm이 DP보다는 역시 생각하기가 쉬운 것 같다. 일단 위 문제를 풀기 위해서.. 더보기 [백준알고리즘] 11399번: ATM -C, Python [백준알고리즘] 11399번: ATM -C, Python https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 그리디 알고리즘의 대표적인 예라고 생각하는 문제이다. 이 문제는 CPU scheduling 기법 중 하나인 SJF(Shortest Job First)을 알고 있다면 쉽게 풀 수 있는 문제이다. 이 문제도 마찬가지로 처리시간이 짧은 순서대로 정렬을 해서 처리를 해주면 된다. 다른 분들은 이 부분을 위해서 시간복잡도가 빠른 퀵 정렬 등을 사용해서 정렬을 해주었지만, 여기서 .. 더보기 [백준알고리즘] 1931번: 회의실배정 -Python [백준알고리즘] 1931번: 회의실배정 -Python https://www.acmicpc.net/problem/1931 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 아랫부분에 새로 푼 방식의 풀이도 추가했다. 이번 문제도 그리디 알고리즘을 이용하는 문제이다. 시작시간과 끝나는 시간이 주어질 때 회의실을 이용할 수 있는 최대 횟수를 찾는 문제이다. 여기서는 문제에 써있는 "단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다." 이 부분이 중요하다. 즉 회의의 시작.. 더보기 [백준알고리즘] 11047번: 동전 0 -Python [백준알고리즘] 11047번: 동전 0 -Python https://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 그리디 알고리즘(탐욕 알고리즘)의 문제이다. 그리디 알고리즘의 경우에는 동적 계획법과 달리 항상 최적의 해를 준다고 보장되지 않는다. 각 Step에서 Decision에 의해서는 Optimization Value를 선택하지만, 전체를 봤을 때에는 Optimization이 보장되지는 .. 더보기 이전 1 ··· 23 24 25 26 27 다음
