원당컴퓨터학원

1. n진법 n진법이란 0과 n-1 사이의 숫자들을 이용해 수를 표현하는 방식입니다. 즉 우리가 사용하는 10진법은 0~9까지의 수를 사용하며 컴퓨터가 사용하는 2진법은 0~1 까지의 수를 사용합니다. n진법을 사용한다면 n을 기수(Base Number) 라고 합니다. 기수표기 예) 10진수 1234 : 1234(10) 2진수 1010 : 1010(2) 2. 10진수(Decimal Number) 10진수는 기수를 10으로 하는 수 체계이며 0과 9 사이의 숫자를 이용해 수를 표현합니다. 또한 10진수는 정수 1234 에 대해 다음과 같이 표현 할 수 있습니다. 1234(10) = 1*103 + 2*102 + 3*101 + 4*100 즉 오른쪽 부터 왼쪽으로 기수의 0승 , 기수의 1승 ,기수의 2승 자리..

동적계획법 알고리즘이란 동적계획법은 문제의 최적해를 구하거나 답의 개수를 세는 과정에 사용하는 알고리즘 설계기법 - 전체 문제를 작은 문제로 단순화 한 다음 점화식으로 만들어 재귀적인 구조를 활용해서 전체 문제를 해결하는 방식 동적계획법 알고리즘 설계 방법 1. 전체 문제를 작은 문제로 단순화한다. -> 부분문제를 정의 2. 재귀적인 구조를 활용할 수 있는 점화식을 만든다. 3. 작은 문제를 해결한 방법으로 전체 문제를 해결한다. 메모이제이션 기법 메모이제이션(Memoization)은 동적계획법에서 아주 중요한 개념이다. 함수의 값을 계산한 뒤 계산된 값을 배열에 저장하는 방식이다. 이러한 메모이제이션은 필요한 때마다 함수를 다시 호출하지 않고 값을 빠르게 가져 올 수 있다. 동적알고리즘 예시문제 www..

참고문제 : https://ko.khanacademy.org/math/kor-1st-2/xdffa2afcc11cd098:1-2-1/xdffa2afcc11cd098:1-2-1-8/v/introduction-to-even-and-odd 짝수와 홀수에 대해 배우고 어떤 수가 짝수인지 또는 홀수인지 알아내는 방법을 살펴 봅니다. ​ 짝수란? 도넛이 여러개 있을 때 두명에게 똑같이 나누어 줄 수 있으면 짝수, 그렇지 않으면 홀수라고 합니다. 즉 짝수는 2의 배수입니다. ​ 작품소개 처음시작하면 엔트리봇이 어떤 수를 생각하고 그 수가 짝수인지 홀수인지를 묻습니다. 만약 31은 짝수인지 홀수인지 맞혀보세요? 라고 말했을 때 홀수라고 말하면 정답입니다. 틀리면 틀렸습니다. 를 말합니다. ​ 알고리즘 수,정답 의 변수를..

점화식이란 수열에서 이웃하는 두개의 항 사이에 성립하는 관계를 나타내는 관계식이다. 즉, 수열 { an }의 각 항 an 이 함수 f를 이용해서 f(an) = an+1 과 같이 귀납적으로 정의 될때 f를 수열 {an}의 점화식이라고 하며 또한 수열 {an}은 점화식 f로 정의 된다고 한다. 예) 하노이의 탑 유명한 하노이이탑 문제는 n개의 원판을 이동하는 회수를 수열 an으로 정의 하면 n개의 원판을 이동시키기 위해서는 그 위쪽 n-1개의 원판을 다른 막대로 이동한 후, 맨 아래쪽 원판을 이동하고 다시 n-1개의 원판을 이동해야 하므로 다음과 같은 점화식이 성립함을 알수 있다. f(n) = f(n-1) + 1 + f(n-1) = 2*f(n-1) + 1 = 2^n - 1 (단, f(1)=1) 예) 피보나치..

분할정복 알고리즘이란? 분할정복(Divide and conquer algorithm)은 그대로 해결 할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이다. 대표적인 예로 퀵정렬 또는 합병정렬과 같은 알고리즘이 있다. 알고리즘을 설계하는 요령 - Divide : 문제가 분할이 가능한 경우, 2개 이상의 문제로 나눈다. - Conquer : 나누어진 문제가 여전히 분할이 가능하면 또 다시 Divide를 수행한다. 그렇지 않으면 문제를 정복한다. - Combine : : Conquer한 문제들을 통합하여 원래 문제의 답을 얻는다. ※ 문제를 제대로 나누면 conquer 하는 것이 쉽기 때문에 Divide 를 제대로 하는것이 가장 중요하다. 분할정복 알고리즘 예 function F(x): if F(..

https://ko.khanacademy.org/math/kor-1st-2/xdffa2afcc11cd098:1-2-4/xdffa2afcc11cd098:1-2-4-6/v/getting-to-10-by-filling-boxes 오늘은 1학년 2학기에서 배우는 10보다 작은 어떤 임의의 갯수의 햄버거가 있는데 몇개를 더 더했을때 10이 되는지를 확인하는 게임을 만들어 보겠습니다. ​ 1학년 1학기에서 1부터 10보다 작은 수를 배웠는데 조금 더 확장해서 두자리수를 배우기 전에 두자리수의 처음이 되는 10이 되는 원리를 이해하고 여기에서 덧셈과 뺄셈의 개념을 이해하게 됩니다. ​ 작품소개 처음 시작하면 그릇에 임의의 갯수(1부터 9 사이)의 햄버거를 담아 놓은 다음 엔트리봇이 다음과 같이 질문을 합니다. "그릇..

등차수열이란? 앞과 뒤의 두 항의 차이가 일정한 수열을 말합니다. 11,14,17... 은 두 항의 차이(공차)가 3으로 일정한 등차 수열입니다. 이러한 등차 수열에서 n번째 항의 값 = 초항 + (n-1) * (공차) 예를 들어 1 부터 시작하는 공차 1인 수열이라면 1,2,3,... 과 같이 진행 되는데 10번째 항의 값을 구하려면 초항 1의 9번째 뒤의 값이므로 (10-1)번째 * 공차(1) 을 더해 주면 10이라는 수를 구할 수 있습니다. 등차수열의 합은 (초항 + n번째 항의값) * n(개) / 2로 확인을 할 수 있는데 이 공식은 가우스가 초등학교 3학년때 1부터 100까지의 수를 더하라는 선생님의 문제에 1과 100을 짝짓기 해서 50개를 만들어서 곱셈으로 풀었다는 그 유명한 공식입니다. 오..

1.집합(Set)이란? 명확한 기준에 의해 분류되어 공통된 성질을 가지며 중복되지 않는 원소(Element,Member)의 모임 2. 집합의 표기 방식 1. 원소나열법 : 집합에 포함되는 원소들을 일일이 나열하는 방법 예) A = {1,2,3,4,5} 2. 조건제시법 : 집합에 포함되는 원소들이 공통적인 성질을 조건식으로 제시하는 방법 예) A = {x | 0< x

컴퓨터 과학에서 접미사 배열(Suffix Array)란 어떤 문자열의 접미사를 사전식 순서대로 나열한 배열을 말한다. S = S[0]S[1]...S[n-1] 이라는 문자열이 있다고 하자. 이때 S[i,j] 는 i번째 문자부터 j번째 문자 까지 S의 부분 문자열이라고 하자. 문자열 S에 대한 접미사 배열 A는 S의 접미사들을 사전식 순서로 정렬 했을 때 접미사의 시작 위치를 저장한 정수 배열이다. 즉 A[i] 에 저장 된 내용은 사전순으로 i 번째인 S의 접미사의 시작 위치이다. 다시 말하면 문자열 S의 길이를 n이라고 할 때 , 0

문제 출처 : https://ko.khanacademy.org/math/kor-1st-1/x22720cd23d5246e1:1-1-5 5단원에서는 50까지의 수를 배웁니다. 여기서는 1부터 50까지의 임의의 수를 퀴즈를 내서 어떤 수가 큰지 맞춰 보는 게임을 만들어 보겠습니다. ​ 작품소개 엔트리봇이 시작하기를 클릭하면 1부터 50까지의 임의의 수 2개를 선택합니다. 그리고 그 두수 중 어떤 것이 큰지 정답을 말하라고 하면서 정답을 맞추면 참 잘했어요! 라고 말하면서 +10 점을 틀리면 조금 더 노력하세요! 라고 말하면서 -5점을 줍니다. ​ 총 10문제를 출제하고 마지막에 당신의 점수는 ()점입니다. 라고 말을 합니다. ​ 알고리즘 1부터 50까지의 임의의 수를 저장할 변수 두개를 선언합니다.(첫번째수,..