파이썬 3중 for문 - paisseon 3jung formun

파이썬 반복문

단순한 연산이 이루어지는 코드를 작성하는 것은 쉽다. 그러나 그 연산의 횟수가 많아진다면 반복으로 인해 코드도 길어지고, 정확히 작성하고 있는지 의문이 든다. 반복되는 연산에 대해 코드의 길이를 줄이는 데 도움을 주는 for문을 알아보자.

for문 사용법

위 for문을 보면 for a in b: 이 보이게 되는데 in 뒤에 'b'는 순서가 있는 데이터를 가지고 있는 변수이고 'a'는 'b'에 있는 데이터를 순서대로 받아들이는 변수다. 위 코드에서 'b'는 [1, 2, 3, 4, 5]라는 5개 데이터를 가지고 있는 리스트이고, 'a'는 'b'에 있는 데이터를 순서대로 한 개씩 가지고 와서 받아들인다. 그렇다면 a는 1, 2, 3, 4, 5라는 데이터를 순서대로 'a' 변수에 넣게 된다.

'b' 뒤에 콜론( : ) 입력 후 엔터를 치면 아래 칸으로 커서가 내려오는데 그 안에 반복하려는 코드를 작성하면 되고 in 뒤에 있는 변수에서 더 이상 가지고 올 것이 없다면 반복이 종료된다. 필자는 'b'에서 받은 데이터를 'a'에 할당한 뒤 'c'라는 변수에 누적하여 합하는 코드를 작성했다. 코드 마지막은 변수 'c'에 있는 값을 출력해보니 원하는 대로 'b'안에 있는 모든 데이터 값이 더해지고 종료된 것을 알 수 있었다. 

앞서 for문에서 in 뒤에 있는 변수는 순서가 있는 데이터가 와야 한다고 말했다. 'b'에 문자열을 넣고 이번에는 'a'를 바로 출력하는 반복문을 작성해보니 위와 같이 문자열이 하나씩 출력되는 것을 알 수 있었다.

이번에는 'b'에 순서가 없는 '12'라는 숫자 데이터를 넣고 반복문을 실행했더니 에러가 발생했고, 아래 'b'에는 숫자가 아닌 순서가 있는 문자열 '12'를 입력하니깐 하나씩 순서대로 출력되었다. 

파이썬 for문은 순서가 있는 데이터를 하나씩 가지고 와서 데이터의 개수만큼 반복시키는 반복문이다. 이제 for문 안에 for문을 넣는 이중 for문도 사용할 수 있다. 

이중 for문

for문 안에 for문을 이용한 이중 for문은 바깥쪽에 있는 for문에서 데이터를 하나 가지고 오면 안쪽 for문이 실행되는데 안쪽 for문의 반복이 모두 끝나야 다음 바깥쪽 for문이 실행된다.

위 코드를 보면 바깥쪽 for문은 'b'라는 변수에 있는 첫 번째 데이터 '1'을 가지고 오고 안쪽 for문은 'a' 변수에서 '2'부터 '9'까지 순서대로 가지고 오면서 2*1=2, 3*1=3, 4*1=4 ... 9*1=9라는 첫 번째 출력을 완성한다. 그다음에 바깥쪽 for문에서 '2'를 가지고 오고 안쪽 for문은 '2'부터 '9'까지 순서대로 가지고 오면서 2*2=4, 3*2=6, 4*2=8 ... 9*2=18 두 번째 출력이 완성된다. 

모든 코드가 반복되면 위와 같은 구구단을 출력할 수 있다. 위 코드에서 'b' 대신에 range(1, 10) 그리고 'a' 대신에 range(2, 10)을 작성하면 동일한 결과를 얻을 수 있으며 위 코드보다 더 간결해진다. 

import time

list_a = range(3000)

def func0(list_a):
    ret = []
    for i in range(len(list_a)):
        suma = 0
        for a in list_a[:i+1]:
            suma += a
        ret.append(suma)
    return ret

def func1(list_a):
    ret = []
    suma = 0
    for a in list_a:
        suma += a
        ret.append(suma)
    return ret

start0 = time.monotonic()
ret0 = func0(list_a)
elapsedtime0 = time.monotonic() - start0

start1 = time.monotonic()
ret1 = func1(list_a)
elapsedtime1 = time.monotonic() - start1

if ret0 == ret1:
    print(elapsedtime0, elapsedtime1)

출력 결과는 0.31199999999807915 0.0이 나왔다.

두 함수의 반환값은 같지만 실행 시간은 다르다. 왜 그럴까?

list_a의 길이를 n이라 하자. (위 코드에서는 n=3000)

func0을 보면 이중 for문이 사용되었다. 바깥 for문은 list_a의 길이, 즉 n번 반복되고, 안쪽 for문은 i번 반복되는 것을 알 수 있다. 여기서 i는 첫째항이 1, 마지막항이 n, 공차가 1인 등차수열의 원소이다. 따라서 안쪽 for문이 반복되는 횟수는 등차수열의 합 공식에 의해 n(n+1)/2이다. n에 대한 이차식으로 나타내어지므로 시간 복잡도는 O(n²)이라고 할 수 있겠다.

func1을 보면 for문이 하나이다. n번만큼 반복되므로 시간 복잡도는 O(n)이다.

이 코드에선 n은 3000이므로 두 함수의 출력 시간은 3000배가 차이가 난다고 할 수 있겠다.

실제로 출력 결과를 보면 func0은 0.311초 동안 실행되었다고 하는데 func1은 0초로 너무 빨라서 실행 시간이 측정되지도 않았다. 0.000초도 안 걸린 것이다. 이 코드에서는 n이 3000이지만 실제로 이중 for문이 쓰이는 곳에서는 n값이 엄청 커질지도 모른다. 만약 이중 for문을 안 쓰고 func1처럼 for문 하나만 쓴다면 시간이 1/n으로 줄어들 것이다.

n = 100
a = 0

for x in range(10):
    for y in range(n):
        for z in range(n-10):
            a += 0

위 코드는 삼중 for문이지만 시간 복잡도는 여전히 O(n²)이다.
왜냐하면 명령 횟수가 (n-10)*n*10 으로 n에 대한 이차식으로 나타내어지기 때문이다.

아무튼 시간 복잡도 O(n²)은 피할 수 있으면 피하는 것이 좋다는 결론이다. (게다가 파이썬이라서 다른 언어보다 속도가 느리다..)

ref: https://coding-factory.tistory.com/608