본문 바로가기

분류 전체보기

(317)
# Foundation/알고리즘 가장 긴 공통 부분 문자열 (LCS - Longest Common Substring) 알고리즘 LCS의 정의가장 긴 공통 부분 문자열 (Longest Common Substring)두 문자열의 가장 긴 부분 문자열이다.문자열이란 끊어지지 않는 문자들의 연속이다. 가장 긴 공통 부분 수열 (Longest Common Sequence)두 문자열의 가장 긴 부분 수열이다.부분 수열이란 원래 수열에서 임의의 원소를 0개 이상 지워서 만든 수열이다. 이 포스팅에서는 가장 긴 공통 부분 문자열을 다루며, 다루어지는 주제는 다음과 같다.N^2 풀이경로 추적 N^2 풀이동적 계획법을 사용하여 문제를 풀어보자.작은 문제부터 시작하여 큰 문제를 해결하는 것 이다! int solve(int i, int j) // A[0...i]와 B[0...j]에서, A[i]와 B[j]를 공통된 끝으로 갖는 최대 부분 문자열의 길이..

2019. 7. 1. 12:32

# Foundation/알고리즘 가장 긴 증가하는 부분 수열 (LIS - Longest Increasing Subsequence) 알고리즘 가장 긴 증가하는 부분 수열 (LIS)최장 증가 부분 수열 문제란, 주어진 수열에서 오름차순으로 되어있는 가장 긴 부분수열을 찾는 문제이다. 이 때, 부분수열은 반드시 연속적일 필요는 없으며,필요하다면 중간을 건너뛰는 것도 가능하다. 예를 들어, 수열 A = {10, 20, 60, 50, 30, 40, 20} 에서,가장 긴 증가하는 부분 수열은 A = {10, 20, 60, 50, 30, 40, 20} 이고, 길이는 4 이다. 대표적인 동적 계획법(Dynamic Programming) 문제이며,이 게시글에서 설명할 주제는 다음과 같다.LIS의 특성N^2 문제풀이N*logN 문제풀이경로 역추적 (백트래킹) LIS의 특성어떤 수열에 대해 적절히 n개를 삭제하여 최대한 긴 증가 부분 수열을 만드는 것이므로,이..

2019. 6. 30. 16:25

# Foundation/백준풀이 [이분탐색] 백준 10816 :: 숫자 카드 2 숫자 카드 2 성공시간 제한메모리 제한제출정답맞은 사람정답 비율1 초256 MB98942933201733.723%문제숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.입력첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이가 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정..

2019. 6. 25. 17:47

# Foundation/백준풀이 [이분탐색] 백준 1654 :: 랜선 자르기 랜선 자르기 성공시간 제한메모리 제한제출정답맞은 사람정답 비율2 초128 MB283735211337318.668%문제집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다. 이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm 은 버려야 한다.(이미 자른 랜선은 붙일 수 없다.) 편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 ..

2019. 6. 25. 17:13

# Foundation/알고리즘 동적 계획법(Dynamic Programming) 알고리즘 동적 계획법 이름의 유래수학, 컴퓨터 공학, 경제학에서 사용되는 문제풀이 방법. 리처드 벨만이 처음 이 단어를 사용했으며,그의 자서전 '태풍의 눈'에서 다음과 같이 설명했다. 어떤 문제가 다단계로 이루어져 있으며, // sub-structure시간에 대해 가변적이고, // time-varying동적이다. // dynamic 시간에 대해 가변적이라는 특성은, 특히 경제학에서 주로 다뤄지는 것 같다. 동적 계획법이란?하나의 복잡한 문제를, 동일한 구조의 간단한 문제들의 합으로 푸는 방법. 하나의 문제를, 그것과 동일한 형태의 작은 문제들로 나눈 뒤.작은 문제들을 풀어내어 최종적인 문제에 접근하는 것이 그 목적이다. 또한 어떤 문제를 푸는 도중에, 작은 문제들의 결과값이 필요하다면,작은 문제를 푸는 과정으로 ..

2019. 6. 25. 16:16

# Foundation/백준풀이 [동적계획법] 백준 1003 :: 피보나치 함수 피보나치 함수 성공시간 제한메모리 제한제출정답맞은 사람정답 비율0.25 초 (언어별 추가 시간 없음)128 MB66959146351165829.096%문제다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.1234567891011int fibonacci(int n) { if (n == 0) { printf("0"); return 0; } else if (n == 1) { printf("1"); return 1; } else { return fibonacci(n‐1) + fibonacci(n‐2); }}fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.fibonacci(2)는 fibonac..

2019. 6. 24. 02:46

# 미사용 서브라임 텍스트 3 정규식 바꾸기 매크로 RegReplace Reg Replace 플러그인 Reg Replace 플러그인은 여러개의 바꾸기 작업을 매크로처럼 사용할 수 있도록 도와준다. 유저는 각각의 replace rule을 만들고, 이것을 command로 묶어서 실행시킬 수 있다. 설치하기 InstallationPackage ControlThe recommended way to install RegReplace is via Package Control. Package Control will install the correct branch on your system and keep it up to date.Ensure Package Control is installed. Instructions are found here.In Sublime Text, press..

2019. 6. 24. 02:04

# Foundation/백준풀이 [동적계획법] 백준 1463 :: 1로 만들기 1로 만들기 성공시간 제한메모리 제한제출정답맞은 사람정답 비율2 초128 MB74952244731562832.094%문제정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.입력첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.출력첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.예제 입력 1 복사2 예제 출력 1 복사1 예제 입력 2 복사10 예제 출력 2 복사3 힌트10의 경우에 10 -> 9 -> 3 -> 1 로 3번 만에 만들 수 있다. 문제 ..

2019. 6. 24. 01:25