스파르타 코딩클럽

내일배움캠프 AI 웹개발자양성과정 2회차

알고리즘 강의 1주차 숙제

1. 소수 나열하기

: 정수를 입력 했을 때, 그 정수 이하의 소수를 모두 반환

Q. 정수를 입력 했을 때, 그 정수 이하의 소수를 모두 반환하시오.
소수는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다.

input = 20


def find_prime_list_under_number(number):
    if number < 2:
        return []

    prime_list = [2]

    for num in range(2, number+1):
        prime_bool = True
        for prime in prime_list:
            if num % prime == 0:
                prime_bool = False
                break
        if prime_bool:
            prime_list.append(num)

    return prime_list


result = find_prime_list_under_number(input)
print(result)

2. 문자열 뒤집기

: 주어진 문자열을 모두 0 또는 1로 만들기위한 최소 횟수 반환

Q.
0과 1로만 이루어진 문자열이 주어졌을 때, 이 문자열에 있는 모든 숫자를 전부 같게 만들려고 한다. 할 수 있는 행동은 문자열에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다.
예를 들어 S=0001100 일 때,
전체를 뒤집으면 1110011이 된다.
4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다.
하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다.
주어진 문자열을 모두 0 혹은 모두 1로 같게 만드는 최소 횟수를 반환하시오.

input = "110011000111101"


def find_count_to_turn_out_to_all_zero_or_all_one(string):
    current_char = string[0]
    count_turn = [0, 0]
    count_turn[int(current_char)] += 1

    for char in string:
        if current_char != char:
            count_turn[int(char)] += 1
            current_char = char

    if count_turn[0] < count_turn[1]:
        count_turn_min = count_turn[0]
    else:
        count_turn_min = count_turn[1]

    print(count_turn)

    return count_turn_min


result = find_count_to_turn_out_to_all_zero_or_all_one(input)
print(result)

Github

https://github.com/kimphysicsman/nbcamp-algorithm-220726