WEEK 01 Point Note

여기에서는 Week01의 핵심 내용을 정리해보았다.

들어가기 앞서 파이썬의 숫자는 0, 1, 2, 3 … 순으로 간다. 0을 포함함을 잊지말자.

대표 연산자: 덧셈 ( + ) · 뺄셈 ( - ) · 곱셈 ( * ) · 나눗셈 ( / ) · 거듭제곱 ( ** ) · 몫( // ) · 나머지( % )

배열

배열은 따로 흩어진 변수를 하나로 묶어서 사용할 수 있게 하며 코드를 쉽고 효율적으로 작성 가능합니다. 파이썬에서 배열은 크게 데이터 컨테이너라는 리스트와 튜플로 구현할 수 있습니다.

리스트는 원소를 변경할 수 있는 뮤터블 list형 객체입니다. [,,]로 쉼표로 구분하여 생성가능하며 []만 사용하여 빈 리스트를 생성할 수도 있습니다. list(range(3,13,2)) → [3, 5, 7, 9, 11]를 통해 특정 범위의 정수로 구성된 리스트를 만들 수 있습니다. 여기서 3은 시작점, 13은 끝점(참고로 13은 사실상 12이다), 2는 건너뛰는 단위입니다. list명 = [None] * 5 를 통해 리스트안에 None을 5개 반복시킬 수 있습니다.

튜플은 원소에 순서를 매겨 결합한 것으로 원소를 변경할 수 없는 이뮤터블 자료형입니다. [대괄호] 아닌 (괄호)를 사용하고 사용법은 list와 비슷합니다. 특이하게, (괄호)를 생략할 수 있습니다.

배열보다 다른 개념을 디테일하게 알아보겠다.

문자열

문자열은 문자의 열이므로 개념보다 함수를 중점적으로 설명하겠다.

문자열의 길이 구하기: len(문자열 함수)

문자열 자르기 1: 문자열 함수[-1] → 뒤에서 첫번째 문자열 추출

문자열 자르기 2: 문자열 함수[0:4] → 첫번째 ~ 네번째 문자열 추출

문자열 포매팅
number = 3
"I eat %d apples." % number → 'I eat 3 apples.'

포매팅 종류는 다음과 같다.

코드	설명
%s	문자열(String)
%c	문자 1개(character)
%d	정수(Integer)
%f	부동소수(floating-point)
%o	8진수
%x	16진수
%%	Literal % (문자 % 자체)

자세한건 인터넷을 보고 해결하자.

코딩문제에는 문자열을 한줄에 여러 값을 받을 상황이 자주오는데 그럴땐
a = map(int, input().split())을 쓴다. 의미는 인풋을 모두 정수형으로 사용하고, 공백기준으로 나눈다는 소리이다.

반복문

반복문은 for, while 문 등이 있다. 인터넷에 찾아보자.

재귀함수

보통 재귀함수의 대표적인 문제를 예시로 들면 팩토리얼 문제를 예시로 든다. 팩토리얼의 특징은 전 숫자에서 1을 뺀값을 다시 곱한다는 특징이 있습니다. 밑의 팩토리얼을 3가지 방식으로 표현한 것을 보며 확인해보자

# 재귀함수
def factorial (n):
    if n > 0:
        return n * factorial(n-1)
    else:
        return 1


n = int(input())
print(factorial(n))


# for문
n = int(input())
result = 1
for item in range(n, n+1, 1):  
    result *= item
print(n)
# for문은 재귀함수와 다르게 1부터 n까지 올라가면서 곱한다.

# math 라이브러리 사용
import math
n = int(input())
print(math.factorial(n))

이렇게 재귀함수, for문, math라이브러리를 사용하여 팩토리얼을 표현 가능하다.
위의 재귀함수는 만약 5라고하면 5를 곱하고 -1을 후 다시 본인 함수에 넣고 4를 곱하고 -1을 하고 넣고… 이 과정을 n이 0보다 클때까지 수행합니다. 즉, 1이될때까지 이과정을 반복합니다.

복잡도(BigO, 시간, 공간)

요즘 컴퓨터 성능이 좋아 공간복잡도는 상관안한다고 한다. 시간복잡도가 굉장히 중요한데, 컴퓨터 연상의 가능/불가능을 가늠하기 때문이다.

시간복잡도O(n) = n^2, n^3, 2^n, n!등 다양하다.
복잡도를 생각해볼 예시 문제는 회전판 순환이 있다.

이후 정렬방식을 설명하셨다.

정렬타입	시간복잡도	안정도	평균
삽입	O(n^2)	stable	O(n^2)
합정렬	O(nlogn)	unstable
합병	O(nlogn)	stable
퀵	O(n^2)	unstable	O(nlogn)

정렬

정렬은 버블, 셸, 병합, 힙, 도수, 퀵 정렬 등 다양한 방법이 존재합니다. 그러나 이번 주차에는 정렬의 기본 기능과 퀵 정렬에 대해 다뤘다.

파이썬에서의 정렬은 신기하게 숫자뿐만 아니라 문자도 정렬가능하다.

리스트에서의 정렬: 리스트명.sort() → 리스트를 오름차순으로 정열
만약, 내림차순 정렬을 하고 싶으면 괄호안에(reverse=True)를 입력하면 된다.

보통 리스트 인자를 받을 때 input()으로 받는다. 그런데 입력값이 커지면, 범위가 커서 시간 초과가 나온다.
이를 해결하기 위해 sys패키지를 사용한다. 그런다음 input()자리에 sys.stdin.readline()를 쓰면 된다.
input과 달리 readline이 개행 문자 그대로 입력되기 때문에 입력 시간을 최소화 할 수 있다. 만약, 개행 문자를 제거하고 싶다면 readline().strip() 을 추가하면된다.

정렬문제를 풀다보면 1 ~ 9가 얼마나 포함됐는지 구하라는 문제가 많이 나오는데, 인덱스 수를 세워서 효율적으로 답을 만들 수 있다. 더 알고 싶다면 3월19일에 수 정렬하기-1,2,3 문제를 참고하자.

완전 탐색(백트래킹)

완전 탐색은 수열에서 가능한 모든 수를 찾는 것이다. 만약, 조건에 맞는 경우의 수를 찾는다면 백트래킹을 쓰게 된다. 백트래킹은 마치 미로와 같다. 우리가 미로를 찾을 때 막다른 길이면 그 길을 제외하고 다른 출구를 찾으러 간다. 주어진 조건에 만족하는 결과를 낼 때 유용할 것이다.

완전 탐색의 방식 중 하나로 유명한 DFS가 있다. 깊이 우선 탐색으로 모든 경우의 수를 끝까지 조사하고 결과를 출력한다. 여기서 나는 의구심이 들었다. 그러면 백트래킹이 결과를 찾기에 더 용이한 방법인데, 코딩에서 DFS를 쓰는 경우는 없지않나? 최종 결과를 도출하는데에 모든 경우를 찔러보면 시간복잡도가 올라가는 것이 아닐까?라는 생각이었다.
→ 그러나 이 두개의 개념은 사용 용도의 차이라고 볼 수 있다. 미로에서 출구를 찾으라고 하면 백트래킹 방식으로 찾는 것이 옳지만, 모든 길이 출구인지 아닌지 구하라고 하면 DFS 방식이 옳을 것이다. 즉, 조건이 걸려있으면 백트래킹이고 모든 경우와 변수를 생각해야된다면 DFS이라는 것이다.

솔직히 이론은 어렵지 않다. 근데, 코딩을 하는 것이 어렵다. 백트래킹 같은 경우 조건식을 달고, 만약 조건에 부합하지 않거나 탐색을 완료했으면 pop을 통해 리스트에서 인자하나를 뺀다. 이후 다른 인자를 추가하면서 새 결과를 출력한다. 대표적인 문제로는 N과 M, N-Queen 문제가 있다. N과 M 문제를 푸는데에 고전하고 있어 만약에 100퍼센트 이해됐다면 추가적인 내용을 작성하겠다.

정수론

해당 주차에서 주력적으로 다루는 것은 코드로 소수를 뽑아내는 것이다.

소수의 특징은 본인말고는 아무 수로도 나누어 지지 않는다. 이걸 코드로 작성해보면

**data = list(map(int,input().split()))
count = 0**

for x in data:   # x는 본인 수를 의미한다.
    for i in range(2, x+1):  # 2부터 본인 수까지 나눈다. range의 마지막수는 -1이므로 +1을 해야 본인 수까지 온다.
        if x % i == 0:    # 만약 해당 숫자가 나누었을때 몫이 0이되는 수
            if x == i:    # x와 i 같은 수 이 말은 즉슨 본인 외에 나누어 지는 값이 없을때 이므로 소수이다.
                count += 1  # 값을 1 올려준다.
            break
print(count)

다음과 같이 작성할 수 있다. 더욱 심화적으로 배우고 싶다면 골드바흐 추측 문제를 풀어보자. 해설도 있다.