[ Algorithm | Python | TIL ] 소수 나열하기, 문자열 뒤집기

Haksoo JI·2022년 11월 29일

[ TIL ]

목록 보기

4/30

소수 나열하기, 문자열 뒤집기

🧩 소수 나열하기

내 풀이

input = 20


def find_prime_list_under_number(number):
    # 소수: 약수가 1과 자기 자신 두 개밖에 없는 수.
    # e.g. 20을 입력하면 [2, 3, 5, 7, 11, 13, 17, 19]
    # number 이하 자연수 중에 소수를 찾는다.
    #   그러기 위해서 먼저, number 이하의 각 자연수마다 소수인지 판별한다.
    #       그러기 위해서 먼저, number 이하의 각 자연수를 1과 number(자기 자신) 사이의 수로 나눠본다.
    #                        나누어 떨어지는 것이 있으면 -> 소수 아님 판정 | 없으면 -> 소수
    # 소수 판정 배열에서 소수만 골라서 반환한다.

    prime_list = []                                      # number = 5 -> [0,1,1,0,1]
    turn_out_prime_list = [0] + [1] * (number-1)         # 소수판정 배열: 인덱스 + 1 은 자연수. 값이 1이면 소수, 0이면 소수 아님.

    for num in range(1,number+1):      # input: 5 -> 1 ~ 5를 돌면서 각 수가 소수인지 판정하기

        for div_num in range(2,num):    # number = 5 -> 1 = 기본값 0 : 반복X                     |   4 = 기본값 1 : 4 % 2 == 0 -> 값 0(소수X)
            if num % div_num == 0:                  #   2 = 기본값 1 : 반복X                     |   5 = 기본값 1 : 5 % 2 != 0 -> 값 1
                turn_out_prime_list[num - 1] = 0    #   3 = 기본값 1 : 3 % 2 != 0 -> 값 1(소수)                    5 % 3 != 0 -> 값 1
                                                    #                                                            5 % 4 != 0 -> 값 1(소수)
    for i, val in enumerate(turn_out_prime_list):   # 소수판정 배열의 값이 1인 요소의 인덱스를 구해서 소수값(인덱스+1) 구하기
        if not val == 1:
            continue
        prime_list.append(i + 1)

    return prime_list


result = find_prime_list_under_number(input)
print(result)

모범답안

아쉽게도 나의 사용한 풀이는 가장 기본적인 접근방법이면서, 비효율적인 풀이였다. 소수와 관련된 알고리즘을 만들기 위해서는 먼저 소수(prime number)에 대한 더 깊은 이해가 필요했다.
모범답안에서는 기본접근방법, 1차개선방법, 2차개선방법 으로 총 3가지의 풀이를 알려주는데, 소수의 특징을 잘 알고 활용할수록 짧고 효율적인 알고리즘을 작성할 수 있다는 것을 알 수 있었다.

1. 기본접근방법

활용특징
: 소수는 자기 자신과 1 외에는 아무것도 나눌 수 없다.
코드흐름
1) range 함수를 써서 2부터 number까지 반복문을 돕니다.
2) 그리고 각 숫자를 n이라고 한다면, 2부터 n-1까지의 수로 n을 나눠본다.
3) 그 때까지 안 나누어 떨어진다면 소수이다.

코드

def find_prime_list_under_number(number):
    prime_list = []
    for n in range(2, number + 1):
        for i in range(2, n):
            if n % i == 0:
                break
        else:
            prime_list.append(n)

    return prime_list

2. 1차개선방법

활용특징
: 어떤 자연수가 소수인지 확인해보기 위해서는 그 자연수보다 작은 소수들로 나누었을 때, 나누어 떨어지는지 확인해보면 된다. 즉, 소수가 아닌 자연수로 나눠볼 필요가 없다.

예를 들어서 8이 소수인지 확인해보기 위해서 4나 6 등으로 나누어볼 필요는 없다.

왜냐하면 4, 6 등의 소수가 아닌 수들은 약수를 여러 개 가지고 있고,
어떤 수가 약수가 여러 개인 수로 나누어 떨어진다는 것은
그 수도 약수가 여러 개라는 뜻이기 때문이다.
코드흐름
1) 1과 N사이의 모든 자연수로 나눠볼 필요가 없다.
2) 1과 N사이의 모든 자연수 중에 소수인 수로 나눠본다.

코드

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:
                 break
         else:
             prime_list.append(n)

     return prime_list

3. 2차개선방법(에라토스테네스의 체)

활용특징
: 어떤 자연수가 소수인지 확인해보기 위해서 그 자연수보다 작은 소수들로 나누어 볼 때, 어떤 자연수n의 제곱근sqrt(n) 보다 작거나 같은 소수까지만 나눠보면 된다. 이유는 수가 수를 나누면 몫이 발생하게 되는데 몫과 나누는 수, 둘 중 하나는 반드시 N의 제곱근 이하이기 때문이다.

읽어봐도 왜 그런지 무슨 뜻인지 잘 이해가 안가서 습득하는데 시간이 좀 걸렸다. print()로 코드 중간 중간을 출력해보면서 이해하였다.

예를 들어 자연수 9가 소수인지 확인해보기 위해서 9보다 작은 소수들로 나눌 때에, 9의 제곱근인 3까지의 소수들로만 나눠봐도 충분히 9의 소수여부를 판단할 수 있다.

9를 수와 수의 곱으로 보면 1 X 9, 2 X 4.5, 3 X 3, 4 X 2.25, ... 등으로 표현할 수 있다. 그렇다면 9를 2로 나눈 몫이 4.5 라는 것은 반대로 9를 4.5로 나눈 몫이 2가 나온다는 것이다. 따라서 곱하는 두 수가 서로 같아지는 제곱근을 기준으로 해서 양쪽으로 모두 나눠보는 것은 같은 일을 두 번하는 셈이다. 그래서 한 쪽으로만 나눠보면 되는데, 소수는 자연수니까 굳이 더 많은 범위를 선택해서 검사할 필요는 없을 것이다. 효율적으로 제곱근보다 작은 범위의 소수들로만 나누어보고 나누어 떨어지지 않는다면 그 수는 소수라고 판별할 수 있는 것이다. 조금 설명이 부족해보이기는 하지만 수학공부를 하는 것은 아니기에 여기까지만 하려고 한다.

코드

def find_prime_list_under_number3(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

✅ 자가피드백

for ~ else 문 활용하기
: for문과 같이 사용되는 else문은 for문이 break 등으로 중간에 빠져나오지 않고 끝까지 실행 됐을 경우 else문이 실행되는 방식으로 진행된다.
수학과 관련된 알고리즘일 경우, 문제 자체에 대해 좀 더 깊은 이해(구글링 등)를 한 후 알고리즘을 짜도록 해보기

🧩 문자열 뒤집기

내 풀이

input = "0111101110010001011"


def find_count_to_turn_out_to_all_zero_or_all_one(string):
    # 이 부분을 채워보세요!
    # string = '011110' -> string[1:5] 뒤집기 -> '000000' : 1회
    #                   연속된 문자열끼리 나누면 3부분
    # string = '010110' -> string[2], string[1:5] 뒤집기 -> '000000' : 2회
    #                   연속된 문자열끼리 나누면 5부분
    # string = '0101101011' -> string[3:5] '0100001011', string[2:6] '0111111011', +2회 -> '000000' : 4회
    #                   연속된 문자열끼리 나누면 8부분

    # 결국 연속된 문자열끼리로 나누면 몇 부분인지 구하는 것.

    temp_zero_list = string.split('1')               # 0이 연속된 부분의 개수 구하기 - '1'을 구분자로 split
    temp_zero_list_length = len(temp_zero_list)      # temp_zero_list = 공백 문자열('') 포함된 배열
    for element in temp_zero_list:                   # temp_zero_list 의 각 요소를 검사
        if element == '':                            # -> 전체 요소 개수 - 공백 문자열 개수 == 0이 연속된 부분의 개수
            temp_zero_list_length -= 1

    temp_one_list = string.split('0')                # 1이 연속된 부분의 개수 구하기 - '0'을 구분자로 split
    temp_one_list_length = len(temp_one_list)        # temp_one_list = 공백 문자열('') 포함된 배열
    for element in temp_one_list:                    # temp_one_list 의 각 요소를 검사
        if element == '':                            # -> 전체 요소 개수 - 공백 문자열 개수 == 1이 연속된 부분의 개수
            temp_one_list_length -= 1

    temp_length = temp_zero_list_length + temp_one_list_length      # 0이 연속된 부분의 개수 + 1이 연속된 부분의 개수

    if temp_length % 2 == 0:
        return int(temp_length / 2)
    else:
        return int((temp_length - 1) / 2)

result = find_count_to_turn_out_to_all_zero_or_all_one(input)
print(result)

모범답안

def find_count_to_turn_out_to_all_zero_or_all_one(string):
    count_to_all_zero = 0
    count_to_all_one = 0

    if string[0] == '0':
        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]:
            if string[i + 1] == '0':
                count_to_all_one += 1
            if string[i + 1] == '1':
                count_to_all_zero += 1

    return min(count_to_all_one, count_to_all_zero)