전체 글
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..
JAVA::JVM에 대한 이해
이 글은 '백기선의 더 자바, 코드를 조작하는 다양한 방법' 강좌를 듣고 해당 내용을 공부하며 정리한 글입니다. JVM에 대한 이해 자바를 사용할 때 사용하게 되는 JVM, JRE, JDK 그리고 자바에 대해서 알아보려고 한다. JVM이란? Java Virtual Machine의 약자. 자바 애플리케이션을 클래스 로더를 통해 읽어 들여 자바 API와 함께 실행하는 것으로 JAVA와 OS사이에서 중개자 역할을 수행하여 JAVA가 OS의 영향을 받지 않고 재사용할 수 있게 해준다. 자바, JVM, JRE, JDK JVM(Java Virtual Machine) 자바 가상 머신으로 자바 바이트 코드(.class파일)를 OS에 특화된 코드로 변환(인터프리터와 JIT 컴파일러)하여 실행 바이트 코드를 실행하는 표준..
Longest Common Sub-sequence Algorithm(LCS, 최장 공통 부분수열)
Longest Common Sub-sequence Algorithm(LCS) LIS알고리즘을 정리하다가 비슷한류의 알고리즘으로 보여 함께 이어서 정리하려고 한다. 이문제 또한 아마 DP를 이용한 문제가 될것으로 생각된다. 다만 문자로 이루어진 수열이기에 LIS에서 사용했던 이분탐색은 불가능해보인다. 그리고 해당 문제에서도 길이 뿐만이 아닌 해당 부분수열을 구하는 방법도 알아보도록 하겠다. 정의(Definition) 최장 공통 부분수열으로 두 문자열의 가장 긴 공통된 부분문자열을 구하는 문제 Longest Common Sub-sequence 불린다. 여기서 string이 아닌 sequence는 사용하는 이유는 각 단어가 갖는 개념적 의미가 다르기 때문이다. string : 연속된 문자열 sequence :..
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) 문제에서 이미 재귀함수가 주어지기 때문에 따로 재..
Longest Increasing Sub-sequence Algorithm(LIS, 최장 증가 부분 수열 알고리즘)
Longest Increasing Sub-sequence Algorithm(LIS) 동적계획법(DP)문제를 풀다가 우연찮게 해당 알고리즘의 문제를 풀게되면서 이전 기억을 살려 다시한번 정리를 해보려고 한다. 해당 문제는 최장길이만 구하다 보니 동적계획법을 이용해서 해결이 되었지만, 더 다양한 문제를 해결하기 위해 그리고 LIS알고리즘을 더 잘 이해하기 위해 해당 페이지에 정리를 하려고 합니다. 정의(Definition) 주어진 수열에서 오름차순으로 정렬된 가장 긴 부분수열을 찾는 알고리즘 부분 수열은 연속적이거나 유일한 필요가 없다. 최장길이를 구하거나, 해당 부분수열을 구할 수 있다. 여러 시간복잡도로 문제를 해결할 수 있다. 부분수열이란? 주어진 수열에서 특정 원소들을 선택해서 만들어진 수열을 그 수..
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 ..