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

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

문제이해 문제에서는 다채로운 색이 등장하지만 단순하게 n등분 되어있는 원에서 인접하지않게 k개를 색칠하는 경우의 수를 구하는 문제이다. 알고리즘 전략 알고리즘 구현을 위한 첫걸음은 노트북에서 잠시 손을 내려놓고 펜과 종이로 직접 구해보는것이다. 무언가 규칙성이 있을것같았고 점화식이 있을것같았다. N=6 K=2 일때의 경우로 생각해보자 6개의 칸이 있고 2칸을 이웃하지않게 색칠하는 경우의 수를 구하는 문제이다. 이를 편의상 앞으로 color(6,2) 라고 하자 color(6,2)를 구하기 전에 color(5,2) 를 한번보자 color(5,2)는 다음과 같이 5가지이다 여기서 마지막 칸을 두개로 쪼갠다면 다음과 같다. 바로 위의 5가지 경우는 color(6,2) 의 경우의 수들중 일부이다. color(6,..