분류 전체보기

🗨 개인적인 공부 목적으로 정리한 내용입니다. 잘못된 내용에 대한 피드백은 언제나 감사합니다 :)     ⭐ 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보다 작거나 같은 자연수이다.  출력..

🔗 문제 링크 : https://www.acmicpc.net/problem/12865  문제이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.     입출력 예시입력첫 줄..

🔗 문제 링크 : https://www.acmicpc.net/problem/2467  문제KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다. 같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다.  예를 들어, 주어진 용액들의 특성값이 [-99, -2, -1, 4, 98]인 경우에는 특성값이 -99..