문제 01 모든숫자 더하기
(n * (n + 1))/2
는 1부터 n까지의 합을 구하는 공식이다.
풀이
# 재귀를 이용한 방법
def add(n):
if n is 0:
return n
return add(n-1) + n
# 반복문을 이용한 방법
def add(num):
sum = 0
for n in range(0,num+1):
sum += n
return sum
# 사칙연산을 이용한 방법
def add(num):
half = num/2
sum = (num*half)+half
return int(sum)
# 공식을 이용한 방법 (파이써닉)
def add(num):
return num*(num+1)//2
#//는 정수 나눗셈을 뜻함.
대문자 O 표기법
문제1에서 재귀나 반복문을 사용한 알고리즘은 O(n)이다. 하지만 사칙연산을 사용한 알고리즘은 O(1)이므로 훨 빠르다.
연습문제
- 1부터 n까지 연속한 숫자의 제곱의 합을 구하는 알고리즘. 제곱의 합 공식은
n*(n+1)*(2*n+1)/6
이다.
# for을 사용한 방법
# O(n)
def addSquare(num):
sum = 0
for n in range(0,num+1):
sum += n**2
# 공식을 사용한 방법
# O(1)
def addSquare(num):
return num*(num+1)*(2*num+1)//6
문제 02 최댓값 찾기
주어진 숫자 n개 중 가장 큰 숫자를 찾는 알고리즘을 만들어 보세요.
풀이
# 반복문을 사용한 방법
# O(n) 시간복잡도믄 len(array)와 같다.
def find(array):
biggest = float("-inf")
for item in array:
if biggest < item:
biggest = item
return biggest
응용문제
- 최댓값의 위치를 구하는 알고리즘
def find_index(array):
length = len(array)
biggest_i = 0
for i in range(0,length):
if array[biggest_i] < array[i]:
biggest_i = i
return biggest_i
리스트
리스트는 배열이다. ㅇㅇ `len()`함수가 밖에서 감싸주는게 조금 생소해보인다.
리스트 함수
a = [1,2,3]
len(a) # 3
append(4) # [1,2,3,4]
a.insert(0,5) # 0번 위치에 5를 추가한다.
a.pop(0) # 0번 위치에 있는 자료를 리스트에서 빼내면서 그값을 반환한다. 위치를 지정하지 않으면 마지막 값을 빼내면서 반환한다.
a.clear() # 리스트를 비운다.
2 in a
# 어떤자료가 리스트 a 안에 있는지 확인한다.(x not in a는 반대다.)
# True
문제 03 동명이인 찾기 1
n명의 사람 이름 중에서 같은 이름을 찾아 집합으로 만들어 돌려주는 알고리즘을 만들어 보세요.(이렇게 친절하다고?)
# 예
find_same_name(["샤미드", "쥬피썬더", "부스터","파이어", "파이리", "부스터"])
# {"부스터"}
집합(set)
집합은 리스트와 같이 정보를 여러개 넣어서 보관할 수 있다. 다만, 집합 하나에는 같은 자료가 중복되어 들어가지 않고, 자료의 순서도 의미가 없다.
s = set()
s.add(1)
s.add(2)
s.add(2) # 이미 2가 있기 때문에 중복해서 들어가지 않는다.
len(s) # 2
s == {2,1} # True 자료의 순서가 무관하므로 같은 집합으로 간주한다.
집합함수
len(s) # 집합 s의 길이를 구한다.
s.add(x) # 집합 s에 자료 x를 추가한다.
s.discard(x) # 집합에 자료 x가 있으면 삭제한다. 없으면 변화없음.
s.clear() # 빈 집합으로 만든다.
x in s # 집합 s안에 x라느 자료가 있는지 확인한다.
풀이
# 반복문을 사용한 방법
# O(n**2)... 상당히 마음에 안드는뎅..
def find_same_name(names):
same_name = set()
length = len(names)
for i in range(0,length):
for j in range(i+1,length):
if names[i] == names[j]:
same_name.add(names[i])
return same_name
4개의 배열의 경우의 수는 3+2+1인것을 알 수 있는데, 이는 1+2+3 ... (n-1)로 생각할 수 있다. 문제1의 모든 수를 더하는 공식에 이를 대입하면 손쉽게 경우의 수를 알 수 있다.
연습문제
- n명의 사람들중 두명씩만 뽑아 짝을 짓는다고 할때 짝을 지을수 있는 모든 조합을 출력하는 알고리즘을 만들어 보세요.
def find_same_name(names):
same_name = set()
length = len(names)
for i in range(0,length):
for j in range(i+1,length):
# 이름이 같으면 건너뛴다. 흠...별로 맘에 안들어..
# 근데 뭐가 맘에 안드는지 모르겠으니 넘어가자.
if names[i] == names[j]:
continue;
else:
print(names[i] + '-' + names[j])
find_same_name(["샤미드", "쥬피썬더", "부스터","파이어","부스터"])
다음식을 각각 대문자 O표기법으로 표현해 보세요
65536 => O(1)
- n-1 => O(n)
- 2n**3/10000n => O(n**3)
- 3n**4 - 4n**3-6n+7 => O(n**3)