Grace's Tech Blog

유클리드 호제법이란 주어진 두 수 사이에 최대공약수를 구하기 위한 알고리즘이다. 이를 통해 최대공약수를 구하면 최소공배수 역시 쉽게 구할 수 있다. 두 수 A, B가 있다고 하자. 그리고 r은 A를 B로 나눈 나머지(A%B) 라고 하자. 유클리드 호제법은 A, B, r 세 수를 가지고두 단계를 반복하는 것이다. step1. A를 B로 나누어 r을 만든다. step2. r이 0이면 이 때의 B가 최대공약수이고, r이 0이 아니면 B의 값은 A가, r의 값은 B가 되어 step1~step2를 반복한다. (언제까지?? r이 0이 되어서 B라는 최대공약수를 구할 때까지) 구현 위의 방법을 구현하는 방식은 2가지가 있다. 1) 반복문을 이용한 방법 while(1){ let r = A%B; if(r===0){ re..

1. 정렬이란, 특정 기준을 적용하여 나열하는 것입니다. ex) 3 4 1 2 →오름차순 정렬→ 1 2 3 4 2. 정렬 알고리즘의 효율성을 판단하는 기준 비교 횟수 데이터가 정렬될 때 이동하는 횟수 사용되는 메모리 양 선택정렬 1) 원리: 정렬이 완료 된 것(bar 왼쪽)과 아닌 것(bar 오른 쪽)을 나누는 기준인 bar가 시작할 때 맨 앞에 있다고 생각합니다. 즉, 시작 할 때는 bar 왼쪽에 아무 원소도 없으니 '아 아직 정렬 된 게 아무 것도 없구나' 라는 의미가 되는 것입니다. 본격적으로 (오름차순)정렬 시에는 그 bar의 오른쪽에 있는 원소들 중 가장 최소 값을 찾고, 찾은 최소값을 bar가 있는 원소의 자리와 바꾸어줍니다. 이렇게 원소 하나의 자리를 찾아 주었다면 bar를 한 칸 옆으로 이..

3. k 번째 큰 수 현수는 1부터 100사이의 자연수가 적힌 N장의 카드를 가지고 있습니다. 같은 숫자의 카드가 여러장 있을 수 있습니다. 현수는 이 중 3장을 뽑아 각 카드에 적힌 수를 합한 값을 기록하려 고 합니다. 3장을 뽑을 수 있는 모든 경우를 기록합니다. 기록한 값 중 K번째로 큰 수를 출력 하는 프로그램을 작성하세요. 만약 큰 수부터 만들어진 수가 25 25 23 23 22 20 19......이고 K값이 3이라면 K번째 큰 값 은 22입니다. ▣ 입력설명 첫 줄에 자연수 N(3

2. k번째 작은 수 N개의 숫자로 이루어진 숫자열이 주어지면 해당 숫자열중에서 s번째부터 e번째 까지의 수 중 k번째로 작은 수를 출력하는 프로그램을 작성하세요. ▣ 입력설명 첫 번째 줄에 테스트 케이스 T(1

inflearn의 파이썬 알고리즘 문제풀이 를 시작했습니다. 1. k번째 약수 어떤 자연수 p와 q가 있을 때, 만일 p를 q로 나누었을 때 나머지가 0이면 q는 p의 약수이다. 6을 예로 들면 6÷1=6...0 6÷2=3...0 6÷3=2...0 6÷4=1...2 6÷5=1...1 6÷6=1...0 그래서 6의 약수는 1, 2, 3, 6, 총 네 개이다. 두 개의 자연수 N과 K가 주어졌을 때, N의 약수들 중 K번째로 작은 수를 출력하는 프로그램을 작성하시오. ▣ 입력설명 첫째 줄에 N과 K가 빈칸을 사이에 두고 주어진다. N은 1 이상 10,000 이하이다. K는 1 이상 N 이하이다. ▣ 출력설명 첫째 줄에 N의 약수들 중 K번째로 작은 수를 출력한다. 만일 N의 약수의 개수가 K개보다 적어서 K..

1. Brute-Force Algorithms이란, 완전 탐색 알고리즘으로 모든 경우를 시도해봄으로써 답을 구한는 알고리즘이다. 완전 탐색을 하기에 간단한 경우는 모든 경우를 얼마나 돌아야 하는지 알고 있을 때이다. 예를 들어, N개의 숫자 중에서 최소값을 구하라 는 문제가 있고, N가 N개의 숫자가 입력으로 주어진다면 mini = arr[0] for(let i=0; i arr[i]){ mini = arr[i]; } } 로 단순히 하나하나 모든 숫자를 비교할 수 있을 것이다. 그러나 이런 경우가 아닌 문제가 까다로운 것이다. 2. Advanced Brute-Force Algorithms 예를 들어, N개의 알파벳 중에서 r개를 나열할 수 있는 경우를 모두 출력하시오 와 같은 문제라면, r이 달라짐에 따라..