1. 1부터 1억까지 더하는 프로그램

  • for문 사용 > 실행속도가 느리다.
  • 재귀함수 사용 > stack overflow 발생
  • 등차수열 사용 > 가장 좋은 방법

1. for 문

sum = 0

for i in range (1, 100000001):
    sum += i

print(sum)

2. recursive : 재귀함수는 함수 내에서 동일한 함수가 나오고, 탈출조건이 있어야 한다.

def sum_to_num(num):
    # 탈출 조건
    if num == 1:
        return 1

    return sum_to_num(num -1) + num

print(sum_to_num(10))

3. (등차수열)

sum = (100000000 * (1 + 100000000)) / 2
print(sum)

2. 버블 정렬

  • 제일 앞의 값과 바로 뒤의 값을 순차적으로 비교하여 큰 수를 뒤로 보낸다.
  • 첫번째와 나머지 값들의 비교가 끝나면, 가장 큰 값이 마지막으로 간다.
  • 그 다음 맨뒤의 값을 제외하고 반복한다.
sample = [2, 4, 3, 1]
n = len(sample)

for i in range(0, n):
    for j in range(0, n - i - 1):
        if sample[j] > sample[j + 1]:
            sample[j], sample[j + 1] = sample[j + 1], sample[j]


print(sample)

3. 시간 복잡도

데이터 개수가 늘어날 때, 연산회수가 얼마나 증가 하나는가 판단하는 것이 시간복잡도 개념이다. 이 때, 컴퓨터 공학에서는 비교연산을 몇 번했는가로 계산한다.

예를 들어 위의 버블정렬에서 if문(비교연산)은 (3 + 2 + 1)번 실행된다. 만약 n개의 숫자가 있다면, 1 + 2 + 3 + … + (n-1)번 실행될 것이다.

빅오를 계산하면 O(n(n +1) / 2) = O((n^2 + n) / 2) 이다. 여기서 다 떼고 가장 큰 수만 남기면 O(n^2)이다.

Big-O cheat sheet

  • O(1) : 가장 좋으나, 있을 수 없는 경우
  • O(n^2) : 최악의 경우
  • O(n log2 n) : 좋음, 현업에서 이정도만 해도 대단
  • O(log2 n) : 가장 베스트

4. 그 외

  • 괄호가 있는 수식 계신가 만들어 보기
    • 컴퓨터는 괄호를 인식하지 못하므로, 중위표기법을 후기표기법으로 바꿔 계산
  • 파이썬으로 공부 시, 유의사항
    • array : 동일한 자료형으로 이루어진 집합 VS python list : 여러자료형 저장 가능
    • call by value vs call by reference
      • call by value : 다른 함수에서 호출할 경우 인자로 값만 전달
      • call by reference : 다른 함수에서 호출할 경우 인자로 그 변수자체를 전달
      • VS 파이썬에는 위의 개념 대신 call by assignment가 존재한다. 그렇기 때문에 기본 개념을 꼭 익혀야 한다. (like C언어)
# call by value 와 call by reference의 경계가 없음
a = [1, 2]

def func(a):
    a.append(3)
    a = [12,13,14]

func(a)
print(a)  # [1, 2, 3]