알고리즘&자료구조

    큰 수의 법칙

    1. 단순하게 푸는 방법 #N, M, K를 공백으로 구분하여 입력받기 n, m, k = map(int, input().split()) # N개의 수를 공백으로 구분하여 입력받기 data = list(map(int, input().split())) data.sort() first = data[n - 1] #가장 큰 수를 second = data[n - 2] #두번째로 큰 수를 result = 0 while True: for i in range(k): #가장 큰 수 k번 더하기 if m == 0: break result += first m -= 1 #더할 때마다 1씩 빼기 if m == 0: break result += second #두번째로 큰 수 한 번 더하기 m -= 1 #더할 때마다 1빼기 print..

    그리디 알고리즘

    개요 이름에서 알 수 있듯이 어떠한 문제가 있 을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다. 여기서 탐욕적이라는 말은 ‘현재 상황 에서 지금 당장 좋은 것만 고르는 방법’을 의미한다. 그리디 알고리즘을 이용하면 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 예제) 거스름돈 당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50 원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다. 그리디 알고리즘의 대표적인 예제로 가장 큰 단위인 500원부터 세고 남는 돈..

    최대공약수, 최소공배수 쉽게 구하기

    유클리드 호제법을 알면 최대공약수와 최소공배수 모두 쉽게 구할 수 있다. 유클리드 호제법은 GCD를 쉽게 구할 수 있는 알고리즘 중의 하나이다. 두 수 a와 b (a > b)가 있다고 할 때, a와 b의 최대공약수 G는 b와 a%b(a를 b로 나눈 나머지)의 최대공약수 G'과 서로 같다! 예시 입력으로 보면, gcd(24, 18) = gcd(18, 6) = gcd(6, 0)인 것이다! 여기서 b가 0이 되는 순간의 6이 바로 최대공약수가 된다. 이렇게 최대공약수를 쉽게 구하면, 최소공배수는 바로 구할 수 있다. 여기서 두 수 A와 B가 있다고 할 때, A와 B는 각각 x*gcd(a, b), y*gcd(a, b)이다. 따라서 A*B/gcd(a, b)를 해주면 최소공배수가 된다! 이 수가 최소공배수인 이유는..

    약수로 원래수 구하기

    약수로 원래수를 구하는 방법은 1과 자기자신을 제외한 가장 작은 약수와 가장 큰 약수를 곱하면 된다. 숫자 12를 예로 들어보면, 12의 약수는 1, 2, 3, 4, 6, 12이고, 1과 자기자신을 제외하고 약수는 2,3,4,6 일 것이다. 여기서 2와 6을 곱하면 원래의 수인 12가 구해진다.

    백준 4948번: 베르트랑 공준 - 합성수의 성질을 이용해서 간단히 풀기

    문제 베르트랑 문제는 숫자를 입력 받았을때 그 숫자보다 크고 그 숫자의 두배보다 작거나 같은 범위안에서 소수가 몇개인지 파악하는 문제이다. 해결법 1) 범위 안의 숫자를 1부터 탐색하여 하나하나 소수를 찾는 법 이 방법은 가장 간단한 방법이다. 하지만 문제는 시간복잡도가 크다는 것이다. 백준에서 해당 방법으로 풀어서 제출하면 시간이 초과했다는 결과가 뜬다. 따라서 다른 방법을 찾아야 할 필요성이 있다. 2) 합성수의 성질을 이용한 방법 우선 합성수가 무엇인지 알아야 한다. 합성수란 소수가 아닌 나머지 자연수를 말한다. 즉 1과 자기자신을 제외하고 또 다른 약수가 존재하는 수이다. 여기서 합성수가 될 수 있는 조건을 알고나면 문제를 간단하게 풀 수 있게 된다. 합성수는 2부터 해당 합성수의 제곱근까지 범위..

    이진탐색 (binary search, 파이썬)

    알고리즘 우리가 범위를 세울 때 쓰는 최솟값과 최댓값을 변수로 놓습니다. 현재 시도하는 인덱스 또한 변수로 잡습니다. 그리고 시도했을 때 target 보다 작다면 더 큰 값들을 뒤져야 하니까 최솟값에 시돗값 + 1 을 대입합니다. 만약 시도했을 때 target 보다 크다면 더 작은 값들을 뒤져야 하니까 최댓값에 시돗값 - 1 을 대입하면 됩니다. 이를 최솟값 ≤ 최댓값 까지 반복해야 합니다! 왜 < 가 아니라 ≤ 냐면 최솟값 == 최댓값인 시점까지 확인을 해야 하기 때문입니다. def is_existing_target_number_binary(target, array): current_min = 0 current_max = len(array) - 1 current_guess = (current_min +..

    문자열 안에서 최빈값 찾기 (파이썬)

    1. a부터 z까지 저장될 배열을 선언한다 alphabet_array = [0] * 26 2. 최빈값을 구하는 함수를 우선 작성한다. def find_max_occurred_alphabet(string): return 3. 입력받은 문자열을 처음부터 돌면서 공백문자가 없는 값들을 찾아내 아스키 코드를 사용하여 a를 0을 기준으로 만들어 인덱스에 넣어줄 값을 만든다. 그 후 처음 선언한 배열에서 해당 인덱스의 값을 반복하여 1씩 증가시킨다. for list in string: if list.isalpha() == True: array_num = ord(list) - ord('a') alphabet_array[array_num] += 1 4. alphabet_array의 길이만큼 탐색하여 0부터 시작하는 맥..