강의
-
-
[고급-8] 동적테이블 응용3강의 2017. 1. 11. 10:14
선물n개의 선물을 한명씩 적절하게 분배.조건 1 : 각자의 부피는 [길동>=길순>=길삼]을 만족하도록분배한다. 조건 2 : 다음의 d가 최소가 되도록 한다. d=(길동선물 부피의 합)-(길삼 선물의 부피 합)조건 3 : 같은 d가 되는 배분방법이 여럿일 경우에는 길동의 선물의 부피 합이 적은 방법을 선택한다. W=a+b+c1~k까지의 선물을 받았을 때, 길순이가 부피 b, 길삼이가 부피 c를 받을 상태는 존재하는가? a=W-(b+c)a값을 굳이 저장 안해도 구할 수 있다는 사실! 1234567891011121314151617181920212223242526272829#include int n, W, G[21], A, B, C, ans=987654321;bool DT[21][2001][2001];int m..
-
[고급-7] 동적테이블 응용2강의 2017. 1. 9. 00:04
색상환 : 미국의 화가 먼셀이 교육용으로 고안한 20색상환문제 : n개의 색에서 인접하지 않은 k개의 색을 구할 때, 경우의 수를 10억3으로 나눈 값을 출력하라! solve(a, b) = 현재 a번 색상에 대해 고려하는 상태, 규칙에 맞도록 b개의 색깔을 이미 선택한 상태.하지만 문제 발생!따라서 f(a,b,c)는 c가 참이면 마지막 색을 고를 수 없는 상태. f함수 설계:if(b==k) return 1; ==> 찾으면 리턴1if(a>=n-can) return 0; ==> a가 2단계로 건너뛰는 경우도 있기 때문에return (f(a+1,b,can)+f(a+2,b+1,can)) %MOD; ==> 두가지 상태의 합을 MOD로 나눈 값의 나머지 출력.하지만 시간이 너무 많이 걸려서if(DT[can][a][..
-
[고급-6] 동적 테이블의 응용1강의 2016. 12. 19. 00:06
학습목표 : 주어진 문제를 동적테이블을 활용하여 해결할 수 있다.재귀함수와 반복문으로 동적테이블을 적용할 수 있다. 1. 동적테이블의 응용1 (1) 광석수집맵이 주어졌을 때, 왼쪽 맨 위의 SCV가 오른쪽 맨 아래의 도착점까지 아래로, 혹은 오른쪽으로만 이동해서 최대의 광석을 구해야 한다. 전체탐색.모든 경로를 탐색한다. 무조건 정답을 찾을 수 있지만 비효율적. 동적테이블 이용12345678910111213141516171819202122232425262728293031#include int n, m, A[210][210], DT[210][210]; int max(int a, int b){ return a>b? a : b;} int solve(int a, int b){ if(DT[a][b] == 0){ ..
-
[고급-5] 동적표와 상/하향식 설계강의 2016. 12. 19. 00:06
학습 목표 : 1. 동적표를 활용하여 알고리즘의 효율을 높일 수 있다.2. 동적표를 이용하여 상/하향식으로 알고리즘을 설계할 수 있다. 1. 동적표 표에서 하나의 값을 이용해 나머지 칸을 차례차례 채워가는 것. 예제 ) 10칸의 표를 만들고 k번째 칸에는 1부터 k까지의 합을 기록한 표를 만들기. 풀이 ) 수학적인 식 이용. n(n+1)/2 = 1~n까지의 합 동적으로 표 채우기. T[k] = 1+2+3+...+(k-1)+kT[k-1] = 1+2+3+...+(k-1)=>T[k]=T[k-1]+k 예제 ) 피보나치 수열.반복적으로 계산된 것들을 모아둔 표를 생성해서 참고한다. 2. 상향식 설계와 하향식 설계 (1) 반복문에서 보면...상향식 : for(i=0; i=1; --i)(2) 재귀함수상향식 : voi..
-
[고급-4] 재귀함수의 확장강의 2016. 11. 27. 02:12
학습목표-이진 문자엘에 대한 문자열 압축(혹은 암호화)에 대한 기법을 실제적인 문제를 통해 해결하는 과정을 재귀적인 관계로 설명할 수 있다.-압축(암호화)된 이진 문자열을 압축이전의 문자열로 복원하는 방법을 압축하는 방법에 대한 역의과정으로 설명할 수 있다.-재귀적인 관계 구성의 다양한 방법을 이해할 수 있다. 1. 재귀함수 활용이진 압축이란, {0,1}로 이루어진 길이가 2^k인 문자열에 대해서 모두 같은 문자가 될 때까지 크기가 2^(k-1)인 두 그룹으로 분할하여 모두 같은 문자가 되도록 하는 과정으로 암호화 한다.1101=>-1-01-:분할, 1:왼쪽은 모두 1, -오른쪽 분할됨, 01:왼쪽0오른쪽1 ex)00111101을 암호화 해보자.분할하면 0011/1101왼쪽 분할하면 00/11/1101오..
-
[고급-3] 재귀함수의 활용강의 2016. 11. 27. 01:10
학습목표-수학적 접근을 통해 해결되는 문제를 수학적 귀납법 설계를 통해 문제를 해결하는 방법을 다양하게 제시할 수 있다.-경우의 수에 대한 문제의 계산량을 감소하는 방법의 필요성과 문제해결 전략을 설계할 수 있다.-비선형적인 구조를 선형적인 구조로 변환하는 방법을 이해하고 이를 실제 문제에 적용할 수 있다. 1. 재귀함수 심화12*1, 2*2크기의 타일을 2*n크기의 직사각형 모양 틀에 배치하는 문제. 값이 커서 주어지는 수 m으로 나눈 나머지 출력. {첫번째 방법. f(n)=1번 칸부터 n번째 칸까지 조건에 맞도록 채운 경우의 수}f(n) = f(n-1) + f(n-2) + f(n-2)1234int f(int k){ if(k짝수일때(1) 반으로 쪼갠다.(2) f(n/2)를 알고 있다고 가정하고 한것이기..
-
[고급-2] 재귀함수의 설계강의 2016. 11. 27. 00:45
학습 목표-문제를 통해 수학적인 함수의 관계를 모색하고 이를 함수로 정의할 수 있다.-다양한 패턴 출력 문제를 통해 수학적 귀납법을 적용할 수 있는 다양한 도메인을 학습할 수 있다.-경우의 수를 세는 방법을 이해하고 수학적 접근과 정보과학적인 접근의 차이점을 이해할 수 있다. 1. 재귀함수 기초 3 하나의 정수를 거꾸로 출력하는 프로그램.예)123{첫번째 방법. 단순 출력} : 1등분12345void f(int n){ if(n==0) return; printf("%d", n%10); f(n/10);}cs{두번째 방법. 오른쪽 끝의 숫자*(자리수-1) 해서 저장.}(자리수는 으로 구한다. : 2등분1234int f(int n){ if(n
-
[중급-3]비선형구조의 탐색, 그래프의 구현강의 2016. 5. 11. 02:31
비선형 구조의 탐색:비선형 구조 : i번째 원소를 탐색한다음 그 원소와 연결된 다른 원소를 탐색하려고 할 때, 다음에 탐색할 수 있는 원소가 여러개 존재하는 구조.일반적으로 트리나 그래프 형태로 자료를 구성할 수 있을 때에 해당 비선형 구조는 단순한 반복으로 탐색할 수 없어서 스택이나 큐같은 자료구조를 통해 탐색방법과 순서를 만들어 탐색한다.비선형 구조의 대표적인 예 : 트리, 그래프어떤 임의의 정점에서 다른 정점까지 이동한다고 가정할때, 사용한 간선들의 순서로 만들어지는 집합을 경로라고 하며, 그 경로에 순환이 생기는 경우를 회로라고 한다.자기자신을 연결 : 자기간선동일한 정점과 연결 : 다중간선모든 간선의 수 : 차수 그래프의 구현 : 그래프 형태로 표현되는 문제 상황 또는 데이터 구조인접 행렬 : ..
-
[중급-2] Lower bound, Upper bound강의 2016. 5. 8. 21:55
학습 목표 :Lower bound의 개념과 방법을 이해한다.Upper bound의 개념과 방법을 이해한다. 1. Lower bound->Lower boundlower bound는 찾고자 하는 값 이상이 처음 나타나는 위치.원소가 여러개 있어도 상관 무.즉, 찾고자 하는 값 이상이 처음 나타나는 위치를 찾기 위해 쓴다.(이분탐색 방법 조금 변형하면 된다) 문제 : n개로 이루어진 정수 집합에서 원하는 수 k이상인 수가 처음으로 등장하는 위치를 찾으시오. 단, 입력되는 집합은 오름차순으로 정렬되어있으며, 같은 수가 여러 개 존재할 수 있다. 입력 : 첫줄에 한 정수 n이 입력됨.둘째 줄에 n개의 정수가 공백으로 구분되어 입력됨.셋째 줄에 찾고자 하는 값 k가 입력됨.2