원당컴퓨터학원

크루스칼 알고리즘이란? 그래프 내의 모든 정점들을 가장 적은 비용으로 연결 하기 위해 경로를 찾을 때 사용되는 알고리즘입니다. 즉 그래프에는 노드(node)와 엣지(edge)가 있으며 엣지에는 가중치가 포함되어 있습니다. 이러한 그래프에서 모든 정점을 포함하고 사이클(Cycle)이 없는 연결선을 그렸을 때 가중치의 합이 최소가 되는 값을 구할 때 사용합니다. 크루스칼 알고리즘은 다음과 같은 단계로 구합니다. 1단계 : 각 정점 하나만을 포함하는 n개의 집합을 만듭니다. 2단계 : 모든 간선을 가중치 값을 기준으로 오름차순으로 정렬합니다. 3단계 : 가중치가 가장 작은 것 부터 검사하여 간선이 서로소(disjoint)인 두 집합을 연결하면 그 간선을 추가하고 연결된 두 집합을 하나의 집합으로 연결 합니다...

1. 트리의 개념 루트(root)라는 특별한 노드(Node)를 갖고 그래프를 구성하는 꼭짓점 u,v 간에 단순 경로가 존재하는 비순환 연결 그래프를 트리(Tree)라고 한다. 예) 오른쪽 트리(Tree) 를 기준으로 개념이해 루트(Root)노드 : 트리의 가장 높은 곳에 위치하는 시작 노드인 A 부모(Parent)노드 : 트리를 구성하는 임의의 노드의 한단계 상위노드 (예- B,C,D의 부모 노드는 A) 자식(Child)노드 : 트리를 구성하는 임의의 노드의 한단계 하위노드(예-B의 자식 노드는 E,F) 형제(Sibling)노드 : 트리를 구성하는 임의의 노드와 부모가 같은 노드(예-E의 형제는 F) 리프(Leaf)노드 : 트리를 구성하는 임의의 노드중 자식이 없는 노드(예-E,F,C,G) 중간(Inte..

길동이가 사는 마을은 7일에 한번씩 장이 열립니다. 즉 1일에 장이 열렸다면 그 다음 장은 8일에 열립니다. 원당이가 사는 마을은 5일에 한번씩 장이 열립니다. 즉 1일에 장이 열렸다면 그 다음 장은 6일에 열립니다. 길동이가 사는 마을과 원당이가 사는 마을에서 오늘 장이 열렸습니다. 그렇다면 몇일 후에 길동이가 사는 마을과 원당이가 사는 마을에서 같은 날짜에 장이 열릴까요? 문제풀이) 이 문제는 5와 7의 최소 공배수를 찾는 문제입니다. 최소 공배수를 찾는 알고리즘은 a * b / 최대공약수(a,b) 입니다. 최대공약수를 찾는 알고리즘은 유클리드 호제법을 이용해서 a와 b의 최대 공약수는 b와 a를 b로 나눈 나머지의 최대공약수와 같다고 정의 할 수 있습니다. 따라서 최대공약수를 구하는 알고리즘을 C언..

https://ko.khanacademy.org/math/kor-2nd-1/x6a6e0d447699d993:2-1-1/x6a6e0d447699d993:2-1-1-5/e/hundreds--tens--and-ones 백의 자리, 십의 자리, 일의 자리 (연습) | 1. 세 자리 수 | Khan Academy 수학, 예술, 컴퓨터 프로그래밍, 경제, 물리학, 화학, 생물학, 의학, 금융, 역사 등을 무료로 학습해 보세요. 칸아카데미는 어디에서나 누구에게나 세계 최고의 무료 교육을 제공하는 미션을 가진 ko.khanacademy.org ​ 100 ~ 999 사이의 숫자에서 1의 자리,10의 자리,100의 자리를 찾는 연습을 해 봅니다. ​ 만약 234에서 백의 자리는 2,십의 자리는 3, 일의 자리는 4입니다...

1. 중심극한정리(central limit theorem)란? 확률론과 통계학에서 중심극한정리는 동일한 확률분포를 가진 독립확률변수 n개의 평균의 분포는 n이 적당히 크다면 정규분포에 가까워진다는 정리이다. 이 의미는 다음과 같다. 모집단이 있을 때 여기서 30개의 샘플을 뽑아 표본을 만든다. 그 다음 표본의 평균을 계산한다. 이런 과정을 여러 번 반복해서 1000개의 평균을 만들어 놓는다. 그리고 이 1000개의 평균을 히스토그램으로 그리면 놀랍게도 정규분포를 따른다. 현실에서는 표본을 수집하는 일에 비용이 많이 들지만 파이썬 프로그램을 사용해 이런 과정을 간단히 묘사할 수 있다. 예를 들어 남산도서관 대출데이터를 가지고 확인을 해 보자. 혼자공부하는데이터분석 에서 제공하는 자료 ( https://bi..

저울 문제란? 일명 천칭문제라고도 불리우는 양팔저울 혹은 전자저울을 이용하여 문제를 풀어나가는 문제를 의미한다. 전자 저울은 무게를 수치로 정확하게 잴 수 있지만 대개 1번 등의 매우 적은 횟수로만 무게를 판별하라고 한다. 또 무게를 비교하는 용도로는 양팔 저울에 비해 약간의 응용이 필요한 문제들이 출제되고 있다. 양팔 저울은 무게를 수치로 정확하게 잴 수 없는 대신 횟수는 3번 정도는 주어지는 편이다. 무게의 상대적 가벼움과 무거움을 재는 데에는 유리하지만 수치적으로 나열하기는 어렵다는 특징이 있다. 저울 관련한 유형은 최적화의 개념이나 부등식의 성질을 이해하여 해결하는 문제로 교과나 경시에서 관련 문제가 자주 출제 된다. 문제1) 크기와 모양이 같은 공 11개가 있다. 이 공들 중 무게가 다른 공은 ..

부분합 알고리즘이란? N명의 시험 성적을 내림차순으로 정렬해 둔 score[] 가 있다고 하면 여기서 우리는 a등에서 b등까지의 평균을 구하려고 한다. 가장 간단한 알고리즘으로는 a등부터 b등까지의 합을 구한 다음 b - a + 1 로 나누는 것이다. 하지만 이렇게 구하는 횟수가 빈번해진다고 하면 1회를 구할 때마다 최대 N번씩 반복하게 된다. 이럴 때 유용하게 사용하는 것이 부분합(Partial sum)이다. 위와 같이 psum 테이블을 미리 구해 놓는다고 하면 2번지 부터 4번지까지의 부분합을 구하려고 하면 psum[4] 는 0,1,2,3,4 의 모든 합이기 때문에 여기서 0,1 의 값을 빼면 2번지부터 4번지 까지의 부분합이 된다. 따라서 psum[4] - psum[1] 의 값이 2번지 부터 4번지..

1. 누적분포란 평균이 0이고 표준편차가 1인 정규분포를 표준정규분포라고 한다. 평균이 0이고 표준편차가 1인 z점수 공식에 대입하면 z = x 가 된다. 따라서 표준 정규분포는 z 점수를 사용해 전체 데이터가 어떻게 분포되어 있는지 나타낼 수 있다. 예를 들어 표준정규분포에서 z 점수가 1.0 이내에 위치한 샘플은 전체의 약 68%에 해당한다. z점수 2.0 이내에 위치한 샘플은 95%에 해당한다. 여기서 x축은 샘플값 또는 z점수, y축은 샘플의 등장 빈도 또는 밀도가 된다. 그럼 z 점수 1.5 이내에 있는 샘플의 비율은 얼마나 될까? 2. 누적분포 구하기 누적분포는 주어진 확률이 특정 값보다 작거나 같은 확률을 나타내는 값이다. 가령 표준정규분포에서 평균 0 까지 누적분포는 정확히 50%가 될것이..

방정식이란? 기본적인 연산을 할 때 구체적인 수들을 볼 수 있어요. 가령 23 + 5 = 28 과 같이 계산이 되는 것을 볼 수 있습니다. 대수의 세계로 들어가면서 변수라는 개념을 다루게 됩니다. 변수란 바뀔 수 있는 값이나 식을 의미합니다. 예를 들어 x + 5 라고 쓴다고 하면 x 의 값에 따라 결과값은 달라 집니다. 이러한 것은 하나의 식이라고 합니다. 여기서 식과 방정식의 차이를 확인해 보겠습니다. 식은 단지 어떤 값을 나타내는 표현입니다. 예를들어 x + 5 라는 식은 x의 값에 따라 결과값이 바뀔것입니다. 방정식의 경우는 식이 서로 같다고 가정하고 시작합니다. 예를 들어 x + 5 = 10 이라고 하면 한개의 값을 모르는 상황에서 x의 값을 알아낼 수 있습니다. 이렇게 미지수가 포함된 식에서 ..

조합탐색이란? - 완전 탐색 알고리즘은 대개 답을 만드는 과정을 여러개의 선택으로 나눈 뒤 재귀 호출을 이용해 각각의 선택지를 채워가는 형태로 구현됨 - 기존 완전 탐색은 모든 답을 다 만들어 보면서 문제를 해결하므로 완전 탐색의 수행시간은 탐색 공간의 크기에 직접적으로 비례 - 이는 문제의 규모에 따라 기하급수적으로 크기가 증가. - 조합탐색이란 완전 탐색을 포함해 유한한 크기의 탐색 공간을 뒤지면서 답을 찾아 내는 알고리즘 목표 - 기본적으로 모두 최적해가 될 가능성이 없는 답들을 탐색하는 것을 방지하여 만들어 봐야 하는 답의 수를 줄이는 것을 목표로 함 조합탐색 최적화 기법 - 가지치기 : 탐색 과정에서 최적해로 연결될 가능성이 없는 부분을 잘라낸다. 예) 외판원 문제에서 길이가 10인 경로를 이미..