원당컴퓨터학원

유니온파인드(Union Find)란 - 대표적인 그래프 알고리즘으로 합집합 찾기 라는 의미를 가지고 있다. - 상호배타적집합(Disjoint-set) 이라고도 한다. - 여러개의 노드가 있을때 두개의 노드가 같은 그래프에 속하는지 판별하는 알고리즘 - 2가지 연산으로 이루어져 있다. 단계 1. 주어진 원소들이 서로 같은 집합에 속하는가를 알아내고(Find) 단계 2. 만약에 그렇지 않으면 같은 집합에 속하도록 추가하라(Union) 유니온파인드 구현방법 예) 위와 같은 경우 union(1,5),union(4,5),union(2,3),union(2,7),union(3,7),union(6,7) 을 표현한 그래프 이러한 그래프에 connected component 는 {0},{1,4,5},{2,3,6,7} 이렇..

1. 수의 나누어 떨어지는 성질 성질1 : 만약 a,b,c 가 모두 c 에 의하여 나누어 떨어지면 그들의 합과 차도 모두 c에 의하여 나누어 떨어집니다. 즉 만약 c|a,c|b 이면 c|(a±b) 도 성립됩니다.(단, 여기서 c|a 의 의미는 a가 c로 나누어 떨어진다는 의미입니다.) 예) 2|10,2|6 이면 2|(10+6), 2|(10-6) 입니다. 성질2 : 만약 b와 c의 곱이 a를 나누어 떨어지게 하면 b와 c도 a를 나누어 떨어지게 할 수 있습니다. 즉 만약 bc|a 이면 b|a,c|a 도 성립합니다. 예) 2*5|30 이면 2|30,5|30 이 성립됩니다. 성질3 : 만약 b와 c가 모두 a를 나누어 떨어지게 하고 b와 c가 서로소이면, b와 c의 곱도 a를 나누어 떨어지게 합니다. 즉 b|..

조합은 Combination 이라고 하며 순서를 생각하지 않고 나열하는 경우를 말한다. 즉 123 과 321 은 같은 경우로 생각하는 경우이다. 이러한 문제는 중고등부 유형이나 혹은 알고리즘 유형에서 나오는 문제이다. 다음의 문제를 풀어 보자. 문제풀이) 더보기 1) 남자 13명 중에서 3명을 뽑는 경우의 수는 첫번째 13명중에서 1명을 뽑는 13가지 두번째 첫번째 뽑힌 사람을 제외하고 12명 중에서 1명을 뽑는 12가지 세번째 는 남은 11명 중에서 1명을 뽑는 11가지 즉 13P3 = 1716 이다. 여기서 남자에게 번호를 1~13까지 번호를 붙여 본다면 1번,2번,3번을 선택한 경우는 123,132,213,231,312,321 과 같이 6가지이다. 하지만 이렇게 6가지의 경우는 동일하게 하나로 선택..

더보기 문제풀이) 더보기 2학년부터 4학년 학생중 학점이 3.0 이상인 학생은 2학년 - 22명 3학년 - 28명 4학년 - 18명 2학년 3.0 이상인 학생이 3학년 3.0 또는 4학년 3.0 이상인 학생과 중복 되는 경우가 없으므로 경우의 수는 22 + 28 + 18 = 68 가지 이다. [문제풀이] 더보기 문제풀이) 더보기 1) 한가지만 선택하는 경우이므로 한가지를 선택하면 다른 것을 선택 할 수 없다. 따라서 합의 법칙에 해당한다. 5+2+4+3 = 14 2) 각각 하나씩 선택을 해야 하므로 곱의 법칙에 해당한다. 5 * 2 * 4 * 3 = 120 문제풀이) 더보기 첫째자리에 4가지를 선택 할 수 있다. 둘째자리에 첫째자리에서 선택한 1가지를 제외한 3가지를 선택할 수 있다. 셋째 자리에 첫째자..

숫자로 진을 만드는 것은 일정한 조건에 맞게 여러가지 도형으로 배열하는 문제입니다. 숫자진은 일종의 숫자 그림으로 숫자진 그림에 관한 문제의 종류는 다양하지만 여기서는 밀봉형 숫자진,부채꼴 숫자진,복합형 숫자진에 대해서 알아 보겠습니다. 1. 1~8의 8개의 자연수를 각각 아래 그림의 8개의 동그라미 안에 써 넣어 사각형 각 변 위의 3개의 숫자의 합이 모두 14가 되게 하고, 또한 숫자 1은 사각형의 한 꼭짓점 위에 있게 하려고 합니다. A의 위치에는 어떤 숫자가 들어가겠습니까?(숫자만 입력하세요.) 문제풀이) 더보기 왼쪽 상단 1 위치부터 시계 방향으로 a,b,c,A,d,e,f 로 그림을 그려 보면 1 + a + b = 14 --(1) b + c + A = 14 --(2) A + d + e = 14 ..

1. 도형의 둘레 - 사각형의 둘레 구하기 사각형 둘레는 a + a + b + b 이므로 2 * (a+b) - 삼각형의 둘레 구하기 삼각형의 둘레는 a + b + c ※ 여기서 피타고라스 정리에 의해 직각 삼각형의 빗변 c의 제곱은 다른 두변 a,b의 제곱의 합과 같다 증명) 이렇게 연장선을 그려서 하나의 정사각형을 만들어 보자. CDFH 의 넓이 = 삼각형 ABC의 넓이 * 4 + 사각형 AEGB의 넓이 CDFH 의 넓이 = (a+b)^2 = a^2 + 2ab + b^2 사각형 AEGB의 넓이 = c * c 삼각형 ABC의 넓이 = a * b / 2 이므로 a^2 + 2ab + b^2 = c * c + 4 * a * b / 2 따라서 a^2 + b^2 = c^2 - 원의 둘레 원의 둘레는 원의 반지름과..

정의 스택은 top 이라고 하는 한쪽 위치에서 모든 삽입(push)과 삭제(pop)가 일어나는 순서 리스트 입니다. 후입선출(Last In First Out : LIFO) 의 특징을 가지고 있습니다. 스택에 원소 삽입 및 삭제 top 위치는 다음 데이터를 넣을 수 있는 위치를 가르킨다. push() 에서 top의 위치에 데이터를 입력 후 다음 데이터를 넣을 수 있는 위치로 이동한다. pop() 에서는 top의 위치를 이전의 위치로 먼저 이동 후에 그 위치의 값을 반환한다. 스택의 ADT(추상데이터타입) structure Stack objects: 0개 이상의 원소를 가진 유한 순서 리스트 functions: 모든 stack∈ Stack, item∈ element, max_stack_size∈ positi..

1. 확률의 정의 확률(Probability) : 표본공간 S 중에서 특정 사건 A 가 일어날 가능성 P(A) =\(|A| \over |S| \) 여기서 P(A) 는 0과 1 사이의 실수 |A| 는 특정사건 A가 일어나는 경우의 수 |S| 는 표본공간 S가 일어나는 경우의 수(전체사건이라고도 함) 예) 주사위 두 개를 던질 때 두 수의 합이 3 이하가 나올 확률은 다음과 같이 구한다. 주사위 두개를 던질 때 나오는 모든 경우의 수 (표본공간 S가 일어나는 경우의 수 |S| ) = 6 * 6 = 36가지 두 수의 합이 7 이하가 나오는 경우의 수(특정 사건 A가 일어나는 경우의 수 |A|) = (1,1),(1,2),(2,1) = 3가지 따라서 P(A) = \( 3 \over 36 \) = \( 1 \ove..

목표 행렬 연산을 이해한다. 행렬의 선형변환에 대해 이해한다. 역행렬및 전치 행렬에 대해 이해한다. 행렬이란 n,m이 양의 정수일때 n행 m열로 나열된 실수의 2차원 배열을 행렬이라 합니다. 행렬의 덧셈과 뺄셈 두 행렬 A,B에서 같은 자리에 있는 원소들끼리 더하거나 빼는 연산 두 행렬의 크기가 같아야만 연산 가능함 행렬의 스칼라곱 행렬의 곱셈 n*m 행렬과 m*s 행렬의 곱은 n*s 행렬이 생성되며 A의 i번째 행과 행렬 B의 j번째 열이 서로 대응하여 연산 되기 때문에 행렬 A의 열크기와 B의 행 크기가 서로 같아야 합니다. 전치행렬 n*m 행렬을 행과 열을 바꾼 m*n 행렬을 전치행렬이라고 합니다. 예) 역행렬 정사각행렬 A에 대해 A*B = B*A = I를 만족하게 하는 행렬 B ※ I 는 단위행..

DNA의 염기서열은 adenine(A),thymine(T),guanine(G),cytosine(C) 와 같이 네가지로 구성되어 있습니다. DNA 염기서열을 연구하고 있는 원당이는 고릴라의 염기서열이 GATACCAGATACCCA 와 같이 이루어져 있고 원숭이의 염기서열이 AAGATTGCCATTATT 와 같이 이루어져 있는 것을 발견했습니다. 원당이는 고릴라와 원숭이의 염기서열을 똑같이 만들어 보고 싶습니다. 가령 GATA 의 염기서열을 AAGT 로 만든다면 GATA에서 3개를 변경해서 만들 수 있습니다. 혹은 AA 와 같이 만든다면 G와 T 두개의 염기서열을 삭제해서 만들 수 있습니다. 또는 GATAT 와 같은 경우는 T를 추가해서 염기서열을 만들 수가 있습니다. 이렇게 변경하거나 추가하거나 삭제하는 세가..