룰루랄라 알고리즘

단일 연결 리스트 각 노드들은 메모리의 인접한 곳에 위치하지 않는다 각 노드의 주소는 프로그램 실행 시 매번 틀릴 수 있다 리스트의 이름 = 첫 번째 노드의 주소 노드 생성 C언어에서 연결 리스트의 노드는 자기 참조 구조체를 이용하여 구현한다. struct node { int data; struct node* link; }; int main(void){ struct node *ptr = NULL; ptr = (struct node *)malloc(sizeof(struct node)); ptr->data = 10; //(*ptr).data=10; ptr->link = NULL; } 두 개의 노드 연결 구조체의 link에 다음 노드를 가리키는 포인터를 저장한다 int main(void) { struct no..

문제풀이 고민 하루, 구현 하루 총 2일에 걸쳐 푼 자료구조 교수님의 미친알고리즘 문제 구글에 찾아보기 자존심 상해서 구글링 거들떠도 안보고 풀었다. 얼마전에 주문한 짭플펜슬이 톡톡히 도움 되었음. C++ 과목 A+ 자존심 지킨듯. 풀이는 종강하고 올려야징

아래와 같이 정방행렬의 대각선 위 또는 아래 모든 원소들의 값이 0인 행렬을 각각 하삼각 행렬, 상삼각 행렬이라고 한다. A[n][n]에 저장된 삼각 행렬을 메모리를 절약하기 위해서 0이 아닌 데이터만을 일차원 배열 B[n(n+1)/2]에 저장하고자 한다. A[0][0]은 B[0][0]에 저장하고, 0이 아닌 A의 데이터들을 행 우선 순서로 B에 저장할 때, A[i][j]는 B의 어느 위치에 저장되는가? 단 각각 하삼각 행렬의 i,j 는 i >=j 이고, 상삼각 행렬의 i,j 는 i

희소 행렬을 3원소 쌍을 사용하는 1차원 배열로 구성하였을 때 두 희소 행렬의 곱을 구해보자. 두 희소행렬 a와 b를 3원소 쌍을 사용하는 1차원 배열로 구성 행렬 곱셈의 원리상 a행렬의 한 행과 b행렬의 한열을 곱하는데 희소 행렬 표시에서 같은 row(열)로 계산하면 편하므로 b행렬을 전치하여 col을 row로 변경 후 계산한다. 계산을 시작해보자 먼저 a행렬의 row가 0일 때, b행렬의 row가 0일 때 부터 시작하자 col = 0 -> a[0][0]: 15 * b[0][0]: 1 = 15 col = 3 -> a[0][3]: 22 * b 존재하지 않음 col = 5 -> a[0][5]: -15 * b 존재하지 않음 a행렬의 ..

b 행렬과 같이 value에 0이 많이 포함되는 행렬을 희소 행렬이라고 한다. 1000*1000 행렬에서 그 값의 대부분이 0일 때, 0을 저장하기 위해 1000*1000의 메모리를 사용하려 한다면 매우 큰 메모리 낭비이므로 구조의 구조체를 사용하여 값이 0인 좌표는 과감하게 버리고 유용한 값만 메모리에 저장한다. 이렇게 저장한 희소 행렬은 전치를 어떻게 할까? 보통 행렬은 전치를 하려면 row와 col값만 바꿔주면 된다. 하지만 위처럼 구조체를 활용하여 0의 값을 버린 행렬은 전치하기가 쉽지 않다. row와 col만 바꿔준다면 그 순서가 정렬 되어 있지 않을 것이고, row와 col을 바꾼 뒤 정렬까지 하려면 그 시간 복잡도가 O(N^3)이므로 매우 비효율 적이다. 따라서 다음과 같은 알고리즘을 적용해..

트리의 순회 전위 순회(pre-order traverse): 루트를 먼저 방문 중위 순회(in-order traverse): 왼쪽 자식을 방문한 뒤에 루트 방문 후위 순회(post-order traverse): 오른쪽 자식을 방문한 뒤에 루트 방문 A B C D E F G 실행결과 전위 순회: A - B - D - E - C - F - G 중위 순회: D - B - E - A - F - C - G 후위 순회: D - E - B - F - G - C - A

힙은 특정한 규칙을 가지는 트리로, 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한다. 힙 property : A가 B의 부모노드이면 A의 키값과 B의 키값 사이에는 대소 관계가 성립한다 최소 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙 최대 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙 이러한 속성으로 인해 힙에서는 가장 낮은(혹은 높은) 우선순위를 가지는 노드가 항상 루트에 오게 되고 이를 이용해 우선순위 큐와 같은 추상적 자료형을 구현할 수 있다. 이때 키값의 대소 관계는 부모/자식 간에만 성립하고, 형제노드 사이에는 대소 관계가 정해지지 않는다. heapq.heappush(heap, item) : item을 heap에 추가 heapq...