문제 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)

results matching ""

    No results matching ""