프로그래밍에 대한 고찰 및 생각

최장 공통 부분 수열( LCS : Longest common substring ) 최장 공통 부분 수열(이하 LCS)은 주어진 여러 개의 수열 모두의 부분수열이 되는 수열들 중에 가장 긴 것을 찾는 문제이다. 여기서 공통 부분 수열이라함은 예를 들어 ABCD ADEFB 두 문자열이 있을 때, 공통 부분 수열은 A D AD AB 라고 할 수 있다. 여기서 최장 공통 부분 수열은 이들중 가장 길이가 긴 수열이므로 AD 혹은 AB가 된다. 이 LCS를 구하기 위해서 대표적으로 사용되는 예인 ACAYKP 와 CAPCAK 로 살펴보자. 위의 표로 설명을 할텐데 안에 채워질 숫자의 의미는 해당 열와 행까지의 수열에서 LCS를 의미한다. 다음 그림을 참고해보자. 맨 첫칸부터 (0,0) 이라하면 ? 가 있는 부분은 (..

문제이해 문제에서는 총 N개의 그림이 주어지고 각 그림마다 높이와 가격이 존재한다. 중요한 부분은 앞에서 보았을때 보이는 폭의 길이가 특정정수 S이상이 되어야 판매가능한 그림이 된다는점이다. 이부분을 중점으로 생각해보자 알고리즘 전략 먼저 앞에서 봤을때 보이는 폭의 길이가 중요한 포인트이므로 높이와 가격을 가진 각각의 그림들을 구조체로 선언해주고 높이를 오름차순으로 정렬해주자. 그리고 배열 dp[i]를 이렇게 정의하자. dp[i] : i번째그림까지중 i번째그림을 무조건 선택한다고 했을때 최대 가격의 합 그리고 문제에서는 모든 그림들을 배열한다고 했지만 편의상 총가격에 포함되는 그림들을 선택하고 불필요한 그림들은 선택하지 않는다고 생각하자. 그렇다면 점화식은 어떻게되는지 보자. price[i] 를 i번째 ..

2. Lower Bound 를 이용한 알고리즘 두번째로 알아볼 알고리즘은 Lower Bound를 이용한 알고리즘이다. 시작하기에 앞서 Lower Bound란 정렬된 배열에서 찾고자 하는 값 이상이 처음으로 나타나는 위치를 말한다. 다음과 같은 배열에서 35의 lower bound는 40 이다. 위의 정의대로 처음으로 나타나는 자신보다 큰값 이라고 생각해도 되고 자신보다 큰 값들중 가장 작은 값 으로 생각해도 된다. 이 lower bound 알고리즘을 이분탐색으로 구현하게 될텐데 여기서는 lis[] 배열을 만들어서 사용할것이다. lis[i] 의 정의는 (i+1)의 길이를 갖는 최대증가수열을 만들때, 가능한 가장 작은 수를 의미한다. 먼저 전체코드는 다음과 같다 int lis_lowerbound(int n)..

LIS Algorithm LIS 알고리즘 (Longest Increasing Subsequence Algorithm) 은 최장증가수열 알고리즘으로 증가하는 원소들의 가장 긴 부분집합을 찾는 알고리즘이다. 다음과 같이 7개의 숫자가 나열되어있을때 여기서 LIS는 위와같이 20 40 50 80 으로 최대길이는 4이다. 물론 아래와 같은 경우도 모두 LIS에 속한다. (LIS알고리즘에서 최대길이를 구성하는 모든 원소들을 구할경우 아래와같이 가능한 경우의 수가 여려개 일수 있기때문에 백준저지에서는 스페셜 저지로 채점을 한다.) + 주의할점은 항상 이전에 선택한 원소보다 커야하기때문에 같은원소역시 연속으로 선택할수 없다. 1. DP(Dynamic Programming) 를 이용한 알고리즘 첫번째로 알아볼 알고리즘..

from sys import stdin import sys sys.setrecursionlimit(10000000) def tile(answer,n,now): if(now == 0 or now == 1): return 1 elif(now == 2): return 3 if(answer[now] != 0): return answer[now] tmp1 = 2*tile(answer,n,now-2) tmp2 = tile(answer,n,now-1) total = tmp1 + tmp2 answer[now] = total return total answer = [0] * (251) for n in map(int, stdin.read().split()): print(tile(answer,n,n)) 위와같은 문제의 입력..

소수의 정의 소수라 함은 자신보다 작은 두개의 자연수를 곱하여 만들수 없는 1보다 큰 자연수 이다. 예를 들어 2, 3, 5, 7 ,11 ... 등이 있다. 소수 구하기 소수를 구하는 대표적인 방법은 고대 그리스 수학자 에라토스테네스가 발견한 방법을 사용하는 것이다. 이 방법은 2부터 n까지의 자연수 수열에서 가장 앞에 있는 숫자가 소수가 되고 그 뒤로 그수의 배수들을 전부 지운다. 그리고 그 다음 남아있는 숫자가 소수가 되고 또 그 뒤로 그 수의 배수들을 전부 지운다 ... 이 과정을 반복하다보면 n까지의 소수들을 찾을 수 있다. 아래 자료를 보면 쉽게 이해가 될것이다. 이를 코드로 구현하는 것은 어렵지 않다. 아래는 파이썬으로 구현한 코드이다. n = int(input("")) arr = list(r..

문제 이해 백준저지에는 이미 n x m의 격자상에 특정 블록을 넣어 채우는 경우의 수를 구하는 문제들이 많다. 2 x N 격자에 2 x 1 , 1 x 2 크기의 타일로 채우는 경우의 수를 구하는 11726번 https://www.acmicpc.net/problem/11726 2 x N 격자에 2 x 1 , 2 x 2 크기의 타일로 채우는 경우의 수를 구하는 11727번 https://www.acmicpc.net/problem/11727 3 x N 격자에 2 x 1 , 1 x 2 크기의 타일로 채우는 경우의 수를 구하는 2133번 https://www.acmicpc.net/problem/2133 좌우대칭을 고려해야하는 1720번 https://www.acmicpc.net/problem/1720 위의 타일링..

문제 이해 문제자체는 간단하지만 n이 조금만 커져도 경우의수가 커지고 점화식도 쉽게 발견되지 않아 조금은 까다로웠던 문제였다. 서로 팔이 교차하지 않는 것을 중점으로 생각해봐야 할것같다. 알고리즘 전략 점화식에 접근할때 n이 주어졌을때 그 상황들을 분해하려고 고민을 했다. 먼저 n = 8 일때로 먼저 분석을 해보자. ( 편의상 n=k일때 가능한 경우의 수를 dp[k]라고 하자 ) 이 상황에서 악수를 할수 있는 경우의 수를 찾다보면 한가지 규칙을 찾을 수 있다. 어떤사람과 어떤사람이 악수할때 그 둘 사이에 있는 사람의 수가 홀수가 되면 안된다는 것이다. 따라서 파란색 점을 기준으로 할때 이 사람이 악수 할수 있는 사람은 위의 3점과 자신을 제외한 4개의 점이다. 파란색이 악수 할수있는 점은 다음과 같다. ..