백준
BaekJoon(1644)::소수의 연속합
문제 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 문제파악 연속된 소수의 합으로 나타낼수 있는지 여부의 문제이다. 다면 여기서 연속된 소수의 합이기 떄문에 소수판별의 문제와 투포인터를 사용해서 문제를 풀수 있을 것으로 보인다 문제풀이 소수판별(에라토스테네스의 체) 투포인터 2가지를 고려해서 'r_index까지의 합'에서 'l_index까지의 합'을 뺌으로써 값을 찾을 수 있다 #include #include #include #include using namespace std; const int MAX_N = 4000000; vector primSumArr; bool primeArrYn[MAX_N + 1]; void setSi..
BaekJoon(2023)::신기한 소수
문제 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 문제파악 해당 문제는 N자리의 수가 주어질 경우 해당 수의 왼쪽부터 1자리,2자리 3자리가 전부 소수인 소수를 구하는 문제가 된다. 즉, 해당 문제를 푸는데 있어서 내가 든 생각은 다음 조건들이 있다는 생각이 들었다. 각 자리의 수 : 0~9 소수 판별 N자리 수만큼 반복 이러한 조건들을 생각해보고 문제를 해결해 보았다. 문제풀이 #include using namespace std; bool isPrime(int num) { if (num < 2..
BaekJoon(5582)::공통 부분 문자열
문제 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 문제파악 해당문제는 LCS와 비슷하게 풀 수 있는 문제이다. 다만, 기존 LCS는 Longest-Common-Subsequence라면 해당 문제는 Longest-Common-SubString 문제이다. 위 두 LCS또한 결국 DP문제이기 때문에 점화식을 통해 문제를 해결하면 쉽게 해결가능하다. 문제풀이 해당문제의 LCS(Longest Common SubString)의 점화식을 구해보면 다음과 같다. $$ LCS(X_i, Y_j) = \begin{..
BaekJoon(9252)::LCS 2
문제 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제파악 해당문제 또한 백준1904번의 LCS와 같이 제목에서부터 해답을 전달해주고 있다. Longest Common Sub-sequence Algorithm(LCS, 최장 공통 부분수열) Longest Common Sub-sequence Algorithm(LCS) LIS알고리즘을 정리하다가 비슷한류의 알고리즘으로 보여 함께 이어서 정리하려고 한다. 이문제 또한 아마 DP를 이용한 문제가 될것으로 생각된다. ..
BaekJoon(9251)::LCS
문제 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제파악 해당문제는 단순하게 제목에서부터 풀이법을 말해주고있다. Longest Common Sub-sequence Algorithm(LCS, 최장 공통 부분수열) Longest Common Sub-sequence Algorithm(LCS) LIS알고리즘을 정리하다가 비슷한류의 알고리즘으로 보여 함께 이어서 정리하려고 한다. 이문제 또한 아마 DP를 이용한 문제가 될것으로 생각된다. 다만 문자로 dev-sanghu..
BaekJoon(1904)::01타일
문제 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 문제 파악 이 문제는 결국 00타일 1타일 두개로 N길이의 타일을 만들수 있는 가지수를 구하는 문제이다. 그림으로 그려봐도 알 수 있는 것처럼 결국 N-2 타일에 00을 붙이냐 N-1타일에 1을 붙이냐의 차이의 문제가 될것같다 $$f(n) = f(n-1) + f(n-2)$$ 문제 풀이 문제 파악과정에서 알게 된 수식을 보면 피보나치 수열과 같음을 알 수 있다. 피보나치 수열의 단점은 시간이 오래 걸릴수 있다는 점이다. 이 점을 해결하기 위해 dp를 사용할 예정이..
BaekJoon(9184)::신나는 함수 실행
문제 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 문제 파악 if a 20, then w(a, b, c) returns: w(20, 20, 20) if a < b and b < c, then w(a, b, c) returns: w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c) otherwise it returns: w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1) 문제에서 이미 재귀함수가 주어지기 때문에 따로 재..
BaekJoon(11053)::가장 긴 증가하는 부분 수열
문제 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 파악 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000) LIS 알고리즘으로 해결이 가능한 문제이다...
BaekJoon(10844)::쉬운 계단 수
문제 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 파악 여기서 쉬운 계단수란? '인접한 모든 자리의 차이가 1'인 수를 말한다. N이 주어졌을때, 길이가 N인 쉬운 계단 수가 몇개 있는지 구하는 문제이다. 여기서 주의할점은 숫자의 길이가 100자리를 넘는다는 점과 0으로 시작하는 수는 계단수가 아니라는 점이다 문제 풀이 해당 문제의 진행을 다음과 같다. 결국 N자리의 수에서의 계단수의 갯수는 N-1번째 계단의 수에서 결정이 된다. 이유를 잘생각해보면 N자리의 마지막 수는 N-1번째 계단수의 마지막수와 차이가 1일 수 밖에 없기 때문이다. 이러한 점을 잘 생각해보면 다음과 같은 식을 구할 수 있다. 끝자리의 값이 무엇..
BaekJoon(1463)::1로 만들기
문제 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제파악 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 최소 연산횟수를 구하는 문제. 즉, DP를 사용하면 해결이 가능해 보인다. 문제풀이 해당 문제도 dp를 이용하면 풀수 있을 것이며, 그중 나의 경우 반복문을 이용해서 풀 생각이다. dp[n] = dp[n-1] + 1는 기본적으로 가능한 횟수이다. 그리고 각 나누어떨어지는 상황 즉, 2로 나누는 연산과 3으로 나누는 연산과의 횟수를 비교해서 작은 값을 저장해 주면 된다. #include using na..
BaekJoon(10773)::제로
문제 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 문제 파악 해당 문제는 0을 넣으면 가장 최근에 넣은 수를 빼는 문제 즉, 스택을 이용해서 문제를 해결하면 된다. 여기서 0은 지울수 있는 수가 있음을 보장하기 때문에 empty 여부를 확인 하지 않아도된다. 문제 풀이 딱히 풀이 할 것이 없어보인다. 스택을 이용하면 된다. #include #include using namespace std; int main() { int n; cin >> n; stack st; while ..
BaekJoon(9012)::괄호
문제 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 문제파악 괄호문자열(Parenthesis String,PS)은 두 개의 괄호 기호인 '('와 ')'로 구성된 문자열. 그 괄호 모양이 잘 닫혀져 있으면 올바른 문자열은(Valid PS, VPS)라고 부른다. 예를 들어 '(()())' 그리고 '((()))' 등은 vps지만 '(()(' 혹은'(()' 등은 vps를 만족하지 못한다. '(' 그리고 ')'로 구성된 문자열 : VPS 두개의 vps로 접합된 문자열 또한 VPS 만족 ..