파이썬 자료구조/알고리즘 01 : 알고리즘 기초1

728x90

알고리즘 : 어떠한 문제를 해결하기 위해 정해놓인 일련의 절차

자료구조 : 컴퓨터에 정보를 효율적으로 저장하고 관리하는 방법

알고리즘과 자료구조는 서로 상호 보완 관계에 있다. 자료구조를 만드는 과정이 알고리즘으로 순서화되어 있기 때문이다.

이 포스팅을 하면서 코딩테스트에 대한 대비뿐만 아니라, 논리적인 사고 능력을 기르고 파이썬을 파이썬스럽게 잘 활용할 수 있는 방법들을 배우는데 큰 도움이 되기를 기대한다.

print('세 정수의 최댓값 구하기')
a = int(input('정수 a의 값을 입력하시오'))
b = int(input('정수 b의 값을 입력하시오'))
c = int(input('정수 c의 값을 입력하시오'))

maximum = a

if b > maximum: maximum = b
if c > maximum: maximum = c

print(f'최댓값은 {maximum}')

이와 같이 순차적으로 처리되는 구조를 순차구조라고 한다.

if와 콜론(:) 사이에 있는 식을 조건식이라고 하며, 조건식으로 평가한 결과에 따라 프로그램의 실행 흐름이 변경되는데 이러한 구조를 선택구조라고 한다.

if 문과 while문의 경우 복합문이라고도 하는데, 모두 콜론으로 끝이난다는 공통점이 있다.

복합문은 헤더와 스위트의 결합으로 이루어진다.

스위트란 헤더와 한 세트로 따라다니는 실행문을 의미한다.

if num > 10:		# 헤더
    sum + = num		# 스위트
    print(sum)		# 스위트

스위트는 반드시 행마다 같은 수준으로 들여쓰기를 해야한다. 파이썬에서는 공백 4개를 들여쓰기로 사용할 것을 권장한다.

만약 스위트가 단순문이면 헤더와 같은 행에 둘 수도 있다. 세미콜론(;)으로 구분하여 같은 행에 여러개의 스위트문을 둔다.

if a < b: num = 4; num2 = 8;

다만 스위트가 복합문인 경우 당연히 같은 행에 포함시킬 수 없다.

if a < b: if c < d: num = 8		# 오류 발생

코드가 짧다고 해서 항상 좋은 프로그램이 만들어지는 것은 아니다.

다음은 파이썬의 함수를 이용하여 세 정수를 입력받아 중앙값을 구하는 코드이다.

def middle(a, b, c):
    if a > = b:
    	if b >= c:
            return b	# a >= b >= c
        elif a <= c:
            return a	# c >= a >= b
        else:
            return c
    elif a > c:
        return a    # a < b and a > c, 즉 b > a > c
    elif b > c:
        return c    # a < b and b > c, a > c는 아니므로 a < c < b
    else
        return b

a = int(input('a값 입력 : '))
b = int(input('b값 입력 : '))
c = int(input('c값 입력 : '))

print(f'중앙값 : {middle(a, b, c)}')

위 코드의 middle 함수를 다음과 같이 축약하여 작성할 수도 있다.

def middle(a, b, c):
    if (b >= a and c <= a) or (b <= a and c >= a):
        return a
    elif (a > b and c < b) or (a < b and c > b):
        return b
    return c

하지만 코드가 간결해졌을지라도, 오히려 효율이 떨어지는 코드가 되어버렸다.

if문의 조건식이 거짓이라면 이어지는 elif문이 같은 항목에 대한 비교를 수행할 필요가 없다.

두번째 코드가 첫번째 코드와 다른점은, 같은 항목에 대한 비교가 계속해서 일어난다는 점이다.

a와 b에 대한 비교만 해도 b >= a, b <= a, a > b, a < b 이런식으로 4번이나 이루어진다.

첫번째 코드는 아무리 많아도 최대 4번만 비교하면 값이 도출되는데 반해, 두번째 코드에서는 그보다 훨씬 많은 비교를 거쳐야 답이 도출된다.

연산자와 피연산자

산술 연산자 : +, -, / 과 같은 기호

피연산자 : 연산의 대상이 되는 것

a / b 에서 연산자는 /이고, 피연산자는 a와 b이다.

피연산자의 개수에 따라 연산자의 명칭이 달라진다.

-a : 단항 연산자

b > a : 이항 연산자

a if b else c : 삼항 연산자

파이썬의 삼항 연산자는 if else문을 이용한 조건 연산자가 유일하다.

x = 5
y = 6
c = 0
a = x if x > y else y
print(a)
print('c는 0입니다.' if c == 0 else 'c는 0 아닙니다.')

결과 >
a = 6
c는 0입니다.

가운데에 있는 조건식이 참이면 앞에 항을, 거짓이면 뒤에 항을 선택하도록 한다.

반복 알고리즘

다음은 정수 n을 입력받은 후, 1부터 n까지 정수의 합을 구하는 알고리즘이다.

n = int(input('n값 입력'))
sum = 0
i = 1

while i <= n:
    sum += i
    i += 1

print(f'1 ~ {n}까지 정수의 합 : {sum}')

while 조건식: 명령문

이처럼 조건이 성립하는 동안 계속해서 반복 처리하는 것을 반복구조 또는 루프라고 한다. while의 조건식이 참일 경우 명령문이 계속해서 반복되는 것이다.

이때 변수 i가 반복문을 제어하는 역할을 하게 되는데, 이러한 변수를 카운터용 변수라고도 한다.

위의 코드처럼 변수가 하나만 존재할때는 for문을 사용하는 것이 더 효율적이다.

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

i값이 1부터 n까지 증가하면서 sum = sum + i라는 연산을 계속해서 수행하도록 한다.

이터러블 객체 생성

range() 함수와 같은 이터러블 객체는 말 그대로 반복할 수 있는 객체를 뜻한다. list, str, tuple등도 이에 해당한다.

range() 함수의 대표적인 사용방법은 다음과 같다.

range(n) -> 0이상 n 미만 수를 나열하는 수열

range(a, b) -> a이상 b미만

range(a, b , step) -> a이상 b미만 수를 step 간격으로 나열하는 수열

반복문의 효율 높이기

다음은 정수 a와 b를 입력받고 a부터 b까지의 정수들의 합을 출력하는 알고리즘이다.

a = int(input('정수 a입력 : '))
b = int(input('정수 b입력 : '))
sum = 0

for i in range(a, b+1):
    if i < b:
        print(f'{i} + ', end = '')
    else:
        print(f'{i} = ', end = '')
    sum += i
    
print(sum)

결과 >
정수 a입력 : 2
정수 b입력 : 4
2 + 3 + 4 = 9

else문에 도달하기 전까지 i는 값을 증가시키며 2 + 3 + ...의 형태를 반복하고

최종적으로 =을 붙인채로 반복문을 빠져나와 i값의 총 합을 출력시키는 형태이다.

그러나 이런 형태는 입력한 정수 사이의 값이 커질수록 비효율적인 연산을 처리하게 된다.

1 + 2 + ... + 5734 + 5735 + ... 계속 반복하는동안 else문 실행 판단 여부또한 그만큼 반복하게 될 것이다.

결국 맨 마지막에 이르러서야 else문이 실행되는데, 단 한번만 작동할 것 같으면 굳이 for문 내에 else를 두는 형태로 만들 필요가 없다.

위의 코드를 for문 이후로 다시 작성하면 이렇게 된다.

for i in range(a, b):
    print(f'{i} + ', end = '')
    sum += i
    
print(f'{b} = ', end = '')
sum += b

print(sum)

sum값 출력 명령을 반복문 밖으로 빼고 반복 횟수또한 1회 감소시키면서 알고리즘의 효율도를 높일 수 있다.