🔗 문제 링크 : https://www.acmicpc.net/problem/1916  문제N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다.     입출력 예시입력첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 ..

🔗 문제 링크 : https://www.acmicpc.net/problem/1929  문제M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.     입출력 예시입력첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.  출력한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.      풀이 입력값 M, N에 대하여, M ~ N 범위의 소수를 구하는 문제이다.에라토스테네스의 체 알고리즘을 이용하면, ⏱ 시간복잡도 $\mathbf{O(n\;log\;log\;n)}$으로 간단히 해결할 수 있다.  ✒ 에라토스테네스의 체 에라토스테네스의 체는 2부터 시작하여 소수의 배수를 지워나가는 방식으로 소..

🗨 개인적인 공부 목적으로 정리한 내용입니다. 잘못된 내용에 대한 피드백은 언제나 감사합니다 :)     ⭐ Longest Common Subsequence(LCS) 알고리즘은 두 문자열에서 순서를 유지하면서 공통으로 나타나는 가장 긴 부분 수열을 동적 계획법(Dynamic Programming)으로 찾아내는 알고리즘이다.   📌 Longest Common Subsequence (LCS) vs Longest Common Substring Longest Common Subsequence(최장 공통 부분 수열, LCS)는 두 개의 문자열이나 수열 사이에서 순서를 유지하면서 연속하지 않아도 되는 공통된 부분을 말한다.이 알고리즘과 비슷하면서 다른 Longest Common Substring(최장 공통 문자..

🔗 문제 링크 : https://www.acmicpc.net/problem/16928  문제뱀과 사다리 게임을 즐겨 하는 큐브러버는 어느 날 궁금한 점이 생겼다. 주사위를 조작해 내가 원하는 수가 나오게 만들 수 있다면, 최소 몇 번만에 도착점에 도착할 수 있을까? 게임은 정육면체 주사위를 사용하며, 주사위의 각 면에는 1부터 6까지 수가 하나씩 적혀있다. 게임은 크기가 10×10이고, 총 100개의 칸으로 나누어져 있는 보드판에서 진행된다. 보드판에는 1부터 100까지 수가 하나씩 순서대로 적혀져 있다. 플레이어는 주사위를 굴려 나온 수만큼 이동해야 한다. 예를 들어, 플레이어가 i번 칸에 있고, 주사위를 굴려 나온 수가 4라면, i+4번 칸으로 이동해야 한다. 만약 주사위를 굴린 결과가 100번 ..

🔗 문제 링크 : https://www.acmicpc.net/problem/2935  문제수업 시간에 떠드는 두 학생이 있다. 두 학생은 수업에 집중하는 대신에 글로벌 경제 위기에 대해서 토론하고 있었다. 토론이 점점 과열되면서 두 학생은 목소리를 높였고, 결국 선생님은 크게 분노하였다. 이렇게 학생들이 수업 시간에 떠드는 문제는 어떻게 해결해야 할까? 얼마전에 초등학교 선생님으로 취직한 상근이는 이 문제를 수학 문제로 해결한다. 학생들을 진정시키기 위해 칠판에 수학 문제를 써주고, 아이들에게 조용히 이 문제를 풀게 한다. 학생들이 문제를 금방 풀고 다시 떠드는 것을 방지하기 위해서, 숫자를 매우 크게 한다. 아직 초등학교이기 때문에, 학생들은 덧셈과 곱셈만 배웠다. 또, 아직 10의 제곱꼴을 제외한..

🔗 문제 링크 : https://www.acmicpc.net/problem/9251  문제LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.     입출력 예시입력첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.  출력첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.       풀이 LCS(Longest Common Subsequence, 최장 공통 부분 수열) 알고리즘을 공부하고 첫 번째로 풀기 좋은 문제다! #inclu..

🗨 개인적인 공부 목적으로 정리한 내용입니다. 잘못된 내용에 대한 피드백은 언제나 감사합니다 :)     ⭐  선형 에라토스테네스의 체는 기존의 에라토스테네스의 체를 개선하여 $O(n)$의 시간 복잡도로 소수를 찾는 알고리즘이다.이는 각 숫자를 가장 작은 소인수로 한 번만 처리하여 불필요한 계산을 줄였다.   에라토스테네스의 체에 대한 글 [Algorithm] 에라토스테네스의 체(Sieve of Eratosthenes) : 소수를 구하는 고효율 알고리즘 [Algorithm] 에라토스테네스의 체(Sieve of Eratosthenes) : 소수를 구하는 고효율 알고리즘🗨 개인적인 공부 목적으로 정리한 내용입니다. 잘못된 내용에 대한 피드백은 언제나 감사합니다 :)     ⭐ 에라토스테네스의 체는 작은 ..

🗨 개인적인 공부 목적으로 정리한 내용입니다. 잘못된 내용에 대한 피드백은 언제나 감사합니다 :)     ⭐ 에라토스테네스의 체는 작은 수부터 시작하여 소수의 배수를 지워나가는 방식으로 소수를 찾는 고효율적인 알고리즘이다.   📌 에라토스테네스의 체 (Sieve of Eratosthenes)고대 그리스의 수학자인 에라토스테네스가 발견한 소수를 찾는 가장 빠르고 쉬운 방법이다.   ⏱ $\mathbf{O(n\;log\;log\;n)}$ 의 시간 복잡도를 가진다. 아래 동작 원리 부분을 보면 알겠지만, 지워진 부분도 차례가 되면 불필요하게 탐색하기 때문에 이를 보완한 방법도 존재한다.이는 기존의 에라토스테네스의 체를 개선한 "선형 에라토스테네스의 체"로, 시간 복잡도를 $O(n)$으로 줄인 알고리즘이다...

🔗 문제 링크 : https://www.acmicpc.net/problem/1535  문제세준이는 성형수술을 한 후에 병원에 너무 오래 입원해 있었다. 이제 세준이가 병원에 입원한 동안 자기를 생각해준 사람들에게 감사하다고 말할 차례이다. 세준이를 생각해준 사람은 총 N명이 있다. 사람의 번호는 1번부터 N번까지 있다. 세준이가 i번 사람에게 인사를 하면 L[i]만큼의 체력을 잃고, J[i]만큼의 기쁨을 얻는다. 세준이는 각각의 사람에게 최대 1번만 말할 수 있다. 세준이의 목표는 주어진 체력내에서 최대한의 기쁨을 느끼는 것이다. 세준이의 체력은 100이고, 기쁨은 0이다. 만약 세준이의 체력이 0이나 음수가 되면, 죽어서 아무런 기쁨을 못 느낀 것이 된다. 세준이가 얻을 수 있는 최대 기쁨을 출력하..

🔗 문제 링크 : https://www.acmicpc.net/problem/2749  문제피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다. n=17일때 까지 피보나치 수를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.     입출력 예시입력첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.  출력..