알고리즘(Algorithm) 기초 정리 - python

우리가 알고리즘에 대해서 대부분 학교 수업이나 코딩 테스트를 위해 처음 접하는 경우가 많다. 그렇다면, 알고리즘이란 무엇이고 왜 알고리즘을 배워야 할까? 좋은 알고리즘이란, 간단하다.

1. 문제를 해결하는 것
2. 문제를 더 잘 해결하는 것

 

 

알고리즘을 사용하는 이유는 문제를 더 잘 해결하기 위함이다. 따라서 어떻게 문제를 잘 해결할 수 있을지 같이 고민해볼까 한다. 여기서 제공하는 실습 문제만 암기하여 빠르게 작성할 수 있다면, 알고리즘을 공부하기 위한 기초 코딩은 완성 되었다고 할 수있다. 사실 알고리즘을 공부하고자 하는 우리의 목표는 우리가 만들고자 하는 로직을 작성할 수 있게 함에 있다. 따라서 기초적인 알고리즘을 공부하기 전에 파이썬에 대한 기본적인 숙련도가 필요하다고 생각된다. 기본적으로 for문을 1000번이상은 적어보지 못했다면, 당신은 아직 파이썬을 제대로 공부해보지 못했다고 생각한다.

 

 

자료구조 확인하기

 

 

---

 

컴퓨터 알고리즘이란?

컴퓨터 알고리즘이란, 컴퓨터가 어떤 문제를 해결하기 위해서 컴퓨터가 이해할 수 있는 방식으로 정리되어 있는 해결 방법.

쉽게 말하면, 특정 문제를 해결하기 위해 정해둔 일련의 절차라고 할 수 있다. 좋은 알고리즘이란 문제를 잘 해결하는 것이라고 이야기한 적이 있다. 이는 모든 경우에도 잘못된 결과를 도출하면 안 되는 것을 의미한다. 즉, 우리는 모든 경우에 올바른 결괏값을 내는 알고리즘을 만들어야 한다. 정리하면, 우리가 특정 문제를 해결하기 위해 코드를 짠다면, 사실 모든 코드가 알고리즘이라 할 수 있겠다.

 

알고리즘을 왜 하지?

초입자의 관점이라면 가장 큰 관심사는 취업이라고 생각이 된다. 우리가 좋은 회사에 취업을 한다면, 같이 일할 동료들의 대부분은 대표적이 알고리즘은 당연히 알고 있고, 아래와 같은 대화를 편하게 할 수 있다.

 

BFS로 접근하자
분할정복을 사용하자.
여기선 O(lg N)으로 해보자

 

위와 같은 내용에 대해서 알고리즘에 대한 지식 없이는 원활한 소통이 어렵다. 또한 초급 단계에서는 알고리즘을 공부하다보면 자연스럽게 기초코딩 능력도 향상된다. 이 글에서는 알고리즘을 공부하기 위한 최소한의 코딩 능력을 향상시켜줄 수 문제들을 준비했다.

 

 

---

 

 

파이썬 특징

 

 

파이썬은 순차적으로 코드를 실행한다.

print(3)
print(4)
print(1)

```
3
4
1
```

 

 

 

파이썬은 들여 쓰기를 사용한다

PEP 8(파이썬 스타일 가이드)에 따르면, 공백 4개를 사용하는 것을 권장한다.

여러 개발자들이 작업 시 코드 스타일이 다르면 코드에 일관성이 없어진다. 파이썬에서는 PEP8 문서를 통해 가이드를 제공해 준다. 우리는 함수를 쓸 때 왜 스네이크(snake_case)를 쓸까? 클래스를 쓸 때는 왜 카멜 케이스(CamelCase)를 쓸까? 이는 PEP8에서 권장해 주는 방식을 쓰고 있는 것이다.

 

파이썬은 모두가 객체로 이루어진 언어이다.

변수, 함수, 클래스, 모듈 등등이 모두 객체이기 때문에 변수 자체도 값을 가지지 않는다. 변수는 객체를 참조하는 값을 가지고 있는 것이다. 모든 객체는 메모리를 가지고, 객체를 구분할 수 있는 객체의 고유번호를 가진다. 아래의 예를 보자.

 

x = 9
print(id(x)) # 4367483376
print(id(9)) # 4367483376

 

id() 함수는 객체의 식별 번호(identity)를 반환해 주는 함수이다. 위의 결과를 보면, 9의 값이 x로 복사하여 들어가는 것이 아니라, 식별 번호만 복사되어 들어간다고 할 수 있다. 파이썬은 함수 시작/종료 시 객체가 생성 소멸되지 않는다는 점 정도는 이해하자.

 

---

알고리즘 맛보기

 

input() 함수

키보드로 문자열을 입력받아 반환한다.

기본적으로 문자열을 적은 후에 enter를 누르면 반환된다.

 

# 예시1
print('문자열을 적으세요 : ')
val = input()



# 예시2
val = input('문자열을 적으세요 : ')

 

예시 1과 예시 2는 동일하다. 정리하면 input() 내부에 string을 적으면 print를 생략해서 적는 것이 가능하다.

 

 

실습 ) 두 정수의 합 구하기

first_data = int(input('첫 번째 정수를 입력하시오 : '))
second_data = int(input('두 번째 정수를 입력하시오 : '))
print(f`두 정수의 합은 {first_data + second_data} 입니다`)

 

 

 

실습 ) input 데이터를 변수에 넣기

'''
#input
2 4 5
'''


input_data = map(int, input().split(" "))
print(input_data)
# [2, 4, 5]

[a, b, c] = map(int, input().split(" "))
print(a, b, c)
# 2 4 5

 

---

 

조건문 실습으로 이해하기

산술 연산자(operator)와 피연산자(operand)

산술 연잔사는 +나 -, *, / 같은 기호이고, 연산 대상을 피연산자라고 한다. 피연산자의 개수에 따라 아래와 같이 나늰다.

단항 연상자(unary operator) -  ex) a

이항 연산자(binary operator) - ex) a > b

삼항 연산자(ternary operator) - ex) a if b else c

 

# 이 코드와 아래의 코드는 같습니다.
if (조건문):
    t = a
else:
    t = b
print(t)

# 파이썬의 유일한 삼항 연산자 (if ~ else)
t = a if (조건문) else b
print(t)

 

위의 조건문이 참이면 a가 프린트되고, 거짓이면 b가 print 된다.

 

 

조건문 최적화?

 

실습 ) 두 정수를 오름차순으로 변경하기

> a, b를 입력받았다. 나는 a보다 b가 더 큰 수가 들어가도록 코드를 변경하고 싶다. 어떻게 해야 할까?

단일 대입문 이해하기

a = int(input('정수 a 입력하시오 : '))
b = int(input('정수 b 입력하시오 : '))

if a > b:
    a, b = b, a
    
print(f`a값 : {a} , b값 : {b}`)

 

정렬 부분에서 다시 하겠지만, 위의 단일 대입문을 사용하지 않는다면 아래와 같은 방식으로 a와 b의 값을 변경해야 한다.

 

a = int(input('정수 a 입력하시오 : '))
b = int(input('정수 b 입력하시오 : '))

temp = a # 임시 변수 temp를 사용하여 값 변경
a = b
b = temp

 

 

반복문 실습으로 이해하기

 

range() 함수 : 이터러블 객체(반복할 수 있는 객체)를 다루는 함수이다.

+ 대표적인 이터러블 자료형 - list, str, tuple 이 있다.

• range(n) - 0 이상 n 미만인 수를 차례로 나열하는 수열
• range(a, b) - a 이상 b 미만인 수를 차례로 나열하는 수열
• range(a, b, step) - a 이상 b 미만인 수를 step 간격으로 나열하는 수열

 

실습 ) 1부터 n까지의 정수의 합 구하기(while)

n = int(input('1부터 n까지 정수합을 할 n을 적어주세요 : '))

sum_cnt = 0
i = 1

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

print(f`총합은 {sum_cnt}입니다`)

 

 

실습 ) 1부터 n까지의 정수의 합 구하기(for)

n = int(input('1부터 n까지 정수합을 할 n을 적어주세요 : '))

sum_cnt = 0

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

print(f`총합은 {sum_cnt}입니다`)

 

 

실습 ) 1부터 n까지의 정수의 합 구하기 (고등 수학 이용하기 - 가우스 덧셈)

n = int(input('1부터 n까지 정수합을 할 n을 적어주세요 : '))

sum_cnt = n * ( n + 1 ) // 2


print(f`총합은 {sum_cnt}입니다`)

 

 

실습 ) a부터 b까지의 합을 구하시오

a = int(input('정수 a 입력하시오 : '))
b = int(input('정수 b 입력하시오 : '))

if a > b:
    a, b = b, a

sum_cnt = 0

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

print(f`총합은 {sum_cnt}입니다`)

 

반복문 조건문 최적화하기

기본적으로 모든 반복문 내부의 조건을 통해 하나씩 하는 것은 일반적인 코딩 법이다. 반복되는 것이 있다면, //와 %를 활용하여 줄여주면 효율적인 코딩이 가능하다.

 

 

진수

val = 40
b = format(val, '#b') # 10진수를 2진수로 변환
o = format(val, '#o') # 10진수를 8진수로 변환
h = format(val, '#x') # 10진수를 16진수로 변환

b = format(val, 'b')   # 10진수를 2진수로 변환 (Ob 접두 생략)
o = format(val, 'o')  # 10진수를 8진수로 변환 (Oo 접두 생략)
h = format(val, 'x')  # 10진수를 16진수로 변환 (Ox 접두 생략)

2,4,16진수는 위와 같이 라이브러리를 제공한다. 그러나 그 외는 아래와 같이 직접 구현해야 한다.

number = int(input("숫자를 입력하세요: "))
n = int(input("변환할 진수를 입력하세요: "))

answer = ""

while number // n >= 1:
    remain = number % n
    number = number // n
    answer = str(remain) + answer
    if number < n :
        answer = str(number) + answer

print("변환 값: %s(%s)" % (answer, n))

 

 

특정 기준에 따라 변형 후 분류하고, 처음 데이터의 값으로 분류하기.

input_data = ['a12dd', 'B43fdASd', 'c35adf', 'b12asd', 'A56asdf', 'a1231asdf']

# 문제에 맞게 데이터 전처리(아래에서는 데문자를 다 소문자로 바꿈)
mid_data = ['a0012dd', 'b0043fdasd', 'c0035adf', 'b0012asd', 'a0056asdf', 'a1231asdf']
res_data = [[a, 0012, dd], [b, 0043, fdasd], [c, 0035, adf]...]

#res_data로 크기 배교후 성립하면 위치를 바꾸는 구조
def chang_data(data):
    for i in range(3):
        for j in range(len(data)):
            for k in range(j+1, len(data)):
                if data[j][i] > data[k][i]:
                    res_data[j], res_data[k] = res_data[k], res_data[j]
                    input_data[j], input_data[k] = input_data[k], input_data[j] # 같이 넣어준다.

 

중복된 list 지우기

셋으로 만들면, 중복된 부분이 없어진다. 그 후에 다시 list로 만들어 주면 된다.

a = [1, 1, 2, 3, 5, 2]
a = list(set(a))

 

 

 

 Dictionary 자유롭게 다루기

dicrionary의 key값만 print 하시오

>>> x = {'a': 10, 'b': 20, 'c': 30, 'd': 40}
>>> for i in x:
...     print(i, end=' ')
...
a b c d

그냥 하면 위처럼 key만 출력된다.

 

>>> x = {'a': 10, 'b': 20, 'c': 30, 'd': 40}
>>> for key in x.keys():
...     print(key, end=' ')
...
a b c d

.keys()를 활용하면 key만 출력된다.

 

 

dicrionary의 key, value값을 print 하시오

>>> x = {'a': 10, 'b': 20, 'c': 30, 'd': 40}
>>> for key, value in x.items():
...     print(key, value)
...
a 10
b 20
c 30
d 40

 .items()를 활용하면 key와 value 값이 나눠서 출력된다.

 

>>> x = {'a': 10, 'b': 20, 'c': 30, 'd': 40}
>>> for value in x.values():
...     print(value, end=' ')
...
10 20 30 40

values를 활용하면 value만 출력된다.

 

 

아스키코드 변환하기

ord(str) => int

문자를 인자로 받고, 해당 문자에 해당하는 유니코드를 정수 반환한다.

 

chr(int) => str

정수를 인자로 받고, 해당 정수에 해당하는 유니코드 문자를 반환한다.

 

print(ord('a')) # 97
print(chr(97)) # 'a'

 

 

정리

기초적인 파이썬 문제에 대한 정리를 해보았다. 알고리즘에 대한 개념이해도가 높다는 것은 사실상 코딩을 잘하는 것이다. 위의 문제들을 쉽게 풀 수 있다면, 초급을 넘어섰다고 할 수 있겠다. 이제 다음으로 다른 알고리즘에 대한 개념에 대해 이해하러 가보자.