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

연쇄행렬 최소곱셈 알고리즘 (Matrix chain multiplication) 연쇄행렬 최소곱셈 알고리즘이란 주어진 행렬들의 곱을 최소의 연산으로 수행하는 최소횟수를 구하는 알고리즘이다. 행렬의 곱셈에서 결합법칙은 성립하지만 어떤 형태로 결합되느냐에 따라 계산 횟수는 달라질수 있다. 예를 들어 아래와같은 행렬이 있다고 할때 결합 형태에 따른 연산횟수 차이는 다음과 같다. 위와 같이 결합되는 순서에 따라 전체 연산횟수가 달라짐을 알수 있다. 그렇다면 본격적으로 연쇄행렬 최소곱셈 알고리즘에 대해 알아보자. 먼저 행렬의 개수가 5개일때 모든 결합의 마지막 결합 형태는 크게 다음과같이 네가지로 분류가 가능하다. ( 행렬의 개수가 n개일때 (n-1)가지로 분류가 가능하다.) 예를 들어 (AB)(C(DE)) 는 ..

문제이해 N개의 높이가 다른 블록들로 높이가 같은 두개의 탑을 쌓는데 그 탑의 높이가 최대일때의 그 높이를 구하는 문제이다. 단, 모든 블록을 사용할 필요가 없다. 알고리즘 설계 만약 블록을 쌓을때 구역 a와 b에 쌓아서 두개의 탑을 만든다고 할때 각 블록마다 1. a에 쌓는다 2. b에 쌓는다 3. 둘다 쌓지않는다 ( 사용하지 않는다 ) 3가지 경우가 있다. 여기서 한가지 정해놓고 갈 부분. 위 그림은 블록 4개로 탑을 쌓는과정중 일부인데 두 상황이 좌우에 누가 더 높냐만 다르지 25와 30으로 두 상황에서 두 탑의 높이가 동일하다. 따라서 함수를 진행하면서 a구역을 두 탑중 높은 탑, b구역을 두 탑중 낮은 탑으로 진행을 하게될것이고 해당 변수는 l ( large )과 s ( small )이다. 따라..

문제이해 이 문제는 집합에서의 기본적인연산 ( 원소의 추가, 삭제, 확인, 반전, 전체 변경, 전체 삭제 등) 을 수행하는 알고리즘을 설계하는 문제이다. 다만 수행해야하는 연산의 수가 최대 3,000,000 이므로 배열연산보다는 비트마스크를 활용해서 문제를 해결해야할것이다. 알고리즘 설계 사실 비트마스크를 사용해본적이 있다면 쉽게 해결할수 있을것이다. 집합의 원소개수가 1부터 20까지 20개 이므로 한개의 int에서 20bit를 사용해서 n번째 원소가 채워져있으면 2^(n-1) 에 해당하는 부분을 1로 아니라면 0으로 채워서 현재 집합의 상태를 표현할수 있다. #include #include int ss = 0; int bit(char ar[], int k); int main(){ int n,i,j; c..

최장 공통 부분 수열( 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) 를 이용한 알고리즘 첫번째로 알아볼 알고리즘..

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