soicem's note

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273# dynamic programming 행렬 경로 문제 # target = [[10,30,25,8],# [19,50,11,3],# [32,51,3,5],# [6, 100,5,1]]# cache = [[-1,-1, -1, -1],# [-1, -1, -1, -1],# [-1, -1, -1, -1],# [-1, -1, -1, -1]]## direction = [[-1,-1, -1, -1],# [-1, -1, -1, -1],# [-1, -1, -1, -1],# [-1, ..

ref : 영리한 프로그래밍을 위한 알고리즘 강좌 in inflearn 허프만 코딩 개념 1. run(끊을 데이터 단위)를 파일에서 수집한다. ex) '111110110'에서 '11111'까지가 하나의 run이 될 수 있다. 빈도가 높고 길이가 길면 낮은 코드워드로 변환해서 압축 파일 크기를 줄일 수 있을 것이다.2. huffman tree를 만든다.3. code word를 할당한다.4. 할당한 코드 워드를 적당한 자료구조에 저장한다. (저장할 때 길이, 빈도를 함께 저장한다.)5. 인코딩하여 압축 파일을 만든다.(이때 압축 정보는 헤더로 추가한다.)6. 디코딩할 때 헤더 정보를 참조한다. # 재밌다 ㅋ

전역 변수를 쓰기 싫어서 python 3로 리스트에 담아서 카운트했는데 시간 초과, 전역 변수 써도 시간 초과되서 c로 작성. 123456789101112131415161718192021222324252627282930313233343536#include int val0 = 0;int val1 = 0; int fibonacci(int n){ if (n == 0){ val0 += 1; return 0; } else if (n == 1){ val1 += 1; return 1; } else { return fibonacci(n-1) + fibonacci(n-2); }} int main(){ int TestCase = 0; scanf("%d", &TestCase); int Ns[TestCase]; for(int..

경로 찾기, 그냥 재미로 ~ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051import random def matrixShortestPath(row, col): # sets = [(row+1, col), (row, col+1), (row-1, col), (row, col-1)] sets = [(row + 1, col), (row, col + 1)] visitedList[row] = visitedList[row] | (2 ** col) print(lists[row][col]) # if row == 0 and col == 0: # sets = sets[0:2] # elif row == 0:..

depth first search와 breadth first search에 대해 정리하겠습니다. 이는 "성공적인 코딩 인터뷰를 위한 코딩 인터뷰"(허민석님)의 강의와 예제 코드를 보고 연습했습니다. 12345678910111213141516171819202122232425262728293031323334353637383940414243vertexList = ['A', 'B', 'C', 'D', 'E', 'F', 'G']edgeList = [(0,1), (1,2), (1,3), (3,4), (4,5), (1,6)] # vertexList = ['0', '1', '2', '3', '4', '5', '6']# edgeList = [(0,1), (0,2), (1,0) , (1,3) , (2,0) , (2,4) ..

hashing에 대해 정리합니다. 이미 밝혔다시피 해당 포스팅은 inflearn의 "영리한 프로그래밍을 위한 알고리즘 강좌"를 기반으로 합니다. hash table은 dynamic set을 구현하는 효과적인 방법 중 하나입니다. dynamic set이라 함은 다양한 데이터들이 유동적으로 in/out하기에 적합한 자료구조입니다. 데이터를 소스로 하여 특정 함수로 해당 데이터가 저장될 위치를 구하며, 이를 통하여 효율적인 데이터 관리가 가능해집니다. 주의할 점은, 데이터와 특정 함수에 따라서 저장될 위치가 겹치는 경우가 발생합다. 이러한 collision problem에, 두 개 이상의 키가 동일한 위치에 해슁되는 경우, 해결 방안으로 두 가지를 본 강의에서 제시하고 있습니다. 해쉬함수값이 불규칙적이 되도록..

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

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하는 과정을 루트 노드를 제외한 모든 노드에 적용하면 정렬된 리스트를 얻을 수 있습니..

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..

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