알고리즘 문제 풀이 / TIL (22-11-11)

과제로 두개의 문제를 풀어보았다. 아직 함수나 여러 기능들에 대해 잘 몰라서 그런지, 방법은 떠올랐으나 수단을 생각해내기 힘들었다. 문제에 대한 직접적인 해답말고 내가 떠올린 방법들을 구현할 수단들을 위주로 검색하여 문제를 해결해나갔다.

Q. 정수를 입력 했을 때, 그 정수 이하의 소수를 모두 반환하시오.

이 문제는 해결하였다.

input = 20

def find_prime_list_under_number(number):
    num_1 = range(2, number)
    소수 = []
    for num in num_1:
        if num == 2 or num == 3 or num == 5 or num == 7:
            소수.append(num)
        else:
            if num % 2 != 0 and num % 3 != 0 and num % 5 != 0 and num % 7 != 0:
                소수.append(num)
    return 소수

result = find_prime_list_under_number(input)
print(result)

다른 방법

input = 20

def find_prime_list_under_number(number):
    prime_list = []

    for n in range(2, number + 1):
        for i in prime_list:
            if n % i == 0 and i * i <= n:
                break
        else:
            prime_list.append(n)

    return prime_list

result = find_prime_list_under_number(input)
print(result)

Q. 0과 1로만 이루어진 문자열이 주어졌을 때, 이 문자를 모두 0, 혹은 모두 1로 같게 만들어야 한다. 할 수 있는 행동은 연속된 하나의 숫자를 잡고 모두 뒤집는 것 이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다. 주어진 문자열을 모두 0 혹은 모두 1로 같게 만드는 최소 횟수를 반환하시오.

ㄷㄷ 솔직히 처음 봤을 때는 이해가 잘 안됐다! 여러 시도를 해보았으나 결국 실패

input = "011110"

def find_count_to_turn_out_to_all_zero_or_all_one(string):
    count_to_all_zero = 0   # 모두 0으로 만드는 방법에서 최소로 뒤집는 숫자
    count_to_all_one = 0    # 모두 1으로 만드는 방법에서 최소로 뒤집는 숫자

    if string[0] == '0':    #첫 번째 원소가 0인지 1인지에 따라 숫자를 추가
        count_to_all_one += 1
    elif string[0] == '1':
        count_to_all_zero += 1

    for i in range(len(string) - 1):
        if string[i] != string[i + 1]: # 0에서 1 or 1에서 0으로 바뀌었을 때
            if string[i + 1] == '0':    # 0에서 1로 문자열이 전환되는 순간
                count_to_all_one += 1
            if string[i + 1] == '1':    # 1에서 0으로 문자열이 전환되는 순간
                count_to_all_zero += 1

    return min(count_to_all_one, count_to_all_zero) #둘 중에 최솟값을 반환

result = find_count_to_turn_out_to_all_zero_or_all_one(input)
print(result)