스파르타 코딩 클럽 알고리즘 1주차 숙제

숙제하면서 알게 된 것
1. python에서 for 문을 사용할 경우 다른 언어(C, C++ Java 등)의 for 문과는 달리 range(시작값, 종료값, 증감값)을 넣을 수 있음 -> 예전에 사놓은 파이썬 원서를 보고 알게 됨
2. range에서 종료값은 필수, 시작 및 증감값은 선택
3. python은 for 문 내부에서도 else문을 사용할 수 있음

숙제 내용
1. 입력 값이 정해지면 2부터 입력값까지의 소수들을 배열 형태로 출력
2. 0 또는 1로 구성된 문자열을 뒤집을 때 문자열을 모두 0 또는 1로 뒤집기(단, 횟수는 최소화)

1번 숙제

    # using python, find prime number under number
    for n in range(2, number + 1): # 2부터 number까지 n값을 1씩 증가시키면서 비교함(최대 n-2번 비교)
        for i in range(2, n): # 2부터 n-1까지 i값을 1씩 증가시키면서 비교함(최대 n-3번 비교)
            if n % i  == 0: # n을 i로 나눈 결과 0이 나올 경우 for i in range(2, n)을 탈출(최대 1번 비교)
                break
        # i값이 n값과 동일할 경우 else문을 발동하여 prime_list에 추가한다.
        else:
            prime_list.append(n)

여기서 1번 숙제는 시간 복잡도가 O(n^2)이라는 것을 알 수 있다.

2번 숙제

    # 0으로 시작할 경우 count_to_all_one의 값은 1 증가(최대 1번 비교)
    if string[0] == '0':
        count_to_all_one += 1
    # 1으로 시작할 경우 count_to_all_zero의 값은 1 증가(최대 1번 비교)
    elif string[0] == '1':
        count_to_all_zero += 1

    for i in range(len(string) - 1): # 0부터 len(string) - 2까지 i값을 증가시킴(최대 n-1번 비교)
        if string[i] != string[i + 1]: # 해당 숫자가 다음 인덱스에서도 반복되지 않을 때만 발동
            if string[i + 1] == '0': # 해당 숫자가 1에서 0으로 변경
                count_to_all_one += 1 # count_to_all_one의 값을 1씩 증가
            if string[i + 1] == '1': # 해당 숫자가 0에서 1로 변경
                count_to_all_zero += 1 # count_to_all_zero의 값을 1씩 증가

여기서 2번 숙제는 시간 복잡도가 O(n)이라는 것을 알 수 있다.