파이썬을 이용한 알고리즘

요즘은 취업난에 코딩 테스트도 많고 정말 힘든 시기 인듯하다...

그래도 스스로 노력하고, 준비한다면 언젠가 기회는 찾아올 것이라 생각된다!

모두들 화이팅 하자는 의미로 몇 가지 알고리즘에 대해서 준비해보았다.

---

첫 번째

1부터 n까지의 합 구하기

• 합을 기록할 변수를 만들고 0을 저장
• n을 1부터 1씩 증가하면서 반복
• 반복문 안에서 합을 기록할 변수에 1씩 증가된 값을 더함
• 반복이 끝나면 합을 출력

# O(n)
def sum1(n):
    total = 0
    for i in range(1, n+1):
        total += i
    
    return total

# 시간측정
import time

start_time = time.time()

sum1(10000000) # 5050

end_time = time.time()
print("time : ", end_time - start_time)

 

time :  0.45471787452697754

---

# n(n+1)/2
# O(1)

def sum2(n):
    return int(n*(n+1)/2)

start_time = time.time()

sum2(10000000)

end_time = time.time()
print("time : ", end_time - start_time)

 

time :  0.0

 

하나의 문제로 두 개의 해답을 작성해보았다.

같은 결과를 내는 해답이라도 속도의 측면에서 차이가 있다.

여러분도 서로 비교해가면서 문제를 해결해나가면 좋을 것 같다.

---

두 번째

중복 데이터 삭제

다음의 결과를 도출해내시오.

names = ["Dave", "David", "Anthony", "David", "Dave"]
find_same_name(names)
결과 : ["Dave", "David", "Anthony"]

• set 자료형 사용하지 않기
• del names[인덱스]

# O(n^2)
def find_same_name(name_list):
    for idx, name in enumerate(name_list):
        for idx2 in range(idx+1, len(name_list)):
            if(name == name_list[idx2]):
                del name_list[idx2]
                
    return name_list

 

# O(n)
def find_same_name1(name_list):
    nlist = []
    for i in name_list:
        if i not in nlist:
            nlist.append(i)
    return nlist

 

names = ["Dave", "David", "Anthony", "David", "Dave"]
namelist = find_same_name1(names)
print("결과 : ", namelist)

 

결과 :  ['Dave', 'David', 'Anthony']

---

세 번째

최댓값 구하기, 최대값 위치 구하기

# O(n)
def find_max(n):
    max_val = n[0]
    length = len(n)
    
    for i in range(1, length):
        if n[i] > max_val:
            max_val = n[i]
    
    return max_val

data = [17, 92, 18, 33, 58, 7, 33, 42]
print(find_max(data))

 

92

 

 

# 위치 구하기

def find_max_idx(n):
    max_idx = 0
    length = len(n)
    
    for i in range(1, length):
        if n[i] > n[max_idx]:
            max_idx = i
    
    return max_idx

data = [17, 92, 18, 33, 58, 7, 33, 42]
print(find_max_idx(data))

 

1

 

---

네 번째

숫자 야구 프로그램

• 술래(컴퓨터)는 임의의 숫자 3개를 준비
• 숫자는 절대 중복되어서는 안된다.
• 숫자는 1~9까지로 한다.

"""
숫자 야구 게임을 시작합니다.!!!
--------------------------------
정답 : 369
숫자 3자리 입력 : 123
결과 : [0] 스트라이크 [1] 볼 : 123

숫자 3자리 입력 : 345
결과 : [1] 스트라이크 [0] 볼 : 345

숫자 3자리 입력 : 127
결과 : 아웃 :127

숫자 3자리 입력 : 369
결과 : 축하합니다.
횟수 : 3
걸린시간 : 10초
"""

 

import random

number = set()
while len(number)<3:
    number.add(random.randint(1,9))

print(number)
    
listnum = list(number)
com = 100*listnum[0]+10*listnum[1]+listnum[2]

count = 0
strike = 0
ball = 0

print("숫자야구게임을 시작합니다 !!!")
print("---------------------------")

start_time = time.time()

while (strike < 3):
    num = str(input("숫자 3자리를 입력하세요 : "))

    strike = 0
    ball = 0

    for i in range(0, 3):
        for j in range(0, 3):
            if (num[i]==str(listnum[j]) and i==j):
                strike+=1
            elif (num[i] == str(listnum[j]) and i != j):
                ball+=1

    if(strike==0 and ball==0):
        print("결과 : 아웃 : ", num)
    else:
        print("결과 : Strike [",strike, "] Ball : [",ball, "] ", num)
    
    count += 1
print("---------------------------")

end_time = time.time()
print("횟수 : ",count)
print("걸린시간 ", int(end_time - start_time), "초")

 

{9, 2, 3}
숫자야구게임을 시작합니다 !!!
---------------------------
숫자 3자리를 입력하세요 : 923
결과 : Strike [ 3 ] Ball : [ 0 ]  923
---------------------------
횟수 :  1
걸린시간  6 초

---

import random 
import time


def num_bb():
    start_time = time.time()
    r_num01 = str(random.randrange(1,10))
    r_num02 = str(random.randrange(1,10))
    r_num03 = str(random.randrange(1,10))
    
    while (r_num01 == r_num02):
        r_num02 = int(random.randrange(1, 10))
    while (r_num01 == r_num03 or r_num02 == r_num03):
        r_num03 = int(random.randrange(1, 10))

#여기까지 중복안되게 난수생성하는 문제 해결        
    l_rn= [r_num01, r_num02, r_num03]
    
    t_c, s_c, b_c = 0, 0, 0
    
    print (r_num01, r_num02, r_num03)
    print("숫자야구게임을 시작하겠습니다!!!")
    print("---------------------------")
    
    
    while s_c<3 :
        s_c, b_c = 0, 0
        i_n = str(input("숫자 세자리를 입력하세요 : "))
        for i in range(0,3):
            for j in range(0,3):
                
                if i_n[i] == str(l_rn[j]) and i == j:
                    
                    s_c += 1
                elif i_n[i] == str(l_rn[j]) and i != j:
                    
                    b_c += 1

        print("결과 : [", s_c, "] 스트라이크 [", b_c, "] 볼", "입력숫자 : ", i_n )
        t_c += 1
        
    print("---------------------------")
    end_time= time.time()
    print(t_c, "번 만에 정답을 맞추셨습니다. 끝날때까지 걸린 시간은 ", end_time - start_time )
        

    
num_bb()

 

8 1 7
숫자야구게임을 시작하겠습니다!!!
---------------------------
숫자 세자리를 입력하세요 : 123
결과 : [ 0 ] 스트라이크 [ 1 ] 볼 입력숫자 :  123
숫자 세자리를 입력하세요 : 456
결과 : [ 0 ] 스트라이크 [ 0 ] 볼 입력숫자 :  456
숫자 세자리를 입력하세요 : 817
결과 : [ 3 ] 스트라이크 [ 0 ] 볼 입력숫자 :  817
---------------------------
3 번 만에 정답을 맞추셨습니다. 끝날때까지 걸린 시간은  34.036991119384766

---

import random

# 난수 생성
num = [1, 2, 3, 4, 5, 6 ,7, 8 ,9]

ran1 = random.randint(0,8)
num1 = str(num.pop(ran1))

ran2 = random.randint(0,7)
num2 = str(num.pop(ran2))

ran3 = random.randint(0,6)
num3 = str(num.pop(ran3))

number = [num1, num2, num3]
print(number)

# 값 초기화
try_cnt = 0 
strike_cnt = 0 
ball_cnt = 0 

print("숫자야구게임을 시작합니다")
print("---------------------------")
start_time = time.time()
while(strike_cnt < 3):
    num_input = str(input("숫자 3자리 입력 : "))
    
    strike_cnt = 0
    ball_cnt = 0
    
    for i in range(0, 3):
        for j in range(0, 3):
            if num_input[i] == str(number[j]) and i == j: #Strike 카운터
                 strike_cnt += 1
            
            elif num_input[i] == str(number[j]) and i !=j: #Ball 카운터
                ball_cnt += 1
        
    print("결과:", "[", strike_cnt, "]","Strike", "[", ball_cnt, "]", "Ball")
    try_cnt += 1 


print(try_cnt, "번 만에 맞추셨습니다!")
end_time = time.time()
print("걸린 시간", round(end_time - start_time), "초")

 

['2', '4', '7']
숫자야구게임을 시작합니다
---------------------------
숫자 3자리 입력 : 123
결과: [ 0 ] Strike [ 1 ] Ball
숫자 3자리 입력 : 742
결과: [ 1 ] Strike [ 2 ] Ball
숫자 3자리 입력 : 247
결과: [ 3 ] Strike [ 0 ] Ball
3 번 만에 맞추셨습니다!
걸린 시간 22 초

---

# 0이 나오면 안됨
import random
import time

numlist = list(range(0, 9))
com = random.sample(numlist, 3)
print(com)

trynum = 0

start_time = time.time()

while True :
    answer = int(input("서로 다른 세 개의 숫자를 입력하세요! "))
    fst_ans = answer // 100
    snd_ans = (answer-fst_ans*100) // 10 
    trd_ans = answer % 10
    ans_list = [fst_ans, snd_ans, trd_ans]
    strike = 0
    ball = 0
    trynum += 1

    if ans_list == com :
        print(answer, " : 정답♥")
        print("시도 횟수 : ", trynum, "회")
        break
    else :
        for i in range(0, 3) :
            if ans_list[i] == com[i] :
                strike += 1
            elif ans_list[i] in com :
                ball += 1
    
    if strike+ball > 0 :
        print(answer, " : ", strike, "스트라이크", ball, "볼")  
    else :
        print(answer, " : ", "아웃")

end_time = time.time()
print("걸린 시간 : ", int(end_time - start_time), "초")

 

[8, 0, 4]
서로 다른 세 개의 숫자를 입력하세요! 123
123  :  아웃
서로 다른 세 개의 숫자를 입력하세요! 456
456  :  0 스트라이크 1 볼
서로 다른 세 개의 숫자를 입력하세요! 804
804  : 정답♥
시도 횟수 :  3 회
걸린 시간 :  41 초

---

import random

# 정답 생성
answer = []        
while len(answer) < 3:
    numbers = random.randint(1, 9)
    
    if str(numbers) not in answer:
        answer.append(str(numbers))

print(answer)

user_input = []
strike = 0
ball = 0
cnt = 0
starttime = time.time()

print("   숫자 야구 게임을 시작합니다 !  ")
print("==================================")

# 스트라이크 볼 잡기
while strike < 3:
    
    user_input = str(input("숫자 3자리를 입력하세요 : "))
    
    strike = 0
    ball = 0
    
    for i in range(3):
        for j in range(3):
            if (answer[i] == user_input[j]) and (i == j):
                strike += 1
            elif (answer[i] == user_input[j]) and (i != j):
                ball += 1
    
    # 결과
    if strike == 3:
        print("결과 : 정답입니다 !\n")
    elif strike==0 and ball==0:    
        print("결과: 아웃 !")
    else:
        print("결과 : ",strike, "스트라이크 ",ball,"볼\n"  )
    
        
    cnt += 1

endtime = time.time()
    
print("시도 횟수 : ",cnt,"번")
print("걸린 시간", endtime-starttime)  

 

['8', '1', '2']
   숫자 야구 게임을 시작합니다 !  
==================================
숫자 3자리를 입력하세요 : 123
결과 :  0 스트라이크  2 볼

숫자 3자리를 입력하세요 : 812
결과 : 정답입니다 !

시도 횟수 :  2 번
걸린 시간 7.9829559326171875

---

import random

com = [i for i in range(3)]

# 중복처리, 임의의 숫자, 1~9
i = 0
while(i < 3):
    com[i] = str(random.randrange(1, 9, 1))
    
    if(i==1):
        if(com[i] == com[i-1]):
            i -= 1
            
    if(i==2):
        if(com[i] == com[i-1] or com[i] == com[i-2]):
            i -= 1
            
    i += 1
    
print(com)

print("숫자 야구를 시작합니다!!")
print("--------------------------")

strike = 0
ball = 0
while(True):
    user = str(input("숫자 3자리 입력 : "))
    strike, ball = 0,0
    
    if(user == ""):
        print("\n다시 입력해 주세요\n")
        continue
        
    if(len(user) != 3):
        print("\n숫자 3자리만 입력하세요\n")
        continue
        
    if(user.isalpha()):
        print("\n숫자만 입력하세요\n")
        continue
    
    for i in range(3):
        if (com[i] == user[i]):
            strike += 1
            
    if(com[0] == user[1] and com[0] == user[2]):
        ball += 1
        
    if(com[1] == user[0] and com[1] == user[2]):
        ball += 1
        
    if(com[2] == user[1] and com[2] == user[0]):
        ball += 1
        
    if strike == 3:
        print("축하합니다.")
        break
    elif strike == 0 and ball == 0:
        print("아웃 : ", user)
    else:
        print("{}스트라이크 {}볼".format(strike, ball))

다양한 방법으로 숫자 야구 프로그램을 만들어보았다.

사람마다 생각하는 부분이 다르기 때문에 코드 또한 천차만별이다.

---

마지막

피보나치수열

피보나치수열은 0과 1로 시작되며, 다음 피보나치 수는 바로 앞의 두 피보나치 수의 합이 된다.

0 1 1 2 3 5 8 13 21 34 55 ...

def Fibonacci_sequence(n):
    FS = []
    a1, a2=0, 1
    FS.append(a1)
    FS.append(a2)
    
    for i in range(n-2):
        a3 = FS[i] + FS[i+1]
        FS.append(a3)
    print("피보나치 수열 : ", FS)
    
Fibonacci_sequence(15)

 

피보나치 수열 :  [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

---

def Fibo(n):
    F = [0.1]
    a,b = 0,1
    
    for i in range(1,n-1):
        a,b = b, a+b
        F.append(b)
    print("피보나치 수열 : ", F)
    
Fibo(15)

 

피보나치 수열 :  [0.1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

---

a = 0
b = 1

for _ in range(0,10):
    print(a)
    temp = a
    a = b
    b = temp + b

 

0
1
1
2
3
5
8
13
21
34

피보나치수열은 알고리즘에서 많이 나오는 문제라고 들었다.

한 번쯤 들어본 사람도 많이 있을 것이라 생각된다.

간단하게 알고리즘에 대해 풀어보았으니 또 복습하고 새로운 알고리즘에 대해서 학습해야겠다!

그럼 다음 시간에~~ 안녕!!