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

알고리즘 설계 문제에서 주어지는 n명의 그림 소유상태를 비트마스킹으로 표현하고 DP를 이용해서 해결할수 있는문제이다. 만약 비트연산을 처음 들어봤다면 비트연산을 먼저 공부하고 오는 것을 추천한다. 전체 코드는 다음과 같다. #include int n; int pp[16][16]; int dp[15][32768] = {0}; int ddp(int state, int before, int price); int max(int x, int y); int main(){ int i,j; scanf("%d",&n); for(i=0;i

배낭 문제 배낭문제는 n개의물건이 있고 각각 무게와 가치가 주어질때, 물건을 m이하의 무게로 담을때 가능한 최대 가치를 구하는 문제이다. 이 배낭 문제는 크게 3가지로 분류된다. 배낭 빈틈없이 채우기 문제 ( Fractional Knapsack Problem) 0/1 배낭 문제 (0/1 Knapsack Problem) 개수제한 없는 0/1 배낭 문제 (Unbounded Knapsack Problem) 이 중 0/1 배낭 문제 (0/1 knapsack problem) 에 대해 알아보자. 0/1 배낭 문제 ( 0/1 Knapsack Problem) 0/1배낭 문제는 최대 가방무게 이하로 물건을 담을때 가치가 최대로 최게 담아야하는데 단, 물건을 일부만 담을 수 없고 담거나 담지 않거나 둘중 한가지를 택해야한..

배낭 문제 배낭문제는 n개의물건이 있고 각각 무게와 가치가 주어질때, 물건을 m이하의 무게로 담을때 가능한 최대 가치를 구하는 문제이다. 이 배낭 문제는 크게 3가지로 분류된다. 배낭 빈틈없이 채우기 문제 ( Fractional Knapsack Problem) 0/1 배낭 문제 (0/1 Knapsack Problem) 개수제한 없는 0/1 배낭 문제 (Unbounded Knapsack Problem) 이 중 배낭을 빈틈없이 채우는 문제에 대해 알아보자. Fraction Knapsack Problem 배낭 빈틈없이 채우기 문제는 최대 가방무게 이하로 물건을 담을때 가치가 최대로 최게 담아야하는데 단, 물건을 일부만 담을 수도 있다. 예를 들어 무게가 10이고 가치가 20인 물건 A를 절반만 담으면 무게가 ..

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

상수 변수 초깃값을 변경할 수 없는 변수를 상수 변수라고 한다.(줄여서 상수) const int MAX_SIZE = 10; 와 같이 사용한다. 자료형 정수 char - 1byte short - 2byte int - 4byte long 4byte 실수 float - 4byte double - 8byte int 의 범위가 약 21억~21억 인이유 int 의 크기는 4byte로 32bit 이다. 한 비트당 1 또는 0의 상태를 가지므로 총 2^32(4294967296) 가지의 숫자를 표현할수 있는데 맨 앞자리 비트는 부호를 의미하기 때문에 양수 음수 각각 2^31인 2147483648까지 표현이 가능한데 실제 표현 가능 범위는 -2147483648 ~ 2147483647 이다. 마지막 1의자리수가 다른 이유는..

문제이해 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..

비트연산을 쓰는 이유에 대하여 비트연산은 여러분야에서 활용도가 높다. 컴퓨팅 시스템에서 오류검출, 네트워크 시스템에서의 오류검출, 그리고 알고리즘에서의 상태저장 등등에 쓰인다. 그중 알고리즘측면에서 비트연산은 N개의 지점에 대해 0과1로 그 상태를 저장해둘때 유용하다. 예를들어 N개의 도시를 한번씩 방문하면서 순회하는 외판원 문제에서 각 도시들의 방문상태를 저장할때 일반적인 배열을 사용하게 되면 N만큼의 int를 사용하게 되고 N * 4byte의 공간을 사용하게 된다. 그러나 N이 15라고 가정할때 배열에서는 15 * 4byte = 60 byte를 사용하게 되는데 비트연산에서는 2^15 = 32768 이므로 1개의 int(약 -21억~21억)내에 들어오게되므로 4byte에 처리가 가능하다. 이렇게 보면 ..