코드 챌린지 2일차 - 유클리드 호제법, 소수 판별법

유클리드 호제법 - 최대 공약수를 구할 때 사용한다.

N의 약수 찾기
1 ~ N까지 나누어서 나머지가 0이 되는 수의 개수 찾기 = 복잡도 N

호제법 - 서로 나눈다!
두 자연주 a,b에 대해 (a>b) a를 b로 나눈 나머지를 r이라 하면 a,b의 최대 공약수는 b와 r의 최대 공약수와 동일하다.
b를 r로 나눈 나머지 r'를 구하고 다시 r을 r'으로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대 공약수이다.

1071과 1029를 구하자!
1071 % 1029 = 42
1029 % 42 = 21 
42는 21로 나누어 떨어지므로 최대 공약수는 21이다! 

코드로 구현하자! 

def GCD(a,b):
	while b:
    	a,b = b,a%b
    return a

GCD - 최대 공약수
LCM - 최소 공배수 

LCM(a,b) = a*b / GCD(a,b)
어떠한 두 수의 곱은, 그 두 수의 최대공약수와 최소 공배수의 곱과 같다.

gcd는 파이썬 3.5, lcm은 파이썬 3.9 이상부터 지원한다.

import math

math.gcd(10,3)
math.lcm(5,2)

이렇게 사용이 가능하다.

 

소수 판별법 

소수 - 1과 자기 자신만으로만 나누어지는 수이다 == 약수가 2개이다.
1은 소수, 합성수도 아니다.

에라토스테네스의 체 - 소수가 아닌 것을 체로 걸러낸다.
1. 2부터 N까지 모든 정수를 적는다.
2, 아직 지우지 않은 소수 중 가장 작은 소수를 찾는다. 이 수를 P라고 한다.
3. 아직 지우지 않은 수들 중 P의 배수를 크기 순서대로 지운다.
4. 아직 모든 수를 지우지 않았다면, 다시 2번으로 돌아간다.
O(N log(log N))의 시간 복잡도를 가진다.

for i in range(2,N+1):
	# 아직 지우지 않은 수 중 가장 작은 소수를 찾는다.
	if os_prime[i]:
    	for J in rnage(i*1, N=1, i):
        	# j가 소수가 아님을 is_prime 배열에 체크한다.
        	if is_prime[j] : is_prime[j] = False

bool 자료형인 is_prime 안의 모든 요소들에 대하여, 처음에 True로 초기화 후 배수들을 빠르게 처리하여 남은 값들은 소수가 된다.

 

 

정리 정돈을 좋아하는 k씨

• 시간 제한: 1초

정리 정돈을 좋아하는 k씨의 본명은 아무도 모릅니다. 사람들은 k씨의 특이한 행동 2가지 때문에 그를 '정리 정돈을 좋아하는 k씨'라고 부릅니다. 그 두 가지 행동은 그가 숫자를 정리하는 일을 하면 아무 규칙없이 나열되어 있는 숫자중 범위를 정한 후 무조건 오름차순으로 정리한다는 것, 그리고 오름차순으로 정리된 숫자 중 k번째 숫자를 선택한다는 것입니다

예를 들어 a={1,7,6,8,1,6,4,5}라는 수열이 있습니다. 정리정돈을 좋아하는 k씨는 범위를 2에서 5로 정하고, k를 2라고 정했습니다.
그러면 ka​={7,6,8,1}이 되고, 이것을 오름차순으로 정리를 하면 ka​={1,6,7,8}이 됩니다. 그리고 k씨는 2번째인 6을 선택합니다.

배열 a가 주어지고, k씨가 일을 한 횟수가 주어졌을 때, k씨가 고른 숫자를 출력하는 프로그램을 작성하세요.

 

지시사항

입력

• 첫째 줄에 배열의 크기인 정수 n과 k씨가 일한 횟수인 정수 m을 입력합니다.
  
  1≤n≤10000
  
  
  1≤m≤500
• 둘째 줄에는 배열에 포함된 정수를 순서대로 입력합니다. 각 정수는 절댓값이 200을 넘지 않는 정수입니다.
• 다음 줄 부터 m개 줄에 걸쳐 k씨가 고른 범위인 정수 i, j와 정수 k를 입력합니다.
  
  1≤i≤j≤n
  
  
  1≤k≤j−i+1

출력

• k씨가 일할 때마다 k씨가 선택한 숫자를 한 줄에 하나씩 출력합니다.

입력 예시

8 3
1 7 6 8 1 6 4 5
1 5 3
2 6 2
4 8 3

출력 예시

6
6
5

 

n,m = map(int, input().split())
num = [0] * n
num = list(map(int, input().split()))  # 한 줄의 숫자들을 입력받음
a = [0]*3

for i in range (m):
    a =  list(map(int, input().split()))
    b = [0] * (a[1] - a[0] + 1)
    b = num[a[0]-1 : a[1]]
    b.sort()
    #print(b)
    print(b[a[2]-1])

단순하게 풀긴 했는데 다른 방식이 있을지는....

입력에 자꾸 기억이 안나는게 크네요 ..ㅠ 

 

C++

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

vector<int> seq;
int main() {
  int n, m, i, j, k, tmp;
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    cin >> tmp;
    seq.push_back(tmp);
  }
  for (int cnt = 0; cnt < m; cnt++) {
    cin >> i >> j >> k;
    vector<int> part = vector<int>(seq.begin() + i - 1, seq.begin() + j);
    sort(part.begin(), part.end());
    cout << part[k - 1] << endl;
  }
}

Python

def main():
	import sys
	input = sys.stdin.read
	data = input().split()

	n = int(data[0])
	m = int(data[1])
	seq = [int(data[i + 2]) for i in range(n)]

	index = 2 + n
	results = []

	for _ in range(m):
		i = int(data[index])
		j = int(data[index + 1])
		k = int(data[index + 2])
		part = sorted(seq[i - 1:j])
		results.append(part[k - 1])
		index += 3

	for result in results:
		print(result)

if __name__ == "__main__":
	main()

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        List<Integer> seq = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            seq.add(sc.nextInt());
        }
        for (int cnt = 0; cnt < m; cnt++) {
            int i = sc.nextInt();
            int j = sc.nextInt();
            int k = sc.nextInt();
            List<Integer> part = new ArrayList<>(seq.subList(i - 1, j));
            Collections.sort(part);
            System.out.println(part.get(k - 1));
        }
        sc.close();
    }
}