sunrin
-
[고급-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
-
(이산수학-2차시) 시도예선 2013~2014 중고등부 문제 오답노트알고리즘/정올반 2016. 9. 12. 18:55
개요 : 총 문제 15문제 맞춘 문제 10문제 4. 1000개의 동전을 반씩 나누면서 올려놓으면 10번만 반복하면 모든 경우를 탐색할 수 있다. 이진탐색과 같다고 생각하면 된다. 7. '정'은 3등이 될 수 없음(2명이 지목) -> 따라서 경우의 수는 하나밖에 없다. 병이 3등, 을이 1등, 갑이 2등. 8. 1~199 : 111개, 2~~ : 111개, 3~~ : 111개, 4 40 401 402 403 404 405 406 407 408 409 41 410 411 412 413350번째는 413이 온다. 10. 두자리수 정수의 세제곱이므로 : (10a+3)^3 = ...+270a+27 => 끝자리가 7이어야 한다. a=5, 답 : 1953. 12. KOI수열의 점화식을 세워보면 : D[i] = D[i..
-
(이산수학-1차시) 2015~2016 시도예선 중고등부 문제 오답노트알고리즘/정올반 2016. 9. 4. 18:14
(문제는 https://www.digitalculture.or.kr/koi/selectOlymPiadDissentList.do 에서 다운받으실 수 있습니다.)개요: 총 문제 15문제 맞춘 문제 11문제 3. a,b,c,d 네 정수는 무조건 1 이상이어야 하므로 주어진 식을 이렇게 바꿀 수 있다.(a-1)+(b-1)+(c-1)+(d-1)=6 => A+B+C+D=6여기서 6이란 숫자를 6개의 공으로 생각하고, A,B,C,D를 구역으로 생각한다. 이 구역 각각에는 공이 안들어가도 상관 없다.구역 사이에 칸막이 'I'가 있다고 하면, 칸막이는 총 3개가 있는 셈이다.이세 9개의 칸에 공6개와 칸막이 3개를 자유롭게 배치하는 경우의 수를 구하면 된다.ex)00I0II000 => A구역에 공2개, B구역에 공1개,..
-
(1차시) 유전 알고리즘알고리즘/정올반 2016. 9. 4. 17:39
1차시 - 권욱제 선배님의 『유전 알고리즘을 이용한 자동 주행 시뮬레이션』 사용 언어, 엔진 : c++, cocos2d -유전 알고리즘 머신러닝의 알고리즘 중 하나. 다윈의 적자 생존 이론을 기본 개념으로 한다. 처음 무작위 유전자들을 세대를 거듭할수록 문제 해결에 가까워질 수 있도록 해준다.-용어 정리1. 염색체 : 유전정보를 담고 있는 데이터 집합2. 유전자 : 염색체를 구성하는 요소3. 초기화 : 문제 해결을 위해 임의로 염색체를 만드는 과정4. 선택 : 다음 세대를 생성하기 위한 염색체를 선택하는 과정5. 교차 : 선택된 유전자들을 이용해 다음 세대 염색체를 생성하는 과정6. 돌연변이 : 교차 과정에서 일정 확률로 유전자의 정보에 변형을 주는 과정 -학습 과정(1) 염색체 10개를 랜덤 생성.(1..
-
1번문제해킹/webhacking.kr 2016. 7. 17. 19:27
(사진출처 : 유한길님의 블로그) $password="????" 부터 시작하도록 하겠다. if(eregi("[^0-9,.]",$_COOKIE[user_lv])) $_COOKIE[user_lv]=1;이 말의 뜻은 : 만약 쿠키[user_lv]가 0부터 9까지의 값을 포함하지 않았다면 1로 바꿔준다는 뜻이다.그 아래는 만약 쿠키값이 6 이상이면 1로 바꿔준다는 것이고그 아래는 쿠키값이 5 이상이면 solve()를 실행한다. 즉, 6과 같거나 크지 않고, 5보다 큰 수를 쿠키값에 대입시키면 solve()를 실행시킨다는 것이다. 크롬 확장프로그램 중 EditThisCookie를 추가시켜서 쿠키값을 5 초과 6 미만인 수를 대입해 보았다.(나는 5.5를 대입해봤다.) 그리고 새로고침을 해보니 문제가 풀려있었다.
-
버퍼오버플로우 정리해킹/버퍼오버플로우 2016. 7. 17. 18:22
1. Buffer Overflow란?버퍼 오버 플로우 공격은 오래전에 발표된 기술이지만 아직까지도 사용되고 있는 공격 기법이다. 2. Buffer, 버퍼란?버퍼란 쉽게 말하면 연산 하기 전에 미리 입력받은 것을 메모리에 일시적으로 저장하는 것을 말한다.대부분의 프로그램에선 이 버퍼를 스택에다가 저장해놓는데, 이것 때문에 버퍼오버플로우 공격이 가능한 것이다. 3. Buffer Overflow의 동작 원리버퍼오버플로우는 준비된 버퍼보다 더 많은 데이터를 쓸 때에 발생하게 된다. 이 때, 스택에서 준비된 버퍼 다음에 있는 것이 base pointer, 그 다음에 있는 것이 return address이다. 이것들을 모두 조작 하고 그 다음에 있는 쉘 코드를 이용해서 명령을 내릴 수 있다. 아래 그림처럼 말이다...