과제1 소수 나열하기

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

1. 정수를 입력 받는다. 2. 정수 이하의 숫자를 리스트화 시킨다. 3. 소수(자신보다 작은 두개의 자연수를 곱하여 만들수 없는 1보다 큰 자연수)를 구하는 법을 이용해 분류 한다. 4. 분류된 소수를 반환한다.

처음 주어진 형태

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

2. 숫자를 리스트화 필요 -> 20을 받았으니 1부터 20까지 숫자를 펼쳐야 하지만 1은 소수가 아니니 2부터 시작하면 된다.
   range함수를 사용하자 -> 연속적인 숫자 객체를 만들어 반환해주기 때문에 ex)range(횟수)-> range(len('문자열')) = 문자열 길이를 반환해서 횟수로 사용하는 함수

def find_prime_list_under_number(number):
    for n in range(2,number+1):
#2,number+1 2부터 시작하고 number까지 돌려준다.

3. 소수를 구하자 - 나머지를 이용하려고 하는데 나누어줄 값이 없다. => 새로운 for문으로 나눠줄 값을 만들자
   (자기자신으로 나누면의미 없어서 1을 없앴고, 1로나누는것도 의미 없어서 2부터 시작)

def find_prime_list_under_number(number):
    for n in range(2,number+1):
        for i in range(2,n):
            if n % i == 0:

구한 소수를 넣을 공간이 없으니 만들고 넣어줘야 하고 소수가 아닐때는 중지하고 다음것을 실행하기 위해 break를 넣어준다.
else를 if와 같은 위치 들여쓰기를 하게 되면 else의 append가 for문을 타고 반복이 되기에 굉장히 중복되게 나온다. 오늘 알고리즘 공부 하면서 많이 했던 실수다.

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
result = find_prime_list_under_number(input)

하고 과제 정답을 보면 더 개선 방법이 있다고 한다.
말이 어렵긴 한데 지금은 모든 수로 나누고 있는데 그럴 필요 없이 모든 소수로만 나누어 떨어지지 않는지 할 수 있다고 한다.

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

i가 들어가는 for문의 범위를 prime_list로 한정 하면 된다.
여기서 한번 더 개선이 가능하다는데 여기서 부터는 잘 이해가 안된다. N이 N의 제곱근 보다 크지 않은 어떤 소수로도 나눠지지 않는다.....
5, 25. 1 3 5 7 11 13 17 19 23 5로나눠지는건 없으니 소수이다. 흠...

과제2

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

0에서 1로 바뀌든 1에서 0으로 바뀌는것은 중간에 갑자기 지우고 바꿀 수 있는게 아니다. 컴퓨터는 왼부터 오른까지 순서대로 읽기 때문에 바뀌려면 지금과 다음이 일치한지 않하는지로 판단을 하게 된다.

1. 시작이 0인지 1인지 파악한다.
2. 모두 0으로 바꿀 때와 1로 바꿀때를 실행하며 횟수를 카운트한다.
3. 카운트한 횟수를 비교한다.

1-1. 처음 count는 0으로 설정한다.

count_all_zero = 0
count_all_one = 0

1-2. 시작 문자를 파악한 뒤 서로의 반대에 count를 1 더한다. -> 첫 시작이 0이면 전부 1이 되어야 하는 카운트에 1을 더한다.

    if string[0] == '0':
        count_all_one += 1
    if string[1] == '1':
        count_all_zero += 1

2-1 for range(len)문으로 string만큼 반복 0~4까지
-1을 한 이유 : 다음값과 비교하려면 밑에 +1을 붙여야 하는데 -1없이 붙이면 존재하지 않은 7번째를 찾게 되므로 오류가 발생

for i in range(len(string) -1):

2-2 다음 값과 비교 해야함 앞에 i는 0~4까지 뒤에는 1~5까지

if string[i] != string[i+1]:

2-3 서로 바꿔줄 수 있으면 count +1

if string[i+1] == '0':
	count_all_one += 1
if string[i+1] == '1':
	count_all_zero += 1

3 비교

return max(count_all_zero, count_all_one)