분류 전체보기 240

Unit 3. Binary Search Tree

이진 검색 트리, 만들다보니 코드가 길어져서... insert나 traverse는 다다닥 만드는데 delete 만들면서 좀 생각해야했던. 삭제 시 이진 트리에서는 3가지 경우를 고려해야합니다. 자식 노드가 없거나, 1개 있거나, 두 개 다 있거나 한 경우인데요. 저는 case 1을 구현하려고 prev 변수를 만들어서 객체 생성 시 자신의 parent node를 저장했고, 이후 prev 노드가 변경될 때 이를 수정해주며 case 1의 삭제를 구현했습니다. case 3에서 자식 노드가 두 개 다 있을 경우에는 타겟 노드의 자식들 중에서 successor나 predecessor를 추출한 다음 해당 노드를 제거하고, 이어서 타겟 노드의 값을 successor나 predecessor로 변경하면 정상적으로 삭제가 ..

Unit 3. heap sort

heapify와 shiftdown만 하면 max heap과 min heap을 쉽게 구현할 수 있습니다. heap의 property는 부모 노드가 자식 노드보다 커야한다는 것입니다. 부모 노드의 자식 노드를 인덱스로 나타내면 부모 노드가 p의 이름을 가질 때 c(child)는 c1 = p*2+1 or c2 = p*2+2 인덱스에 위치해 있습니다. 이 노드들의 대소비교를 해서 모든 부모 노드들을 shiftdown해주면 heapify된 리스트를 얻을 수 있습니다. 대소 비교에 따라서 최대값 또는 최소값을 root node에 얻을 수 있고 이후 마지막 노드와 루트 노드를 swap한 뒤 마지막 노드를 제외한 나머지를 heapify하는 과정을 루트 노드를 제외한 모든 노드에 적용하면 정렬된 리스트를 얻을 수 있습니..

Unit 2. powerset

powerset이란? 특정 집합의 공집합을 포함한 모든 부분 집합을 멱집합(powerset)이라 한다. 123456789101112131415161718def powerset(level): length = len(List) if level == length: element = [] for i in range(0, length): if include[i]: element.append(List[i]) print element return else: include[level] = False powerset(level+1) include[level] = True powerset(level+1) List = ['a','b','c']include = [False for _ in xrange(len(List))]po..

Unit 3. 들어가기 앞서

알고리즘 해보고싶어서 Coursera에 Introduction of Algo에서 과제가 pass 안되서 전전긍긍한지 언 6개월... inflearn 덕택에 원하던 것을 찾을 수 있게되어 감사 ! 주로 강의를 듣고 그 내용을 python으로 구현해보면서 넘어가고 있습니다. 정렬 섹션에 들어가기 앞서 bubble, insertion, select, quick sort를 정리하고 가겠습니다. 10분이면 되니, 이번에 정리하고 이후엔 스킵! 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859import random def bubbleSort(list): length =..

Unit 2. 상태 공간 트리

상태 공간 트리(state space tree) 1. 해를 찾기 위해 탐색할 필요가 있는 모든 후보들을 포함하는 트리2. 트리의 모든 노드들을 방문하면 해를 찾을 수 있다.3. 루트에서 출발하여 체계적으로 모든 노드를 방문하는 절차를 기술한다. 평소 했던데로 생각하면 해결책이 떠오르지 않는데, 이런 도구들을 사용하니 좀 더 편하게 이해할 수 있었습니다.(recursion is fantastic method !) ref : algorithm

Unit 2. n-queens

대각, 직각에 겹치는 노드가 없게 만드는 예제입니다. 컨셉을 이해는 했으나 만드는 과정이 2시간이나 걸렸다는... Tkinter로 깔끔하게 이미지로 표현할 수도 있지만, 귀찮으므로 패스... 1234567891011121314151617181920212223242526272829303132def non_promising(level): if level == 0: return True else: for col in range(0, level): if level - col == abs(cols[level] - cols[col]): return False if cols[level] == cols[col]: return False return True def queens(level): if level == len..

Unit 2. find maze path and count cells blob

강의를 듣고 간단히 만들어봤습니다. 미로찾기를 구현할 수 있다면 countCellsblob은 자연스레 구현할 수 있습니다. 제 생각대로 만들어서 강의의 코드와 다를 수 있습니다.(강의에선 java를 사용합니다.) MIT OpenCourseWare에서 강의들을 때 미로찾기 나왔었는데 반갑네요 ^^ 쉽고 재밌게 코딩할 수 있는듯 ~ 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950# PATHWAY_COLOUR = 0# WALL_COLOUR = 1# BLOCKED_COLOUR = 2# PATH_COLOUR = 3def findPath(x, y): if x is 8 and y is 9: # out ..

Unit 1, 2 내용 및 단어 정리

exascale(exa + scale) : 10^18 assumption : 1. 추정, 상정 coherency : 일관성 primitive : 초기의, 원시적 단계의 carry out : 수행하다 residue : 1. 잔여물, 2. 잔여 유산 mnemonic : 연상 기호 procedural langauge - "sequence of specific instruction" 1. Syntax vs Semantic Syntax : "what are legal expression" ex) "cat", "dog" - o / "doggg" - x Semantic : "what programs are meaningful", "what does the program", using try-catch in seman..

Unit 1. discrete structure 들어가며, 단어 정리

The principal topics presented in this course are logic and proof, induction and recursion, discrete probability, and finite state machines Unit 1에 들어가기 앞서 코스 소개를 읽어보니 주요 주제 중 하나에 finite state machine이 있다. 어디서 들어본 것 같은 멋진 단어인데, wiki를 찬찬히 읽어보다가 Automata가 나왔다. 뭐 정규 표현식, Artificial Intelligent, Artificial Life, Generic Algorithm 같이 맛만 봤던 것들도 눈에 띄었지만, 결론은 뭔지 잘 모르겠다. 컴파일러, 알고리즘, 인공지능에 사용되는 자동 기계 정도....