Python/알고리즘공부
04_ 피보나치 수열 및 여러 문제들(hard)
input = 20 def fibo_recursion(n): # 구현해보세요! if n==1 or n==2: return 1 return fibo_recursion(n-1) + fibo_recursion(n-2) print(fibo_recursion(input)) # 6765 피보나치 수열은 재귀함수로 간단하게 구현할수 있다... 하지만 굳이 n-1, n-2 이렇게 저장하면서 하면 될꺼같은데 이렇게 계산량을 늘릴 필요가 있나? 싶던 찰나에 input = 100 # memo 라는 변수에 Fibo(1)과 Fibo(2) 값을 저장해놨습니다! memo = { 1: 1, 2: 1 } def fibo_dynamic_programming(n, fibo_memo): if n in fibo_memo: return fib..
03_ DFS , BFS
얘네는 딱 하나만 기억하면 될거 같다. DFS는 깊게 트리를 분석하는거, BFS는 한단계씩 전반적으로 파고들어가는것! DFS부터 봐보자. graph = { 1: [2, 5, 9], 2: [1, 3], 3: [2, 4], 4: [3], 5: [1, 6, 8], 6: [5, 7], 7: [6], 8: [5], 9: [1, 10], 10: [9] } visited = [] def dfs_recursion(adjacent_graph, cur_node, visited_array): # 구현해보세요! visited_array.append(cur_node) for adjacent_node in adjacent_graph: print(adjacent_node) if adjacent_node not in visited_..
02_heap
heap은 비선형 자료구조이다. 가장 큰 값이나 가장 작은값이 항상 첫번째로 들어가게 한다. sorted와는 다르게 이진트리 방식으로 구성되어 있는것이 특징. class MaxHeap: def __init__(self): self.items = [None] def insert(self, value): # 구현해보세요! self.items.append(value) cur_index = len(self.items) -1 while cur_index > 1: parent_index = cur_index // 2 if self.items[cur_index] > self.items[parent_index]: self.items[cur_index] , self.items[parent_index] = self.ite..
01_1week
첫주에 배운건 자료구조적인 느낌보단 전반적인 알고리즘에 익숙해지는 느낌이었다. 나중에 깃에 모아서 올릴 생각이다. 사실 첫주에 배운게 2주전이다.. 블로그를 시작하기 전이니까 정리해보면서 복습하려고 파일들을 열었는데 주석처리가 안되어 있으니까 어떤 문제였는지 다시 생각해봐야 한다.. 이래서 주석이랑 깔끔하게 정리해 두는 습관이 중요한것 같다. 앞으로는 체계적이고 주석남겨가면서 꼼꼼히 정리해야겠다. 서론이 길었고 시작해야겠다. 아마 코드들이랑 간단한 리뷰들만 쓸 것 같다. 1. 가장 많은 알파벳을 출력 input = "hello my name is sparta" def find_max_occurred_alphabet(string): # 이 부분을 채워보세요! alphabet_array = [0] * 26 ..
00_공부시작 배경
한이음 공모전을 통해서 유료 강좌를 무료로 들을 수 있는 기회가 생겨서 평소에 백준 프로그래밍을 푸는 김에 한번 체계적인 수업도 받아보고 싶어서 신청했었다. 사실 코딩에 재일 흥미있었던게 이런 문제해결 과정이었던 것 같은데 여러 자료구조들을 배우고 풀면 더 잘 풀 수있을거 같아 기분이 좋다. 컴퓨터 구조론 시간에 배운 스택,큐등을 이용해서 푸는것 같다. 아마 마이크로프로세서 들을때도 좀 도움이 되지 않을까?