티스토리

활주로

검색하기

블로그 홈

활주로

stop0729.tistory.com/m

stop0729 님의 블로그입니다.

구독자: 1

방명록 방문하기

주요 글 목록

최소신장트리 알고리즘 최소신장트리, 프림, 크루스칼 미니멈 스패닝 트리 문제 : 엣지에 웨이트가 있는 노드들이 있다고 할때, 모든 노드들이 연결되어 있으면서 엣지 웨이트의 합이 최소가 되도록 스패닝 트리 : 모든 노드가 연결되있는 트리 스패닝 트리 weigth : 엣지들의 weight가 부여되어 있다면 우리가 선택한 엣지의 weight 합 프림 알고리즘 : 그리디 알고리즘 노드가 한개라면, 연결된 엣지중에서 가장 적은 weight를 가진 노드 연결. 보편적으로는 직접적으로 edge 하나로 연결된 vertex 가운데 weight가 가장 작은것을 추가하는 알고리즘. 현재 트리와 가장 가까운 vertex를 하나씩 추가해나가는 방법 어떠한 vertex에서 시작해도 차이가 없다. N개의 vertexr가 있다면 N-1 의 엣지를 고를때.. 공감수 0 댓글수 0 2021. 8. 31.
힙 자료구조 binary heap 1. min heap 2. max heap min heap : binary tree의 루트 노드가 이 트리 내의 다른 모든 값들보다 작아야 한다. sibling 끼리는 어떤 정해진 관계성이 존재 하지 않는다. 서브트리의 루트값이 최소값이면 된다는 조건말고 다른 조건은 필요하지 않다. max heap : min heap 과 반대 heap에서의 operation 3가지 1. Top : 가장 작은값 (맥스 힙 값은 경우에는 가장 큰값) 을 찾아오는 동작. 루트 노드만 찾으면 되기에 constant time 2. pop : 루트에 있는 값을 제거하는것. 만약 3을 pop 하면, 7이나 12중 작은값을 promotion을 해야한다. 7을 promotion 하면 9와 31중 작은값을 promo.. 공감수 0 댓글수 0 2021. 8. 24.
점근적 분석 Asymptotic Analysis : 점근적 분석법 - 같은 문제를 푸는 2개의 알고리즘이 있을 때, 어떤 알고리즘이 더 좋은지 과학적이고 수치적으로 표현할 수 있기 위해서 만든것. 알고리즘을 수학적으로 분석해서 뭐가 더 좋은지 결론을 내린다. - variable : 알고리즘을 분석하는데, 런타임 메모리 요구량등을 표현하는것. (e.g variable n 한개라면, n개의 원소로 이루어진 array를 sorting 하는데 드는 복잡도) - linear search : 앞에서부터 순차적으로 하나씩 테스트 - binary search : array가 소팅되어 있을 때, 순서가 non-decreasing order로 정렬이 되어 있을때만 적용할수 있는 방법. 중간값과 우리가 찾고자하는 값을 비교해서 중간값보.. 공감수 0 댓글수 0 2021. 8. 1.
그래프 탐색 알고리즘 그래프 traversal : 그래프의 노드들을 방문하는 과정. search라고도 쓰임. breadth-fist search : 너비 우선 depth-first search : 깊이 우선 스택. 큐와 연계하여 어떻게 실행할까? bfs : 밑에는 queue array이고 위에는 우리가 정렬하려는 트리. A를 시작 vertex로 큐에 넣는다. 그다음 A를 큐에서 팝 하면서 visit됨을 표현한다. 그다음 큐에 A와 인접한 B, C, E 를 넣는다. B, C, E 는 같은 breath 상이므로 뭘 넣던 상관이 없는것 같다. B를 먼저 팝하고 그와 인접하며 큐에 있지 않는 D를 푸쉬 한다. 그다음은 C를 팝하고 인접한 F를 푸쉬한다. 그다음 E를 팝하고 인접한 H와 G를 푸쉬한다. 다음은 D를 팝. F를 팝. H.. 공감수 0 댓글수 0 2021. 7. 25.
비선형 자료구조 tree : 노드들의 집합체, 계층적인 관계, 어떤 정보는 노드에 포함된다. 뿌리 노드가 존재한다. 루트를 제외한 각각의 노드는 정확하게 하나의 노드를 부모노드로 가진다. degree : 노드가 가지고 있는 자녀의 숫자 ex) E의 degree는 2 sibling : 같은 부모를 가지는 노드들 ex) j k l 은 I라는 같은 부모노드를 가진다. leaf : 자녀가 없는 degree 0인 노드들 internal : 자녀가 있는 노드 unordered : 자녀의 순서가 무시되는 ordered : 자녀의 순서를 지켜야하는 트리의 경로를 정한다고 하면 부모와 자식 노드간 관계에서 부모 노드가 무조건 앞으로 와야하며 경로의 길이는 선의 갯수이다. 노드의 갯수가 아니다. 어떤 한 노드와 루트사이의 경로는 유니크하.. 공감수 0 댓글수 0 2021. 7. 22.
선형 자료 구조 배열과 리스트 동적할당 .. 링크 참고 void *malloc(size_t size ); void free(void *memblock ); https://dojang.io/mod/page/view.php?id=285 https://m.blog.naver.com/cache798/130033385486 call by value : 함수의 인자로 들어가는 변수의 값을 복사하여 넘겨주기때문에 해당변수의 값이 수정되지 않는다. call by reference : 변수의 주소를 넘겨주기때문에 변수의 값이 수정될 수 있다. linked list 각각의 node(vertex)는 데이터의 값 자체와 다음 next 노드의 포인터를 가지게 된다. 만약 사용 언어가 c라면 구조체, 객체지향 언어라면 겍체에 데이터 필드와 링크.. 공감수 0 댓글수 0 2021. 7. 16.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.