유클리드 호제법에 관해서 한 번 글을 썼어야 하는데 이제야 써 보네요. 유클리드 호제법은 최대공약수(GCD : Greatest Common Factor)을 구하는 알고리즘입니다. 여담으로 최소공배수는 (두 수의 곱/gcd)를 하면 되기 때문에, 따로 구할 필요가 없고 세 수의 최대공약수를 구한다 해도 gcd(gcd(a,b),c)를 하면 되므로 두 수의 최대공약수를 구하는 알고리즘에 대해서만 알아도 충분할 겁니다. 우선 위의 사진에서 최대공약수를 구하는 알고리즘을 이해할 수 있고, 이는 단순히 r = a%b 에 대해서 gcd(a,b) = gcd(b,r)임을 보이면 됩니다. 증명은 위와 같습니다. 그래서 gcd함수 부분을 코드로 구현하면 int gcd(int a, int b) { if(b == 0) { re..
우리에게 익숙한.. 중학교 1학년 때 배우는 에라토스테네스의 체 이 전에(과제할 때) 반복문을 돌려서 나머지가 0인지를 판별하는 식으로 소수를 판별했는데, https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 이번 백준 문제를 풀고 그 방식이 너무나도 느리다는걸 깨달았습니다. 그래서 나온 결론은 에라토스테네스의 체를 이용하는 방법입니다. 숫자 배열로 공간을 많이 먹기는 해도 속도는 훨 빠르더군요. #include int main(void) { int n, m; int i, j; i..
서론1등만 기억하는 세상. 학교에서 주는 문제를 풀다가 두 번째로 작은 숫자를 찾아야 했습니다. (사실 문자지만 문자나 숫자나~) 보통은 가장 큰 숫자, 가장 작은 숫자를 찾지만 두 번째라고 하니 조금 당황스러웠습니다. 본론제가 작성한 코드는 이렇습니다. 어 그러니까, char을 input해서 그 값이 대문자일 때까지 받고 종료되면 알파벳 순서대로 했을 때 가장 먼저와, 그 다음 수를 출력한다고 해봅시다. 그러면, 제가 작성한 코드는 다음과 같습니다. char input; char first_char = 124, second_char = 124; while (1) { scanf("%c",&input); if(input >= 'A' && input input) { second_char = first_cha..
요즘 다시 C 언어를 공부하는 중입니다. 표준을 지키려고 KNK의 C Programming: A Modern Approach, 2nd ed. 을 보고 있는데 역시 굉장히 좋은 책입니다. 프로그래밍 언어를 공부하는 방법으로 저는 사소한 것들도 계속 따라해보려고 하는 편입니다. 이전에 자료구조를 배우며, 정렬을 정리해본 적은 있으나 기억이 안나는 관계로.. 이 책에 나왔던 퀵 정렬을 정리해보고자 합니다. https://wikidocs.net/book/2494 C 프로그래밍: 현대적 접근 K.N.King의 유명한 책 C Programming: A Modern Approach, 2nd ed.를 한국어로 번역한 책입니다. 모든 저작권은 K.N.King에게 ... wikidocs.net Quick Sort 퀵 정렬..
제가 2019년 캠퍼스형 공동 교육과정에서 자료구조를 이수하며 정리한 것입니다. 최소 신장 트리 알고리즘 다정고등학교 이정민 - 크러스컬 알고리즘(Kruskal’s algorithm) 크러스컬 알고리즘은 변의 개수를 E 꼭짓점의 개수를 V라고 할 때 O(E log V) 의 시간 복잡도를 가진다. 크러스컬 알고리즘은 아래와 같이 작동한다. 1. 그래프의 각 꼭짓점이 각각 하나의 나무가 되도록 하는 숲A 를 만든다. 2. 모든 변을 원소로 하는 집합 S를 만든다. 3. 집합 S 가 비어있지 않는 동안 - 가장 작은 비용의 변을 S에서 하나 뺀다. - 그 변이 어떤 두개의 나무를 연결한다면 두 나무를 연결하여 하나의 나무로 만든다. - 그렇지 않다면 그 변은 버린다. 이와 다른 형태로, 변을 제거하는 방식이 ..
크러스컬 알고리즘(Kruskal’s algorithm)이란?최소 비용 생성나무를 찾는 알고리즘이라고 볼수 있다. 일단 우리는 크러스컬 알고리즘을 구현하는 방법에 대하여 알아보겠다. 크러스컬 알고리즘은 다음 순서로 작동한다 1. 그래프의 각 꼭짓점이 각각 하나의 나무가 되도록 하는 숲A 를 만든다.2. 모든 변을 원소로 하는 집합 S를 만든다.3. 집합 S 가 비어있지 않는 동안- 가장 작은 비용의 변을 S에서 하나 뺀다.- 그 변이 어떤 두개의 나무를 연결한다면 두 나무를 연결하여 하나의 나무로 만든다.- 그렇지 않다면 그 변은 버린다. 일단 위키피디아의 말을 보면 어렵게 느껴진다. 그래서 직접 문제를 가져왔다. 크리스컬 알고리즘을 실제로 사용하자! 이 문제는 정보올림피아드 2016년 중고등부 문제 7번..
