티스토리

보안 이모저모

검색하기

블로그 홈

보안 이모저모

jackpodsecurity.tistory.com/m

Jackpod1001001 님의 블로그입니다.

구독자: 0

방명록 방문하기

주요 글 목록

합병 정렬(Merge sort) 합병 정렬(Merge sort)이란?합병정렬(merge sort)은 정렬 알고리즘의 한 종류로, 폰 노이만이 개발한 알고리즘이다.이 정렬은 안정 정렬에 속하며, 분할 정복(divide and conquer) 알고리즘의 하나이다. 합병 정렬(Merge sort) 아이디어합병(Merge)라는 이름에서 알 수 있듯, 합병 정렬의 기본 아이디어는 정렬할 배열을 분할하여, 작은 조각으로 나눈 후 더 이상 나눌 수 없을 때(하나의 원소만 있을때) 다른 조각과 비교하며 합쳐 정렬하는 알고리즘이다.과정 정렬되지 않은 리스트를 2개의 리스트로 나눈다.각 리스트의 길이가 1이 될때까지 반복한다(길이가 1인 리스트는 정렬된 것으로 간주한다.)2개의 리스트의 값들을 처음부터 하나씩 비교하여 두 개의 리스트의 값 중에서 더 작.. 공감수 0 댓글수 0 2024. 10. 12.
프림 알고리즘(Prim Algorithm) 구현과 증명 프림 알고리즘(Prim Algorithm)이란?어떠한 그래프에서 최소신장트리(Minimum Spanning Tree)를 찾는 알고리즘이다.그리디(Greedy) 알고리즘 중 하나이다. 프림 알고리즘(Prim Algorithm)의 아이디어트리중 하나의 노드에서 시작(아무 노드나 상관없음)우리가 만들어가고 있는 트리에 인접한 edge들 중 가장 작은 weight를 가진 edge를 추가(단, 사이클을 만들지 않아야함)spanning tree가 될때까지 반복 프림 알고리즘(Prim Algorithm)의 증명정확성G : 주어진 그래프(방향성X, 가중치O)V : 전체 node의 집합E : 전체 edge의 집합Y : 방문한 nodeF : 방문한 edge G = (V,E)로 나타낼 수 있고, F ⊆ E, Y ⊆ V이다.. 공감수 0 댓글수 0 2024. 9. 17.
그리디 알고리즘(Greedy Algorithm, 탐욕법) 1. 그리디 알고리즘이란?최적의 값을 구해야 하는 상황에서 전체적인 상황을 상정하여 구하는 것이 아닌, 각 단계에서 최선의 선택을 하는 근시안적 방법론입니다.전체적인 상황을 상정하지 않기 때문에 항상 최적의 해를 구하는 것이 보장되어있지 않지만, 근사해를 구하는것이 가능합니다.아래와 같은 트리에서 각 노드의 합의 최대값을 구하는 상황일때, 탐욕법을 이용하면 각 단계에서 가장 큰 값을 선택하게 되어 5->10->4와 같이 선택하게 됩니다.최적의 해는 5->7->9이므로 탐욕법을 이용하는것이 항상 최적의 해를 구하는 것은 아님을 보여줍니다.2. 그리디 알고리즘의 특징2.1 그리디 알고리즘의 조건그리디 알고리즘이 근사값이 아닌 최적값을 보장하는 조건 2가지가 있습니다. 탐욕 선택 속성 (Greedy Choic.. 공감수 0 댓글수 0 2024. 7. 13.

문의안내

티스토리
로그인
고객센터

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