4개 원소를 골라서 짝지어서 쌍을 만들어 크기 비교하는 놀라운 방법

20366번: 같이 눈사람 만들래? n개의 눈덩이가 있는데, 2개의 눈덩이를 합쳐서 1개의 눈사람을 만들 수 있다 n개중 4개의 눈덩이를 골라 2개의 눈사람을 만들려고 한다 이때 눈덩이 크기의 합이 눈사람의 크기라고 할때, 두 눈사람의 크기 차이가 최소가 되도록 하려고 한다 최솟값을 구하면? -------------------------------------------------------------------------------------------------------------------------------------------------------- n이 최대 600인데 이중 4개를 고르면 600C4로 못해도 600*599*598*597 정도에 근사하는 정도? 아무튼 10^8을 가뿐하게 넘는다..

• format_list_bulleted 알고리즘/정렬 알고리즘
• · 2025. 3. 4.
• textsms

파이썬 pair type stable sort 배우기(tuple counting sort)

https://blog.naver.com/jqkt15/222031601969 [알고리즘] Counting Sort for Stable Sort - Pair Type (ppt, 소스코드) * 소스 코드 * blog.naver.com 1. stable counting sort 원소가 (첫번째 원소, 두번째 원소)의 튜플로 이루어졌을때, 이를 stable하게 counting sort하는 방법 https://deepdata.tistory.com/367 조건을 만족할때 매우 빠른 정렬 - counting sort 1. counting sort(카운팅 정렬) 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여, 선형 시간에 정렬하는 효율적인 알고리즘 하지만 제한사항이 있다 정수나 정수..

• format_list_bulleted 알고리즘/정렬 알고리즘
• · 2023. 8. 16.
• textsms

필요한 위치에 삽입하면서 정렬하는 삽입정렬(insertion sort)

1. 개요 선택 정렬은 실제 사용하기에는 매우 느린편이다. 그렇다면 다른 접근 방법은 없을까? "데이터를 하나씩 확인하면서 각 데이터를 적절한 위치에 삽입하면 어떨까?" 삽입 정렬은 선택 정렬처럼 동작 원리를 직관적으로 이해하기 쉽지만, 구현 난이도가 더 어려운데, 하지만 선택 정렬에 비해 실행 시간 측면에서 효율적이라고 알려져있다 특히 삽입 정렬은 필요할 때만 위치를 바꾸므로 "데이터가 거의 정렬되어 있을때" 매우 효율적이다 선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸는 반면, 삽입 정렬은 그렇지 않다 삽입 정렬은 특정한 데이터를 적절한 위치에 삽입한다는 의미에서 삽입 정렬(insertion sort)이라고 부른다. 더불어 삽입 정렬은 특정한 데이터가 적절한 위치..

• format_list_bulleted 알고리즘/정렬 알고리즘
• · 2022. 10. 9.
• textsms

거품이 올라오는 것처럼 정렬하는 bubble sort(버블 정렬)

1. 개요 인접한 두개의 원소를 비교하면서 자리를 계속 교환하면서 정렬하는 알고리즘 첫번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리까지 이동 한 단계가 끝나면, 가장 큰 원소가 마지막 자리로 이동함 교환하면서 자리를 이동하는 모습이 물 위에 올라오는 거품 모양과 같다고 하여 버블 정렬이라고 부름 2. 예시를 통해 이해하는 버블 정렬 55, 7, 78, 12, 42를 정렬한다고 생각해보자. 먼저 55와 7을 비교하여, 55가 더 크니까 자리를 바꾼다. 다음 55와 78을 비교하여, 78이 더 크니까 자리를 바꾸지 않는다. 다음 78과 12를 비교하여 78이 더 크니까 자리를 바꾼다 마지막으로 78과 42를 비교하여, 78이 더 크니까 자리를 바꾼다. 그러면 배열에서 가장 큰 원소인 ..

• format_list_bulleted 알고리즘/정렬 알고리즘
• · 2022. 10. 9.
• textsms

가장 원시적인 정렬 알고리즘인 selection sort(선택 정렬)

1. 정렬(sorting) 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 프로그램에서 데이터를 가공할 때 오름차순이나 내림차순 등 대부분 어떤 식으로든 정렬해서 사용하는 경우가 많기에, 정렬 알고리즘은 프로그램을 작성할 때 가장 많이 사용되는 알고리즘 중 하나 정렬 알고리즘으로 데이터를 정렬하면, 이진 탐색(binary search)이 가능해진다. 즉, 이진 탐색의 전처리 과정이기도 하다. 정렬을 공부하다보면 알고리즘의 효율성을 쉽게 이해할 수 있어 상황에 적절하지 못한 정렬 알고리즘을 이용하면, 당연히 프로그램은 비효율적으로 동작하면서, 필요 이상으로 시간을 많이 소요 여기 숫자 카드 10장이 있다. 7, 5, 9, 0, 3, 1, 6, 2, 4, 8 어떻게 이 카드를 정렬할 수 있을까? 보통은 ..

• format_list_bulleted 알고리즘/정렬 알고리즘
• · 2022. 10. 9.
• textsms

병합 정렬(merge sort) 알고리즘 파헤치기

1. 병합정렬(merge sort) 여러개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방식 분할 정복 알고리즘을 활용함 주어진 자료를 최소 단위의 문제까지 나눈 다음에 차례대로 정렬해가면서 최종 결과를 얻어내는 방식 시간복잡도는 O(nlogn) 2. 개요 - 간단한 과정 - [69,10,30,2,16,8,31,22]를 병합정렬한다면?? 2-1) 분할과정 절반씩 자료를 왼쪽, 오른쪽으로 나눠가고 더 이상 쪼갤 수 없을때까지 반복해서 나눈다 2-2) 병합과정 가장 밑단의 왼쪽 부분집합과 오른쪽 부분집합의 원소 크기를 서로 비교하여 정렬하여 병합시키고, 최종 1개로 병합될때까지 반복함 3. 구현 길이가 1이면 정렬하지말고, 바로 return 길이가 1보다 크다면, 왼쪽과 오른쪽을 나눠준다..

• format_list_bulleted 알고리즘/정렬 알고리즘
• · 2022. 9. 28.
• textsms