오늘의 공부를 끝내며.. (11/9) and 알고리즘 1주차 완료

오늘은 자료구조의 알고리즘에 대한 강의 1주차를 완강했다. 강의는 파이썬을 기본문법으로 하는데, 여러가지 논리적 문제 에 대해서 풀고, 시간복잡도와 공간복잡도, 점근표기법에 대해서도 익혔다. 여기까지 개념자체는 어렵진 않았다. 다만 숙제하는 부분에서 문자열뒤집기라는 문제가 있는데, 이부분을 이해하기 다소 어려웠다. 현재는 1주차 숙제 첫번째 문제인 한 정수이하의 소수의 배열만 답을 놓았고, 두번째 문제인 문자열 뒤집기는 보류상태이다. 

 

알고리즘은 내 생각으로는 문제를 먼저 가장 잘 이해하는게 중요하다고 생각한다. 왜냐면 문제를 이해하지 못하면 답을 봐도 그 풀이를 이해하지 못하기 떄문이다. 그래서 일단 두번째 문제가 이해될 때까지는 특강을 듣거나, 다른 공부 강의를 하면서 자연스럽게 이해되도록 해야되겠다.

 

1주차 숙제의 첫번째 문제

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

# 20이 입력된다면, 아래와 같이 반환해야 합니다! [2, 3, 5, 7, 11, 13, 17, 19]

 

ㄴ 이것은 어렵지 않았다. 대학교시절에 한번 과제로 냈었던 문제였다.

input = 20


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


result = find_prime_list_under_number(input)
print(result)

 

1주차 숙제의 두번째 문제

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):
    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)

result = find_count_to_turn_out_to_all_zero_or_all_one(input)
print(result)