알고리즘 1주차 - 숙제

소수 나열하기

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

input = 20


def find_prime_list_under_number(number):
    # 이 부분을 채워보세요!
    return []


result = find_prime_list_under_number(input)
print(result)

# 내 코드
input = 20


def find_prime_list_under_number(number):
    result = []
    for i in range(1, number+1):
        count = 0
        for j in range(1, i+1):
            if i % j == 0:
                count += 1
        if count <= 2:
            result.append(i)
    return result


result = find_prime_list_under_number(input)
print(result)

문자열 뒤집기

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

input = "011110"


def find_count_to_turn_out_to_all_zero_or_all_one(string):
    # 이 부분을 채워보세요!
    return 1


result = find_count_to_turn_out_to_all_zero_or_all_one(input)
print(result)

# 내 코드
input = "011110"


def find_count_to_turn_out_to_all_zero_or_all_one(string):
    case_zero = 0
    case_one = 0
    for idx in range(0, len(string)):
        if string[idx] == "0":
            if idx == 0:
                case_zero += 1
            else:
                if string[idx-1] == "0":
                    continue
                else:
                    case_zero += 1
        elif string[idx] == "1":
            if idx == 0:
                case_one += 1
            else:
                if string[idx - 1] == "1":
                    continue
                else:
                    case_one += 1
        else:
            print("0아니면 1만 입력해주세요")
            exit()
    return min(case_zero, case_one)


result = find_count_to_turn_out_to_all_zero_or_all_one(input)
print(result)

알고리즘 문제 풀 때 팁

1. 바로 코드를 작성하지 말고, 문제의 다른 예시들을 떠올리면서 규칙성 생각

2. 배웠던 자료구조를 활용하면 어떨지 생각

3. 문제의 특징들을 하나하나 글로 써보기