시행착오 기술 블로그

문제

풀이

2xn 사각형

n=1 이면 f(1) =1
n=2 이면 f(2) = 1 + f(1) = 2
n=3 이면 f(3) = f(2) +f(1) = 3
n=4 이면 f(4) = f(3) + f(2) = 5

점화식
f(n) = f(n-1) + f(n-2)

코드

n = int(input())

if n <= 2:
    print(n)
else:
    memo = [0 for i in range(n + 1)]
    memo[1] = 1
    memo[2] = 2
    for i in range(3, n + 1):
        memo[i] = memo[i - 1] + memo[i - 2]

    print(memo[n] % 10007)

이 문제도 역시 재귀로 하면 시간초과 발생

bottom up 방식으로 반복문 이용하여 풀어내기

1. lambda 익명 함수: 한줄로 구현하게 해주는 함수 (with map, reduce)

일반적인 함수는 아래처럼 구현하고 호출한다.

def hap(x,y):
return x+y

hap(2,5) # 2+5 = 7 return

lambda 함수를 이용하여 함수를 구현하면 아래처럼 사용 가능하다.

(lambda x,y: x+y)(2,5) # return 7

 lambda함수 내에서 조건문 사용 가능하다.

a = lambda x, y: x*y if x>0 else y

a(4, 8) # 32
a(-4, 8) # 8

다른 내장함수와의 활용

1. map

rambda는 map 함수와 함께 쓰면 기능이 확장될 수 있다.

map 이란 map(함수, 리스트) 형태로 사용이 가능하다.

list(map(lambda x: x**2, range(5)))
[0, 1, 4, 9, 16]

2. reduce

rambda는 reduce(함수, 시퀀스) 형태로 사용 가능하다.

여기서 시퀀스란 문자열, 리스트, 튜플 등을 의미한다.

reduce(lambda x, y: x+y, range(5))
0+1+2+3+4 = 10 return

reduce(lambda x, y: y+x, 'abcde')
edcba 역순으로 return

3. filter

rambda는 filter (함수, 리스트) 형태로 사용 가능하다.

리스트에 들어있는 원소들을 함수에 적용시켜 결과가 참인 값들로 새로운 리스트를 만들어 준다.

list(filter(lambda x: x<5, range(10))
[0, 1, 2, 3, 4] # 5 미만의 값만 필터링 됨.

list(filter(lambda x: x%2 != 0, range(10)))
[1, 3, 5, 7, 9] # 홀수 값만 필터링 됨.

4. max, min

key를 이용해 리턴할 값의 기준을 정한다.

strings = ["abc", "abcdef", "abcedfgh"]
longest = max(strings, key = lambda x:len(x))

numbers = [1, 10, 100, 1000]
biggest = max(numbers, key = lambda x:x))

2. zip 데이터를 엮어주는 함수

zip은 파이썬 내장함수로 데이터를 엮을 때 사용한다.

아래 코드는 numbers 리스트와 letters 리스트를 zip()  함수의 인자로 넘겨서 호출 후에, 

for문으로 zip() 함수의 반환값을 대상으로 루프를 돌면서 튜플을 차례로 출력한다.

numbers = [1, 2, 3]
letters = ['A', 'B', 'C']

for pair in zip(numbers, letters):
	print(pair)
    
(1, 'A')
(2, 'B')
(3, 'C')

 zip() 기능:

1. 여러 그룹의 데이터를 반복문 한번에 처리할 수 있음!! 병렬처리 가능!!!

for number, upper, lower in zip("12345", "ABCDE", "abcde"):
	print(number, upper, lower)

1 A a
2 B b
3 C c
4 D d
5 E e

2. zip() 함수를 이용해 upzip 가능하다.

zip()

numbers = (1, 2, 3)
letters = ('A', 'B', 'C')

pairs = list(zip(numbers, letters))
print(pairs)

[(1, 'A'), (2, 'B'), (3, 'C')]

unzip

pair = [(1, 'A'), (2, 'B'), (3, 'C')]

numbers, letters = zip(*pairs)
numbers # (1,2,3)
letters # ('A', 'B', 'C')

3. zip() 과 2개의 리스트 이용해 딕셔너리 생성 가능

keys = [1, 2, 3]
valuse = ['a', 'b', 'c']

dict(zip(keys, values))
# {1:'A', 2:'B', 3:'C'} return

dict(zip(["year", "month", "date"],[2020, 8, 7]))

# {"year":2022 , "month": 8, "date": 7} return

# 주의사항

길이가 동일한 리스트를 사용하지 않으면, 긴 쪽의 인자들이 버려질 수 있다.

3. queue (PriorityQueue...)

4. heapq 

5. startswith( ) 와 endswith( )

startswith( ) : 시작하는 문자열이 동일하면 True, 아니면 False를 반환한다.

endswith( ) : 끝나는 문자열이 동일하면 True, 아니면 False를 반환한다.

file_name = "01-stduent.jpg"

file_name.startwith("01") # True
file_name.endwith(".jpg") # False

6. replace( ' * ', ' ? ' )

replace(바꿀 대상, 바꾸려는 문자열)

file_name = "01-student.jpg"

file_name.replace(".jpg", ".png")

7. count(개수를 알고자 하는 문자)

['a', 'ab','abc'].count('a')  # 1

'ababaaa'.count('a')  # 5

8. compile(query)

9. try: ~  except 예외처리

try:
    실행할 코드
except:
    예외가 발생했을 때 처리하는 코드

try:
    x = int(input('나눌 숫자를 입력하세요: '))
    y = 10 / x
    print(y)
except:    # 예외가 발생했을 때 실행됨
    print('예외가 발생했습니다.')

10. 슬라이싱

역순으로 출력하기 위해서는 step을 -1로 지정하면 된다

a[ : : -1]

사용자 입력 input()

입력값 받기 input() 함수 사용 (시간초과 날 확률 높음)

favoritSport = input('가장 좋아하는 스포츠')
print(favoritSport)

favoritNumber = int(input('가장 좋아하는 숫자'))
print(favoritNumber)

input() 함수로 받은 값은 항상 문자열이다.

따라서 형 변환을 하여 필요한 자료형으로 사용할 수 있다. int ( ), bool ( ), float ( )

age = int(input())
checked = bool(input())
height = float(input())

print(type(age)) # <class 'int'>
print(type(checked)) # <class 'bool'>
print(type(height)) # <class 'float'>

사용자 입력 sys.stdin.readline()

1. 한 개의 정수 입력

import sys
a = int(sys.stdin.readline())

2. 여러 개의 정수 입력받아 변수에 각각 저장

import sys
a, b, c = map(int, sys.stdin.readline().split())

map ( 함수, 객체 )

반복 가능한 객체의 아이템들을 각각 해당 함수로 처리해준다.

3. 문자열 입력 받아 정수형 리스트로 변환하기

import sys
data = list(map(int, sys.stdin.readline().split())

4. 문자열 n줄 입력 받아 2차원 정수형 리스트로 변환하기

import sys
data = []

num = int(sys.stdin.readline())

for i in range(num):
	data.append(list(map(int, sys.stdin.readline().split())))

5. 문자열 n 줄 입력받아 문자열 리스트에 저장하기

strip( ) 문자열의 앞과 뒤에 있는 공백문자 제거하는 함수

import sys

n = int(sys.stdin.readline())

data = [sys.stdin.readline().strip() for i in range(n)]

파일 입출력

writelines()

readlines()

readline()

01. random.sample( range(n,m),  cnt)

n 부터 m-1 사이 랜덤값을 꺼내 cnt 길이의 리스트 반환

import random

randList = random.sample(range(1, 11), 10)
print(randList)

02. random.randrange(number) 

0부터 number -1 사이의 랜덤값 1개 반환

import random

print(random.randrange(100)) # 1~99 사이의 값 1개 반환

list

1. 리스트 선언

대괄호와 콤마를 이용하여 리스트를 선언한다.

students = ['홍길동', '김철수']
numbers = [1,2,3,4,5]
mixed = [1, '이', 3, [4,5,6]]

2. 리스트 아이템 조회

인덱스를 이용하여 아이템 조회가 가능하다. 인덱스는 0부터 부여됨.

numbers = [1,2,3,4,5]

print(numbers[0]) # 1

3. 리스트 길이

리스트 안에 들어있는 아이템의 갯수를 의미한다. len( ) 내장함수 이용.

numbers = [1,2,3,4,5]

len(numbers) # 5

4. 리스트 for 반복문

1차원 리스트는 변수 1개면 됨

numbers = [1,2,3,4,5]

for n in numbers:
    print(n)
    
for i in range(len(numbers)):
    print(numbers[i])

2차원 리스트는 변수 2개 주면 데이터에 쉽게 접근할 수 있음 (이중반복문 또는 인덱스 불필요)

# -------------------------
# 이차원 리스트 

studentNumbers = [[1,20], [2,21], [3,20]]

for classNo, cnt in studentNumbers:
    print( classNo, cnt)

5. 리스트 enumerate( ) 함수

인덱스와 아이템을 한번에 조회할 수 있는 내장함수

sports = ['농구', '축구', '야구', '배구', '마라톤']

for idx, value in enumerate(sports):
    print('{} : {}'.format(idx, value))
    
    
# 0 : 농구
# 1 : 축구
# 2 : 야구
# 3 : 배구
# 4 : 마라톤

6. 아이템을 리스트 맨 뒤에 추가하기 append( )

append( ) 함수를 사용하면 리스트에 아이템을 추가할 수 있다.

sports = ['농구', '축구', '야구', '배구', '마라톤']

sports.append('수영')
print(sports) # ['농구', '축구', '야구', '배구', '마라톤', '수영']

7. 아이템을 특정 인덱스 위치에 추가하기 insert( )

sports = ['농구', '축구', '야구', '배구', '마라톤']

sports.insert(0, '수영') # 0번 인덱스에 데이터 추가, 뒤로 밀려남
print(sports) # ['수영', '농구', '축구', '야구', '배구', '마라톤']

8. 리스트의 마지막 아이템을 삭제하기 pop( )

sports = ['농구', '축구', '야구', '배구', '마라톤']

last = sports.pop() # 마지막 데이터 삭제됨
print(sports) # ['농구', '축구', '야구', '배구']
print(last) # 마라톤

9. 리스트의 특정 인덱스 값을 삭제하기 pop( idx )

sports = ['농구', '축구', '야구', '배구', '마라톤']

data = sports.pop(3) # 인덱스 3인 데이터 삭제됨
print(sports) # ['농구', '축구', '야구', '마라톤']
print(data) # 배구

10. 리스트의 특정 아이템을 삭제하기 remove( value )

# 해당 아이템이 중복되어 들어있다면 가장 앞에 있는 값을 삭제한다.

# 리스트에 해당 아이템이 존재하지 않으면 오류 발생.

sports = ['농구', '축구', '야구', '배구', '마라톤', '배구', '배구']

data = sports.remove('배구') # '배구' 라는 값 삭제
print(sports) # ['농구', '축구', '야구', '마라톤', '배구', '배구']
print(data) # None

# 중복된 아이템 모두 삭제하고자 할 때 while 문 + in 메서드를 사용한다.

sports = ['농구', '축구', '야구', '배구', '마라톤', '배구', '배구']

item = '배구'
while item in sports:
    sports.remove(item)
    
print(sports) # ['농구', '축구', '야구', '마라톤']

11. 리스트 연결하기

(1) extend( ): 리스트1에 리스트2를 연결하여 리스트1을 확장한다.

groupA = ['a', 'b', 'c']
groupB = [1, 2, 3, 4, 5]

groupA.extend(groupB)

print(groupA) # ['a', 'b', 'c', 1, 2, 3, 4, 5]
print(groupB) # [1, 2, 3, 4, 5]

(2) 뎃셈 연산자 +: 리스트1과 리스트 2를 연결하여 리스트3을 생성한다.

groupA = ['a', 'b', 'c']
groupB = [1, 2, 3, 4, 5]

groupC = groupA + groupB

print(groupA) # ['a', 'b', 'c']
print(groupB) # [1, 2, 3, 4, 5]
print(groupC) # ['a', 'b', 'c', 1, 2, 3, 4, 5]

12. 리스트 아이템 정렬하기 sort( ) 오름차순 / sort ( reverse = True ) 내림차순

문자 숫자 모두 정렬 가능하다.

groupA = ['cat', 'apple', 'banana']
groupB = [4, 1, 3, 2, 5]

groupA.sort()
groupB.sort(reverse = True)

print(groupA) # ['apple', 'banana', 'cat']
print(groupB) # [5, 4, 3, 2, 1]

13. 리스트 아이템 순서 뒤집기 reverse( )

sports = ['농구', '축구', '야구', '배구', '마라톤', '배구', '배구']
sports.reverse()
print(sports) # ['배구', '배구', '마라톤', '배구', '야구', '축구', '농구']

14. 리스트 슬라이싱 [n:m]

# list의 인덱스 n 부터 m-1까지 슬라이싱한다.

sports = ['농구', '축구', '야구', '배구', '마라톤', '배구', '배구']
print(sports[1:3]) # ['축구', '야구']

# 인덱스를 생략하면 끝까지를 의미한다.

sports = ['농구', '축구', '야구', '배구', '마라톤', '배구', '배구']

# 인덱스 안쓰면 끝까지를 포함
print(sports[:3])  # ['농구', '축구', '야구']
print(sports[3:])  # ['배구', '마라톤', '배구', '배구']

# 전체
print(sports[:])  # ['농구', '축구', '야구', '배구', '마라톤', '배구', '배구']

# 인덱스는 음수도 가능하다.

sports = ['농구', '축구', '야구', '배구', '마라톤', '배구', '배구']

# 음수도 가능
print(sports[-5:-2])  # ['야구', '배구', '마라톤']

# 슬라이싱의 단계(step)를 설정할 수 있다.

sports = ['농구', '축구', '야구', '배구', '마라톤', '배구', '배구']

print(sports[1:6:2]) # ['축구', '배구', '배구']
print(sports[::2]) # ['농구', '야구', '마라톤', '배구']

# 슬라이싱을 이용해 아이템을 변경할 수 있다.

sports = ['농구', '축구', '야구', '배구', '마라톤', '배구', '배구']
sports[:2] = ['basket ball', 'soccer']

print(sports) # ['basket ball', 'soccer', '야구', '배구', '마라톤', '배구', '배구']

15. 리스트 슬라이싱 리스트명[ slice(n,m) ]

sports = ['농구', '축구', '야구', '배구', '마라톤', '배구', '배구']
sports[slice(2,4)]

print(sports) # ['농구', '축구', '야구', '배구', '마라톤', '배구', '배구']
print(sports[slice(2,4)]) # ['야구', '배구']

16. 리스트 곱셈 연산 list * n

리스트 내 아이템을 n배로 늘린다.

num = [1, 2]
print(num*2) # [1, 2, 1, 2]

17. 리스트 아이템의 위치(인덱스) 찾기 index( value )  또는   index( value, startIndex, endIndex )

범위 내 가장 맨 앞에 있는 아이템의 인덱스를 반환한다.

아이템이 없으면 오류 반환

sports = ['농구', '축구', '야구', '배구', '마라톤', '배구', '배구']

sports.index('배구') # 3
sports.index('배구', 4, 6) # 5

18. 리스트 내 특정 아이템의 개수를 알아내기 count( )

sports = ['농구', '축구', '야구', '배구', '마라톤', '배구', '배구']

print(sports.count('배구')) # 3
print(sports.count('야구')) # 1
print(sports.count('수영')) # 0

19. 리스트 내 특정 아이템 삭제하기 del ( )

# 범위 내 가장 맨 앞에 있는 아이템을 삭제한다.

sports = ['농구', '축구', '야구', '배구', '마라톤', '배구', '배구']

del sports[0] # 농구 삭제
del sports[0] # 축구 삭제
del sports[0] # 야구 삭제
print(sports) # ['배구', '마라톤', '배구', '배구']

# 슬라이싱으로 다수 아이템 삭제가 가능하다.

sports = ['농구', '축구', '야구', '배구', '마라톤', '배구', '배구']

del sports[4:] # '마라톤', '배구', '배구' 삭제
print(sports) # ['농구', '축구', '야구', '배구']

tuple

1. 튜플 선언은 소괄호 ( )

튜플은 한번 선언되면 아이템을 수정하거나 삭제할 수 없다

다양한 자료형을 혼합하여 아이템으로 사용할 수 있다.

numbers = (1, 2, 3, 4, 5, [1,2,3], (1,2,3))
 
print(numbers) # (1, 2, 3, 4, 5, [1, 2, 3], (1, 2, 3))
numbers[0] = 0 # 불가

2. 튜플 아이템 조회하기

인덱스 이용하여 해당 데이터 조회가 가능하다.

numbers = (1, [1,2,3], (1,2,3))
 
print(numbers[0]) # 1
print(numbers[1]) # [1, 2, 3]
print(numbers[2]) # (1, 2, 3)

3. 튜플 in, not in 키워드 사용하기

# 아이템 존재 유무를 확인할 수 있다.

sports = ['농구', '축구', '야구', '배구']

print('농구' in sports) # True
print('수영' in sports) # False

# 문자열 에서도 in, not in 키워드 사용가능하다.

pythonStr = '파이썬 python은 고급프로그래밍 언어로, ' \
            '플랫폼에 독립적이며 인터프리터식 대화형 언어이다. '\
            '파이썬이라는 이름은 코미디 이름에서 따온 것이다.'
            
print('파이썬' in pythonStr) # True
print('파이선' in pythonStr) # False
print('python' in pythonStr) # True

4. 튜플 길이 확인하기 len ( )

sports = ('농구', '배구', '야구')
print(len(sports)) # 3

5. 튜플 결합하기

튜플은 한번 선언되면 수정할 수 없기 때문에 extend 안됨. 덧셈연산자로 결합 가능하다.

sports1 = ('농구', '배구', '야구')
sports2 = ('축구', '당구', '수영')

sports3 = sports1 + sports2

print(sports1) # ('농구', '배구', '야구')
print(sports2) # ('축구', '당구', '수영')
print(sports3) # ('농구', '배구', '야구', '축구', '당구', '수영')

튜플이 아닌 데이터를 튜플과 결합하기 위해선, 형변환이 필요하다.   튜플 형변환   (num , )

numbers = (1,2,3)
num = 10

total = numbers + num # 오류 발생

total = numbers + (num,) # 형이 다른 데이터는 튜플로 형변환 한 후 결합할 수 있다.
print(total) # (1, 2, 3, 10)

6. 튜플 슬라이싱 하기

리스트 슬라이싱과 동일. 단, 슬라이싱을 통한 데이터 변경, 수정은 안됨. 

튜플을 선언할 떈 소괄호 ( ) 썼지만, 아이템에 접근할 땐 대괄호 [ ] 를 사용한다.

numbers = (1,2,3,4,5,6,7,8,9,10)

print(numbers[0:5]) # (1, 2, 3, 4, 5)
print(numbers[5:9]) # (6, 7, 8, 9)
print(numbers[:]) # (1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
print(numbers[-5:]) # (6, 7, 8, 9, 10)

7. 튜플 아이템 정렬하기 sort( ) 와 sorted( )

sort( ) : 원본을 수정함. 튜플은 수정이 불가하기 때문에, 리스트로 형변환 후 정렬 가능하다.

numList = [4,7,2,8,9,3,1,10]
numTuple = (4,7,2,8,9,3,1,10)

numList.sort() # 리스트는 sort() 가능
numTuple.sort() # 튜플은 sort() 불가능

print(numList) # [1, 2, 3, 4, 7, 8, 9, 10]
print(numTuple) # X

sorted( ) : 리스트로 반환해줌. 튜플의 아이템을 정렬하여 리스트로 반환해준다. 따라서 튜플 자료형에서도 사용가능

numList = [4,7,2,8,9,3,1,10]
numTuple = (4,7,2,8,9,3,1,10)

newList = sorted(numList) # 리스트는 sort() 가능
newTuple = sorted(numTuple) # 튜플은 sort() 불가능

print(newList) # [1, 2, 3, 4, 7, 8, 9, 10]
print(newTuple) # [1, 2, 3, 4, 7, 8, 9, 10]

8. 튜플 for 반복문 이용하기

이중 튜플은 변수를 2개 둬서 값을 조회할 수 있다. 인덱스 없이 가능

studentNum = ( (1,20), (2,21), (3,20) )

for num, stu in studentNum:
    print(num, stu)
    
# 1 20
# 2 21
# 3 20

9. 튜플과 리스트의 형변환

리스트와 튜플은 자료형 변환이 가능하다. list( ) tuple( )

numList = [1,2,3,4,5,6,7,8,9,10]
numTuple = tuple(numList)
numList2 = list(numTuple)

print(type(numList))  # <class 'list'>
print(type(numTuple)) # <class 'tuple'>
print(type(numList2)) # <class 'list'>

dict

1. 딕셔너리 선언. 중괄호 { }를 이용한다.

딕셔너리는 key와 value를 이용하여 자료를 관리한다.

student1 = {'이름': '김철수', '나이':12, '취미':['독서', '노래부르기']}
student2 = {'이름': '이영희', '나이':5, '취미':['노래부르기', '영화보기']}
student3 = {'이름': '홍길동', '나이':20, '취미':['피아노', '노래부르기']}

students = {1:student1, 2:student2, 3:student3}

2. 딕셔너리 조회하기

# key 값을 이용하여 value를 조회할 수 있다. 딕셔너리는 인덱스로 조회 불가능

student = {'이름': '김철수', '나이':12, '취미':['독서', '노래부르기']}

print(student['이름']) # 김철수
print(student['나이']) # 12
print(student['취미']) # ['독서', '노래부르기']


print(student['취미'][0]) # 독서
print(student['취미'][1]) # 노래부르기

# get (key)를 이용해 value를 조회할 수 있다.

딕셔너리에 key가 없어도 에러가 발생하지 않는다. None 반환

student = {'이름': '김철수', '나이':12, '취미':['독서', '노래부르기']}

print(student.get('이름')) # 김철수
print(student.get('영어 이름')) # None

3. 딕셔너리 추가하기

key-value 쌍으로 데이터를 추가할 수 있다.

myInfo = { } # 딕셔너리 선언

myInfo['이름'] = '김철수'
myInfo['나이'] = 12
myInfo['취미'] = ['노래부르기', '피아노']

print(myInfo) # {'이름': '김철수', '나이': 12, '취미': ['노래부르기', '피아노']}

4. 딕셔너리 수정하기

같은 key로 데이터를 입력할 경우, 값이 수정된다.

myInfo = { } # 딕셔너리 선언

myInfo['이름'] = '김철수'
myInfo['나이'] = 12
myInfo['나이'] = 20

print(myInfo) # {'이름': '김철수', '나이': 20}

5. keys() 와 values()

전체 key 반환, 전체 value 반환해주는 함수로, list( )로 형 변환 해줘야 리스트 자료형 된다.

student = {'이름': '김철수', '나이':12, '취미':['독서', '노래부르기']}

print(student.keys())   # dict_keys(['이름', '나이', '취미'])
print(student.values()) # dict_values(['김철수', 12, ['독서', '노래부르기']])

print(list(student.keys()))   # ['이름', '나이', '취미']
print(list(student.values())) # ['김철수', 12, ['독서', '노래부르기']]

items()

리스트 안에 key-value 를 튜플 형태로 받아온다.

student = {'이름': '김철수', '나이':12, '취미':['독서', '노래부르기']}

print(student.items())   # dict_items([('이름', '김철수'), ('나이', 12), ('취미', ['독서', '노래부르기'])])
print(list(student.items())) # [('이름', '김철수'), ('나이', 12), ('취미', ['독서', '노래부르기'])]

# 딕셔너리는 인덱스로 조회 불가함. keys() 이용하여 value에 접근 가능하다.

student = {'이름': '김철수', '나이':12, '취미':['독서', '노래부르기']}

for info in student.keys():
    print(student[info])
    
# 김철수
# 12
# ['독서', '노래부르기']

6. 딕셔너리 삭제하기

del

student = {'이름': '김철수', '나이':12, '취미':['독서', '노래부르기']}

del student['이름']
del student['나이']

print(student) # {'취미': ['독서', '노래부르기']}

pop ( ) 삭제한 데이터를 반환해준다.

student = {'이름': '김철수', '나이':12, '취미':['독서', '노래부르기']}

name = student.pop('이름')
age = student.pop('나이')

print(student) # {'취미': ['독서', '노래부르기']}
print(name) # 김철수
print(age) # 12

7.  딕셔너리 in, not in 키워드를 사용하여 키 존재 유무 확인하기

student = {'이름': '김철수', '나이':12, '취미':['독서', '노래부르기']}

print('이름' in student) # True
print('성별' in student) # False

8. 딕셔너리 len( )을 사용하여 아이템의 개수를 확인하기

student = {'이름': '김철수', '나이':12, '취미':['독서', '노래부르기']}

print(len(student)) # 3

9. 딕셔너리 clear( )를 사용하여 딕셔너리 내 모든 데이터를 삭제한다.

student = {'이름': '김철수', '나이':12, '취미':['독서', '노래부르기']}
student.clear()

print(student) #  {} 빈 딕셔너리

백트래킹 

백트래킹(Backtracking)이란,

제약조건을 만족하는 해를 찾기 위한 전략으로, 문제를 푸는 일종의 전략, 기법이라고 볼 수 있다 (알고리즘은 아님)

후보군을 점진적으로 체크하다가 제약조건을 만족하지 못한다고 판단되면 즉시 backtrack (다시는 이 후보군을 체크하지 않을 것이라고 표기) 한다. 다음 후보군을 체크해 나가며 결국 최적의 해를 찾는 방법이다.

Promising: 해당루트가 조건에 맞는지 검사하는 기법

Pruning(가지치기): 조건에 맞지 않으면 포기하고 다른 루트로 바로 돌아서서, 탐색 시간을 절약하는 기법

즉, 백트래킹은 트리구조를 기반으로 DFS로 깊이 탐색을 진행하면서 각 루트에 대해 조건에 부합하는지 체크(Promising), 만약 해당 트리(나무)에서 조건에 맞지 않는 노드는 더 이상 DFS로 깊이탐색을 진행하지 않고 가지를 쳐버림(Pruning)

백트래킹 구현 방법

1. 고려할 수 있는 모든 경우의 수 (후보군)를 상태공간트리(State Space Tree)를 통해 표현한다.

여기서 상태공간트리란 문제해결과정의 중간상태를 노드로 나타낸 트리.

2. DFS 방식으로 각 후보군을 확인

3. 트리를 탐색하면서 제약이 맞지 않으면, 해의 후보가 될 만한 곳으로 바로 넘어가서 탐색한다.

N Queen 문제

N Queen

대표적인 백트래킹 문제로, N x N 크기의 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치하는 문제.

퀸은 상하좌우, 대각선으로 이동할 수 있으므로, 배치된 퀸 간에 공격할 수 없는 위치로 배치해야 한다.

Promising: 해당루트가 조건(퀸과 수직, 수평, 대각선에 위치하지 않음)에 맞는지 검사하는 기법

Pruning(가지치기): 조건에 맞지 않으면 포기하고 다른 루트로 바로 돌아서서, 탐색 시간을 절약하는 기법

파이썬으로 백트래킹 N Queen 구현하기

1. Promising: 수직 체크와 대각선 체크 

수직 체크: candidate[queen_row] == current_col

대각선 체크: abs(candidate[queen_row] - current_col) == current_row - queen_row

def is_available(candidate, current_col):
    current_row = len(candidate)
    for queen_row in range(current_row):    
        if candidate[queen_row] == current_col or abs(candidate[queen_row] - current_col) == current_row - queen_row:
            return False
    return True

2. Pruning(가지치기)

1) if문 이용해 탈출조건 구현

2) pop() 이용해 backtracking 한다. ( 최적위치 찾았으면 return됨. DFS를 빠져나왔다는 것은 실패했다는 뜻 )

def DFS(N, current_row, current_candidate, final_result):
    if current_row == N:
        final_result.append(current_candidate[:])
        return
    
    for candidate_col in range(N):
        if is_available(current_candidate, candidate_col):
            current_candidate.append(candidate_col)
            DFS(N, current_row + 1, current_candidate, final_result)
            current_candidate.pop() # backtraking

n은 row의 전체 줄 수

current_row 현재 검사하고자 하는 row

current_candidate 지금까지 배치된 퀸의 위치가 저장되어 있음

final_result 퀸의 배치조건을 모두 만족하는 n개의 퀸 위치가 저장되어 있음

def solve_n_queens(N):
    final_result = []
    DFS(N, 0, [], final_result)
    return final_result


solve_n_queens(4) # [[1, 3, 0, 2], [2, 0, 3, 1]]

최단경로 알고리즘

최단경로 문제란,

두 노드를 잇는 가장 짧은 경로를 찾는 문제. 

가중치 그래프에서 간선(Edge)의 가중치 합이 최소가 되도록 하는 경로를 찾는것이 목적이다.

최단경로 문제의 종류

1. 단일 출발 - 단일 도착 최단경로: A 노드에서 출발 K노드에 도착하는 가장 짧은 경로 찾기

2. 단일 출발 최단경로(다익스트라): A 노드 출발. A외 모든 노드(B,C,D...) 도착하는 가장 짧은 경로 찾기

3. 전체 쌍 최단경로: 그래프 내 모든 노드 쌍(u,v)에 대한 최단 경로를 찾는 문제

다익스트라 알고리즘

다익스트라 알고리즘로직은

첫 정점을 정하여, 그 정점을 기준으로 연결된 정점들을 추가해가며 최단거리를 갱신하는 기법.

BFS 너비우선탐색과 유사한 방식을 따른다. depth의 노드를 모두 확인하고, 그 다음 depth로 넘어가는 측면에서 유사.

우선순위 큐를 사용하는 방식이 가장 개선된 방법

파이썬으로 구현하는 다익스트라 알고리즘

1. 우선순위 큐 사용하기

데이터가 리스트인 경우, 0번 인덱스를 우선순위로 인지하는 자료구조 (주의, 앞에 숫자가 아니면 동작을 안함)

우선순위가 낮은 순서대로 pop() 한다.

import heapq
queue = []
heapq.heappush(queue, [2,'A'])
heapq.heappush(queue, [5,'B'])
heapq.heappush(queue, [1,'C'])
heapq.heappush(queue, [7,'D'])
heapq.heappush(queue, [4,'E'])

print(queue)
print()
for index in range(len(queue)):
    print(heapq.heappop(queue))



# 출력    
[1, 'C']
[2, 'A']
[4, 'E']
[5, 'B']
[7, 'D']

2. 다익스트라 함수 구현하기

1단계: 초기화

- 거리배열을 생성하고, 첫 노드는 거리가 0이고 나머지는 무한대(inf)로 설정한다.

- 우선순위 큐(최소힙) 에 첫 노드를 넣는다. (시작은 A)

2단계: 우선순위큐(0, A)

우선순위 큐에 있는 노드 (0, A)를 pop 하여 (첫노드 - 인접노드) 간의 거리를 계산하여 거리배열 업데이트 (B,C,D 반복)

- 그래프 내 A와 인접한 노드 B,C,D를 방문하며

- 거리배열에 들어있던 값(inf) 보다 가중치가 더 짧으면 거리배열 업데이트 B:8 ,C:1, D:2

- 우선순위큐에 (8:B, 1:C, 2:D) push. 

3단계: 우선순위큐 (8:B, 1:C, 2:D) 중에서 가장 작은 1:C

2단계에서 최소노드를 pop하여 (두번째노드C - 세번째 노드B,D) 간의 거리를 계산하여 거리배열 업데이트 

- 그래프 내 C와 인접한 노드 B,D를 방문하며

- 거리배열 B에 들어있던 값(8) 보다 거리가 더 짧으면( 6 = 1+5 ) 거리배열 업데이트 후 우선순위큐에 (6:B) push.

- 거리배열 D에 들어있던 값(2) 보다 거리가 더 길면 거리배열 업데이트 안 함. 우선순위큐에 push도 안 함.

4단계:  우선순위큐 (2:D, 8:B, 6:B) 중에서 가장 작은 2:D

- 그래프 내 D와 인접한 노드 E,F를 방문하며

- 거리배열 E에 들어있던 값(inf) 보다 거리가 더 짧으면( 5 = 2+3 ) 거리배열 업데이트 후 우선순위큐에 (5:E) push.

- 거리배열 F에 들어있던 값(inf) 보다 거리가 더 짧으면( 7 = 2+5 ) 거리배열 업데이트 후 우선순위큐에 (7:F) push.

5단계:  우선순위큐 (5:E, 8:B, 6:B, 7:F) 중에서 가장 작은 5:E

- 그래프 내 E와 인접한 노드 F를 방문하며

- 거리배열 F에 들어있던 값(7) 보다 거리가 더 짧으면( 6 = 5+1 ) 거리배열 업데이트 후 우선순위큐에 (6:F) push.

import heapq

def dijkstra(graph, start_node):
    
    # 초기화
    distances = {node:float('inf') for node in graph} # 거리(가중치의 합) dictionary 생성
    distances[start_node] = 0 # start에서 start는 거리가 0
    
    # 우선순위 큐: 방문해야하는 노드가 담겨있다.
    queue = [] 
    heapq.heappush(queue,[distances[start_node], start_node]) # [distance, node] -> [8, 'A'] 형태로 초기 데이터 넣는다.
    
    # 우선순위 큐에 있는 노드들을 방문
    while queue:
        # 큐에 들어있는 값 중에서 우선순위(가중치) 가장 작은 값부터 pop
        current_distance, current_node = heapq.heappop(queue) 
        
        # 시간계산량 줄일 수 있는 코드(현 가중치가 기존 거리를 넘어섰을 땐 굳이 계산 안해도 됨)
        if distances[current_node] < current_distance:
            continue
        
        for adjacent_node, weight in graph[current_node].items():
            distance = current_distance + weight
            if distance < distances[adjacent_node]:
                distances[adjacent_node] = distance
                heapq.heappush(queue, [distance, adjacent_node])

    return distances   
    
dijkstra(mygraph, 'A') # {'A': 0, 'B': 6, 'C': 1, 'D': 2, 'E': 5, 'F': 6}

다익스트라 알고리즘의 시간복잡도 계산하기

다익스트라는 2개의 과정을 거친다.

과정1. 각 노드마다 인접한 간선들을 모두 검사하는 과정

과정2. 우선순위 큐에 노드+거리 정보를 넣고 삭제(pop)하는 과정

과정별로 시간복잡도를 측정해보면

과정1. 간선의 개수E 일때, O(E) 

과정2. 하나의 간선에서 배열의 최단거리가 갱신되고, 우선순위큐에 추가되어야 하는 최악의 경우 O(log E) 이다. 따라서 모든 간선에서 최악의 경우가 발생할 때, O(E log E)

다익스트라의 시간복잡도는 O(E log E)이다.

탐욕알고리즘(Greedy Algorithm)이란

최적의 해에 가까운 값을 구하기 위해 사용되는 알고리즘으로,

여러 경우 중에서 하나를 선택해야할 때마다 매 순간 최적이라고 생각되는 경우를 선택하는 방식이다.

탐욕알고리즘의 대표적인 문제

1) 동전

지불해야 하는 값이 4720원 일 때 1원 50원 100원, 500원 동전으로 동전의 수가 가장 적게 지불하시오

• 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식으로 구현 가능
• 탐욕 알고리즘으로 매순간 최적이라고 생각되는 경우를 선택하면 됨: 가장 큰 동전으로 최대한 많이 지불하는 것.

coin = [1, 50, 100, 500]
coin.sort(reverse=True)
pay = 4720
coin_count = 0

for c in coin:
    while pay >= c:
        coin_count += pay//c
        pay = pay % c
print(count)

탐욕알고리즘의 대표적인 문제

2) 부분 배낭

무게 제한이 k인 배낭에 최대 가치를 가지도록 물건을 넣는 문제. 가치가 가장 높은 물건을 우선적으로 담는 것.

• 각 물건은 무게(w)와 가치(v)로 표현될 수 있음
• 물건은 쪼갤 수 있으므로 물건의 일부분이 배낭에 넣어질 수 있음, 그래서 Fractional Knapsack Problem 으로 부름

data_list = [(10, 10), (15, 12), (20, 10), (25, 8), (30, 5)]
data_list = sorted(data_list, key=lambda x:x[1]/x[0], reverse=True)

k = int(input())
result = 0

for w, v in data_list:
    if k >= w:
        k -= w
        result += v
    else:
        result += (v/w)*k 
        break
        
print(result)

그래프

그래프란,

실제 세계의 현상이나 사물을 정점(Vertex) 또는 노드(Node)와 간선(Edge)로 표현하기 위해 사용한다.

ex)

집에서 회사에 가는 경로를 그래프로 표현하면,

________________>지하철________________

|                                                                          |

집                                                                        회사

|_________________>버스________________|

그래프 종류

1. 무방향 그래프

방향이 없는 그래프

간선을 통해 양방향의 노드로 접근 가능하다.

A와 B가 연결된 경우 (A, B) 로 표기

2. 방향 그래프

간선에 방향이 있는 그래프

A에서 B 방향으로 가는 경우 <A,B> 로 표기

3. 가중치 그래프

간선에 비용 또는 가중치가 할당된 그래프

그래프와 트리의 차이

트리는 그래프 중에 속한 특별한 종류라고 볼 수 있음

그래프 탐색 알고리즘

• 너비 우선 탐색 (Breadth First Search): 정점들과 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 탐색하는 방식
• 깊이 우선 탐색 (Depth First Search): 정점의 자식들을 먼저 탐색하는 방식

• BFS 방식: A - B - C - D - G - H - I - E - F - J
  • 한 단계씩 내려가면서, 해당 노드와 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 순회함
• DFS 방식: A - B - D - E - F - C - G - H - I - J
  • 한 노드의 자식을 타고 끝까지 순회한 후, 다시 돌아와서 다른 형제들의 자식을 타고 내려가며 순화함

파이썬으로 BFS 알고리즘 구현하기 (큐 2개 이용)

1. 딕셔너리+리스트 자료형을 이용하여 그래프 표현

graph = dict()

graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']

2. 큐 자료형을 이용하여 need_visit 큐, visited 큐 생성

• need_visit 큐: 방문해야 할 노드들이 순서대로 담겨 있다. 
• visited 큐: 방문했던 노드들이 들어있다.

def bfs(graph, start_node):
    visited = list()
    need_visit = list()
    need_visit.append(start_node)
    
    # 방문할 노드가 없을때까지 반복
    while need_visit:
        node = need_visit.pop(0) # pop(0): 큐 기능 (0번인덱스 pop, 이후 데이터로 채워짐)
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node]) # extend: 리스트끼리를 하나의 리스트로 합침
    return visited
    
bfs(graph,'A') # ['A', 'B', 'C', 'D', 'G', 'H', 'I', 'E', 'F', 'J']

파이썬으로 DFS 알고리즘 구현하기 (스택+큐 이용)

• need_visit 스택: 방문해야 할 노드들이 순서대로 담겨 있다. 
• visited 큐: 방문했던 노드들이 들어있다.

def dfs(graph, start_node):
    visited = list() # 큐
    need_visit = list() # 스택
    need_visit.append(start_node)
    
    while need_visit:
        node =  need_visit.pop() # pop(): 스택 기능 (최근 입력된 값부터 꺼내기)
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])
    return visited


dfs(graph, 'A') # ['A', 'C', 'I', 'J', 'H', 'G', 'B', 'D', 'F', 'E']