정렬 알고리즘 수행시간 비교
2020/03/10 - [Study/소프트웨어] - 컴퓨터 알고리즘 초급 #2 ( 선택정렬 in c ) 2020/03/18 - [Study/소프트웨어] - 컴퓨터 알고리즘 초급 #3 ( 삽입정렬 in c ) 2020/03/20 - [Study/소프트웨어] - 컴퓨터 알고리즘 초급 #4 ( 합병정렬 in c ) 2020/03/20 - [Study/소프트웨어] - 컴퓨터 알고리즘 초급 #5 ( 힙정렬 in c ) 2020/05/13 - [Study/소프트웨어] - 컴퓨터 알고리즘 초급 #6 ( 힙 정렬 in c ) 2 수행시간만 보면 효율적인 것은 nlgn을 가지는 정렬이다. mrege sort 는 nlgn이긴 하지만 추가 공간이 필요하다. heapsort 는 nlgn이긴 하지만 힙 구조를 만들고, 그 구조..
컴퓨터 알고리즘 초급 #6 ( 퀵 정렬 in c )
2020/03/20 - [Study/소프트웨어] - 컴퓨터 알고리즘 초급 #5 ( 힙정렬 in c ) 컴퓨터 알고리즘 초급 #5 ( 힙정렬 in c ) 힙 정렬 힙 정렬이란? - 힙의 특성을 이용한 정렬 수행시간 : 합병정렬과 동일한 O(nlogn), 삽입정렬과 동일한 제자리 정렬 (Sort in Place) 힙이란 ? - 완전 이진 트리에 가까운 형태 이진 트리란? - 각 �� 15051015.tistory.com 퀵 정렬 (Quicksort) : 피봇이라는 값을 기준으로 피봇보다 작은것은 왼쪽, 큰것은 오른쪽으로 보내는 파티셔닝이라는 작업을 반복해서 작은 숫자는 계속 왼쪽, 큰 숫자는 계속 오른쪽으로 보내서 정렬시키는 방법 Divide-and-Conquer paradigm을 사용 (작게 쪼개서 작은걸..
컴퓨터 알고리즘 초급 #6 ( 힙 정렬 in c ) 2
2020/03/20 - [Study/소프트웨어] - 컴퓨터 알고리즘 초급 #5 ( 힙정렬 in c ) 3산이 나오면 대피해야한다. ( 힙 구조 만들기 (Building a heap) BULID-MAX-HEAP(A) A.heap-size = A.length for i = [A.length / 2] downto 1 MAX-HEAPIFY(A,i) : 배열의 절반크기부터 자식과 부모를 비교하며 올라간다. 배열의 절반부터 하는 이유 : n번째 부모는 2/n에 있다. 2/n보다 큰 부모는 없다. 가장 마지막에 있는 부모가 2/n이다. 10개의 숫자가 배열로 입력되었을 때 이진 트리의 표현 방법 A = {4,1,3,2,16,9,10,14,8,7} 2/10 = 5 (자식을 가지는 마지막 노드) A[5] = 16 (자식..
객체지향 프로그래밍 (JAVA) 중간, 기말점수 및 등수
그때 당시의 중간고사와 기말고사를 떠올리면 중간고사는 알고리즘 문제에 가까웠다. 하지만 어려운 것은 아니었고 if문과 for 문을 적절히 활용하면 풀 수 있을 정도의 문제였다. 기말고사는 그때당시에 비주얼 프로그램을 했는데 (응용프로그램? 연산만이 아닌 화면과 버튼, 체크박스 등이 존재하는 프로그램을 만들었다.) 이것도 약간의 알고리즘이 들어갔지만, 화면을 어떻게 만들고 구성하고. 레이아웃들을 어떻게 배치할 수 있느냐가 관건 이었던 것 같다.
아는 동생이 부탁해서 만들어보았다. ㄹ자로 숫자가 출력된다. input : 4 , 6 으로 주었다. #include int main() { int input1; int input2; int a[100][100]; int i =0; int j =0; int count =1; printf("행 크기를 입력하세요\n"); scanf("%d",&input1); printf("열 크기를 입력하세요\n"); scanf("%d",&input2); for(i=0;i
컴퓨터 알고리즘 초급 #5 ( 힙정렬 in c )
힙 정렬 힙 정렬이란? - 힙의 특성을 이용한 정렬 수행시간 : 합병정렬과 동일한 O(nlogn), 삽입정렬과 동일한 제자리 정렬 (Sort in Place) 힙이란 ? - 완전 이진 트리에 가까운 형태 이진 트리란? - 각 노드의 자식수가 2이하인 경우 완전 이진 트리란 ? - Root(맨 위)노드부터 Leaf(가장 아래)노드까지 빠짐없이 채워져 있는 트리 여기서 root의 어원은 트리를 뒤집었을 때 가장 첫번째 . 뿌리라고하여 root라고 부른다. 완전 이진 트리의 조건은 왼쪽부터 차례로 채워야함. 만약 ㅇ ㅇ ㅇ ㅇ ㅇ 이렇게 있으면 왼쪽아래가 비어있다. 즉 왼쪽부터 차례로 채우지 않았기 때문에 완전이진트리가 아니다. ㅇ ㅇ ㅇ ㅇ ㅇ ㅇ ㅇ ㅇㅇㅇ 이렇게 있으면 오른쪽아래는 비어있지만 왼쪽부터 채..
합병 정렬 알고리즘 합병 정렬이란? - 합병을 이용한 알고리즘 합병이란? - 두개를 합치는 것 무엇을 합병할 것인가? 두개의 정렬된 배열을 하나의 배열로 합병 입력 : n개의 숫자 출력 : 정렬된 n 개의 숫자 ( 오름 차순 ) ex ) 배열 1 : 배열 2 : -> 결과 : Point : 두 정렬은 이미 정렬이 되어 있다. 알고리즘 : 배열 1과 배열 2의 첫번째 숫자를 비교해서 저 작은걸 결과의 첫번째에 넣어준다. 여기서는 배열 1의 첫번째 숫자 (1) 이 더 작으므로 1을 넣는다. 그 후 더 작았던 배열 1의 첫번째 숫자를 삭제한다. 그 후 배열 1의 첫번째 자리와 배열2의 첫번째 자리를 비교하는 작업을 반복한다. Step0 : 배열 1 : 배열 2 : -> 결과 : Step1 : 배열 1 : 배열..