# 알고리즘 문제풀이&연습/[ Algorithm ]

안녕하세요 허언증입니다. Heap Sort 힙은 최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리입니다. 힙에는 최대 힙과 최소 힙이 존재 최대 힙은 '부모 노드'가 '자식 노드'보다 큰 경우 일 때. 일단 힙 정렬을 하기 위해서는 정해진 데이터를 힙 구조를 가지도록 만들어야 합니다. 6 => 부모 노드(root) 2,3 => 자식노드 부모노드의 값(6)이 자식노드(2,3) 보다 클 경우 그림 처럼 최 상단에 제일 큰 값이 있는 경우 2 => 부모 노드(root) 1,4 => 자식노드 현재의 경우에는 부모노드에 2가 있고 자식노드에 1,4가 있지만 4는 2보다 값이 더 크기 때문에 서로 교체를 해줘야 힙 형태가 된다. 이를 "힙 정렬"이라고 한다 이진트리가 힙정렬이 완료가 되..

안녕하세요. 허언증입니다. Union_Find에 대해 알아봅시다 여러 개의 노드가 존재할 때 두 개의 노드를 선택해서, 현재 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘입니다. 1. Find (부모 노드를 찾는다) 2. Union ( 두 개의 노드를 하나의 부모노드로 만들어준다) 1~9번 Node가 있습니다. 각 번호는 현재 각자의 번호를 부모노드로 인식하고 있습니다.( 자기자신이 부모노드로 인지) 만약 2번이 1번과 연결을 한다면 2번의 부모노드는 1번이 됩니다. (단. 둘 중 더 작은번호가 부모노드 우선권이 있다고 가정할 때) 그런데 3개이상 연결이 될 땐 신경써줘야 할 부분이 생깁니다. 이처럼 3번째 노드의 부모는 1이 되어야 하지만 2로 지정되어 있습니다. 이 문제점을 해결하기 위해선..

안녕하세요! 허언증입니다. 버블정렬에 대해 공부 하도록 하겠습니다. 버블정렬(Bubble Sort)? 옆에 있는 값과 비교 후 작은 값을 앞으로 보내면 어떨까? 생각에서 만들어지게 된 알고리즘 입니다. 곧 바로 예시로 한 번 알아보도록 하겠습니다. 1, 5, 3, 10, 4, 7, 9, 2, 6, 8 (정렬되지 않은 숫자 1~10까지의 나열 된 상태입니다) 버블정렬의 방식으로 나열을 시작하면 첫 번째 자리에 있는 1을 기준으로 2번 자리 값과 비교를 하고 작은 수와 자리를 바꿔줍니다. 1은 이미 제일 작은 수 이기도 하고 첫 번째자리에 있으니 변화가 없습니다. 이제는 두 번째 자리와 세 번째 자리와 비교를 합니다. 1, 5, 3, 10, 4, 7, 9, 2, 6, 8 두 번째자리인 5 와 세 번째 자리를..

안녕하세요! 허언증입니다. 선택정렬에 대해 공부 하도록 하겠습니다. 선택정렬(Selection Sort)? 가장 작은 것을 앞으로 이동시키면 어떨까? 생각에서 만들어지게 된 알고리즘 입니다. 곧 바로 예시로 한 번 알아보도록 하겠습니다. 1, 5, 3, 10, 4, 7, 9, 2, 6, 8 (정렬되지 않은 숫자 1~10까지의 나열 된 상태입니다) 선택정렬의 방식으로 나열을 시작하면 첫 번째 자리에 있는 1을 기준으로 2~10번 자리까지 비교를 하고 제일 작은 수와 자리를 바꿔줍니다. 1은 이미 제일 작은 수 이기도 하고 첫 번째자리에 있으니 변화가 없습니다. 이젠 첫 번째 자리를 제외하고 두 번째 자리에 있는 5를 가지고 비교를 시작합니다. 1, 5, 3, 10, 4, 7, 9, 2, 6, 8 3~10번..

시간복잡도 시간 복잡도란 big-O에 대한 시간 개념으로 알고리즘의 수행 시간이 얼마인지를 나타냅니다. 간단히 생각해서 프로그램이 총 몇번의 명령을 실행하는가? 입니다. 간단하게 예시를 두개를 가지고 이야기를 하도록 하겠습니다. 위 그림은 for문을 이용해서 구구단을 출력하는 프로그램입니다. 컴퓨터가 프로그램의 결과를 산출하기까지 총 11번을 실행하게됩니다. 소스코드 4,5 = 2번 7~8 = 9번 총 11번 빅오표기법으로 O(11) 입니다. * 빅오표기법은 O(실행횟수)로 표시를 합니다 그 다음 소스코드를 확인해 볼까요? 같은 구구단을 출력하는 프로그램이지만, 이번엔 마지막수를 n으로 받았습니다. 고정적인 수가 아닌 n의 입력에 따라 숫자가 달라지며 명령어 횟수도 증가하게 됩니다. 소스코드 4,5 = ..