알고리즘
[BOJ] 2609 최대공약수와 최소공배수
[BOJ] 2609 최대공약수와 최소공배수
2022.02.07최대공약수는 유클리드 호제법을 이용해서 구한다. 최소공배수는 양쪽이 자신이 가진 약수중 상대가 가지지 않은 약수만을 남긴다음, 최대공약수와 모두 곱한 값이다. 예를 들어, X가 A * C 이고, Y가 B * C 이며, A와 B는 서로소라고 하자. X * Y 는 A * B * C * C 이다. #include int GetGCD(int A, int B) { int Bigger = A > B ? A : B; int Smaller = A > B ? B : A; int Remainder = Bigger % Smaller; if (0 == Remainder) return Smaller; return GetGCD(Smaller, Remainder); } int main() { std::cin.tie(0); std:..
[BOJ] 1037 약수 - 정수론
[BOJ] 1037 약수 - 정수론
2022.02.07어떠한 수의 가장 큰 약수와 가장 작은 약수를 곱한값 이다. 어떠한 수 N이 A * B * C 일때, 약수는 다음과 같다. 1과 N을 제외한 약수는 다음과 같다. A, B, C, A * B, A * C, B * C 가장 작은 약수가 A라고 하자. 그러면 가장 큰 약수는 당연히 가장 작은 약수를 제외한 것을 모두 곱한 B * C이다. 문제에서 모든 약수를 준다. 따라서, 배열을 정렬 한 다음 가장 큰 수와 가장 작은 수를 곱해주면 된다. #include #include #include int N; int main() { std::cin.tie(0); std::cout.tie(0); std::cin.sync_with_stdio(false); std::cout.sync_with_stdio(false); std..
[BOJ] 5086 배수와 약수
[BOJ] 5086 배수와 약수
2022.02.07약수도, 배수도 아니라면 서로소이다. #include int main() { std::cin.tie(0); std::cout.tie(0); std::cin.sync_with_stdio(false); std::cout.sync_with_stdio(false); int A = 0; int B = 0; for (;;) { std::cin >> A; std::cin >> B; if (0 == A || 0 == B) break; if (0 == B % A) { std::cout
[BOJ] 13305 주유소 - 그리디 알고리즘.
[BOJ] 13305 주유소 - 그리디 알고리즘.
2022.02.07매우 간단한 문제이다. 배열을 순회하며 도시를 지날때마다 요금을 정산하는 식으로 한다. 우선 바로 이전 도시에서 해당 도시까지 달린 요금을 정산한다. 물론 저장된 최저기름값으로 한다. 이러면 기름값이 가장 싼 도시에서 미리 주유한것과 같다. 해당 도시의 기름값이 더 싸다면 최저기름값을 업데이트하고, 다음도시로 향하면 된다. #include int NumOfCity = 0; unsigned long long GasPrice[100001] = { 0 , }; unsigned long long DistanceToNextCity[100001] = { 0 , }; int main() { std::cin.sync_with_stdio(false); std::cout.sync_with_stdio(false); std:..
[BOJ] 1541 잃어버린 괄호 - 그리디 알고리즘
[BOJ] 1541 잃어버린 괄호 - 그리디 알고리즘
2022.02.06매우 간단한 문제이다. 마이너스가 한번 뜨면 그 이후로는 무조건 음수로 만들수 있다. WHY? 그 이후에 오는 연산자가 + 이면 괄호로 합쳐서 음수로 만들수 있고, 연산자가 - 라면 그 이후에 괄호를 칠 수 있고, 이후의 식이 또 다시 음수가 되기 때문이다. 예를 들어 10 - 20 + 30 + 40 - 50 + 60 이라고 하자. 다음과 괄호를 칠 수 있다. 10 -(20 + 30 + 40) - (50 + 60) 10 -20 + 30 + 40 + 50 + 60 이라면? 10 -(20 + 30 + 40 + 50 + 60) #include charbuffer[1024] = { 0 , }; charoperators[100] = { 0 , }; intNumbers[100] = { 0 , }; inttempNu..
[BOJ] 11399 ATM - 그리디 알고리즘
[BOJ] 11399 ATM - 그리디 알고리즘
2022.02.06시간이 오래걸리는 사람은 뒤에 두는 것이 무조건 이득이다. 앞에다 두면 둘수록 뒤의 인원에 시간이 더해지기 때문이다. 정말 간단하다.1 , 4 , 8 을 보자. 8을 맨 앞에 배치하면 8이 3번 더해진다. 1을 맨 앞에 배치하면 1이 3번 더해진다. 4를 맨 앞에 배치하면 4가 3번 더해진다. 각 인원의 ATM 인출시간을 정렬한다. 그리고 뒤에 남은 인원의 수에 자신의 소요시간을 곱해서 차례로 더해나간다. #include #include int Time[1001]; int N; int main() { std::cin.tie(0); std::cout.tie(0); std::cin.sync_with_stdio(false); std::cout.sync_with_stdio(false); std::cin >> N..
[BOJ] 11047 동전 0 - 그리디 알고리즘
[BOJ] 11047 동전 0 - 그리디 알고리즘
2022.02.06큰 동전의 액면가는 작은 동전의 액면가로 무조건 나누어 떨어진다. 다음과 같은 식이다. 5000 1000 500 100 50 25 5 따라서 문제는 간단해진다. 작은 액면가의 동전을 큰 액면가의 동전으로 바꾸어 나가면 된다. 간단한 예를 들어보자. 280원을 만드려고 한다면, 우선 5 원짜리 56개로 시작한다. 5원 짜리에서 25원 짜리로 가기위해선 5원짜리 5개가 필요하다. 25원짜리 11개와 5원 짜리 1개로 바꾼다. 위와 같은 식으로 그냥 바꿔나가기만 하면 답이 된다. 너무 간단하다. #include int Balance[11] = { 0 , }; int CoinValues[11] = { 0 , }; int N = 0; int K = 0; int main() { std::cin.tie(0); std..
[BOJ] 1912 연속합 - 동적 계획법
[BOJ] 1912 연속합 - 동적 계획법
2022.01.17매우 간단한 문제이다. 입력을 받고, 연속해서 숫자를 더해나간다. 그러면 시작점부터, 그 지점까지의 합은 쉽게 구해진다. 음수값이 등장한다. 시작점부터 합을 구했을때 어떠한 구간이 음수라면,그 구간은 제외시키도록 한다. 연속합의 최대값은, 해당 지점까지의 합과 시작점부터 해당지점, 즉 그 구간 내에 있는 음수영역을 빼준 결과중 최대값이다. #include #include int main() { std::cin.tie(0); std::cin.sync_with_stdio(false); std::cout.tie(0); std::cout.sync_with_stdio(false); int MinSumUntilNow = 0; int MaxSumUntilNow = -1001; int LastSum = 0; int S..
[BOJ] 9251 LCS - 동적 계획법
[BOJ] 9251 LCS - 동적 계획법
2022.01.17이 알고리즘을 이해하기 위해서는 확 와닿는 예제가 필요하다.. KCSESE 와 CCCCKC 가 있다고 치자. 답은 눈에 보이다시피 KC의 길이인 2이다. 부분수열을 전부다 구하면 시간내에 못들어온다. 그래서 이걸 동적계획법으로 구해야한다. 점화식을 세워야한다. 우선 A 문자열이 빈 상태로 시작하고, 동적으로 구할 것이므로, 하나씩 원소를 추가한다. A 문자열에 문자가 하나 추가되면 B문자열은 이 추가된 항목에 대해 점화식을 적용한다. 첫 원소가 추가되었다. A 문자열은 이제 A이다. 출발해본다. 이제 차례대로 C, CC, CCC, CCCC, CCCCK, CCCCKCK 와 비교할 것이다. K C A의 마지막 원소 A와 추가된 원소 C를 비교한다. 누가 봐도 다르다. 일단 넘어간다. K CC 이번에 B에 추..
[BOJ] 1149 RGB 거리 - 동적 계획법
[BOJ] 1149 RGB 거리 - 동적 계획법
2022.01.17간단한 동적계획법 문제이다. 이 문제는 아주 예전부터 백준 알고리즘에서 동적계획법으로 문제 분류가 되었다고 한다. 그 만큼 아주 괜찮은 문제라는 것... 아래의 그림을 보도록 하자. N번째 집을 R로 칠했을때의 최대값은 그 이전인 N-1을 G로 칠했을때와 B로 칠했을때의 값중 최대값을 골라서 N번째 집을 R로 칠했을 때의 비용을 합산한 것이다. 그러면 N-1 번째 집을 G 또는 B로 칠했을때의 최대값은 어떻게 구하는가? 또 N-2번째에서의 최대값을 구해봐야하고 이러면 또 N-3 또 N-4 또 N-5 쭉쭉쭉 이어져서 1번째까지 내려가게 된다. 재귀함수로 분기를 하고, 같은 계산시 이득을 볼수 있도록 배열로 저장해둔 값을 적용한다. 코드는 다음과 같다. #include #include enum RGB { R..
[BOJ] 9461 파도반 수열 - 동적 계획법
[BOJ] 9461 파도반 수열 - 동적 계획법
2022.01.17사실상 피보나치 수열과 같은 문제이다. #include unsigned long long PN[101]; int main() { std::cin.tie(0); std::cin.sync_with_stdio(false); std::cout.sync_with_stdio(false); int N = 0; int T = 0; PN[1] = 1; PN[2] = 1; PN[3] = 1; PN[4] = 2; PN[5] = 2; std::cin >> T; for (int X = 0; X > N; if (N < 6) std::cout
[BOJ] 2565 전깃줄 - LIS
[BOJ] 2565 전깃줄 - LIS
2022.01.17LIS를 이루는 것을 알아내고 나면 쉽게 풀어낼 수 있다. LIS 기본 문제는 다음을 참고하도록 하자. 2022.01.16 - [프로그래밍/알고리즘] - [BOJ 11053] 가장 긴 증가하는 부분수열 - LIS 예제의 B 전봇대를 보도록 하자. A 전봇대의 B 전봇대의 타겟을 수열로 나타내면, 8 2 9 1 4 6 7 10 이다. 수열이 증가하는 순서라면 엉키지 않는다. 따라서, 최대 증가 부분 수열을 이루는 부분을 제외하고 나머지 전깃줄을 제거하면 답을 구할수 있다. LIS의 길이를 구하고, 전깃줄의 개수에서 빼준다. #include #include #include int LineTargets[501]= { 0 , }; int main() { std::cin.tie(0); std::cout.tie(0..