우리들의 T'SPACE

효율적인 정렬을 위한 강력한 무기, 합병 정렬 프로그래밍 분야에서 정렬 알고리즘은 매우 중요한 위치를 차지합니다. 데이터를 특정 순서로 정렬하는 것은 다양한 문제를 해결하는 데 필수적입니다. 이러한 정렬 알고리즘 중 하나인 머지 소트(Merge Sort)는 분할 정복(Divide and Conquer) 기법을 활용하여 효율적이고 안정적인 정렬을 수행합니다. 작동 원리 살펴보기 머지 소트는 다음과 같은 세 단계로 진행됩니다. 1. 분할(Divide) 먼저, 정렬해야 할 배열을 두 개의 서브 배열로 나눕니다. 이 과정을 재귀적으로 반복하여 배열의 크기가 1이 될 때까지 계속 분할합니다. 배열의 크기가 1이 되면 더 이상 나눌 수 없으므로, 이를 기저 조건(base case)으로 합니다. 2. 정복(Conqu..

퀵 정렬(Quick Sort) 이해하기 퀵 정렬이란? 퀵 정렬은 분할 정복(Divide and Conquer) 기법을 활용한 효율적인 정렬 알고리즘입니다. 1959년 영국 컴퓨터 과학자 토니 호어(Tony Hoare)가 개발했습니다. 불안정 정렬에 속하며, 비교 기반의 정렬 알고리즘 중 하나입니다. 동작 원리 피벗(Pivot) 선택: 정렬할 리스트에서 하나의 원소를 피벗으로 선택합니다. 일반적으로 리스트의 첫 번째 또는 마지막 원소를 피벗으로 사용합니다. 파티셔닝(Partitioning): 피벗을 기준으로 리스트를 두 개의 부분 리스트로 분할합니다. 피벗보다 작은 값은 왼쪽 부분 리스트에, 큰 값은 오른쪽 부분 리스트에 배치합니다. 재귀 호출(Recursive Call): 분할된 두 개의 부분 리스트에 ..

안녕하세요, 오늘은 선택 정렬(Selection Sort)에 대해 알아보겠습니다. 선택 정렬은 가장 기본적인 정렬 알고리즘 중 하나입니다. 정렬되지 않은 배열에서 작은 값부터 차례대로 선택해 앞쪽으로 가져오는 방식으로 정렬을 수행합니다. 구현 방법이 매우 간단하고 이해하기 쉬운 것이 장점입니다. 선택 정렬의 동작 원리 배열에서 가장 작은 값을 선택합니다. 선택한 값을 맨 앞으로 옮깁니다. (첫 번째 자리) 남은 배열에서 두 번째로 작은 값을 선택합니다. 선택한 값을 두 번째 자리로 옮깁니다. 이런 식으로 배열의 끝까지 반복합니다. 이렇게 하면 매 단계마다 작은 값부터 순서대로 앞으로 이동하게 되어 정렬이 완성됩니다. 간단한 예시로 살펴보겠습니다. [5, 3, 8, 4, 9] 초기 배열 1. [3, 5, ..

삽입 정렬은 간단하면서도 직관적인 정렬 알고리즘입니다. 이 알고리즘은 배열의 모든 요소를 차례대로 이미 정렬된 배열 부분과 비교하여, 각 요소를 적절한 위치에 삽입하는 방식으로 동작합니다. 이 과정을 통해 배열이 점차적으로 정렬됩니다. 삽입 정렬의 작동 과정은 다음과 같습니다: 배열의 두 번째 요소부터 시작하여, 해당 요소가 이전에 정렬된 배열 부분에 삽입될 올바른 위치를 찾습니다. 이 요소를 그 위치에 삽입하고, 필요한 경우 나머지 요소들을 오른쪽으로 이동시켜 자리를 마련합니다. 배열의 모든 요소에 대해 이 과정을 반복합니다. 삽입정렬의 장점: 간단하고 이해하기 쉽습니다: 코드 구현이 간단하여 초보자도 쉽게 이해하고 구현할 수 있습니다. 안정적인 정렬 방법입니다: 같은 값의 요소가 입력에 주어진 순서를..

버블 정렬(Bubble Sort) - 단순하지만 효율적이지 않은 정렬 알고리즘 버블 정렬이란? 버블 정렬은 가장 기본적이고 직관적인 정렬 알고리즘 중 하나입니다. 배열의 인접한 두 원소를 비교하여 순서대로 정렬되어 있지 않으면 서로 위치를 교환하는 방식으로 동작합니다. 이 과정을 배열의 모든 원소가 정렬될 때까지 반복합니다. 버블 정렬의 작동 원리 배열의 첫 번째 원소와 두 번째 원소를 비교하여 순서대로 정렬되어 있지 않으면 서로 위치를 교환합니다. 이 과정을 배열의 마지막 원소까지 반복합니다. 이 과정을 배열의 모든 원소가 정렬될 때까지 반복합니다. 마지막 원소부터 차례대로 정렬이 완료되어, 가장 큰 원소가 배열의 끝으로 이동합니다. 버블 정렬의 장단점 장점: 구현이 매우 단순하여 이해하기 쉽습니다. ..

Binary Search는 정렬된 배열 내에서 대상 요소를 효율적으로 검색할 수 있는 강력한 알고리즘입니다. 이 알고리즘은 검색 공간을 반복적으로 절반씩 나누는 방식으로 작동하므로, 큰 규모의 정렬된 데이터셋에서도 매우 빠르게 동작합니다. 전제 조건: 정렬된 배열 Binary Search를 사용하기 위해서는 배열이 사전에 정렬되어 있어야 합니다. 배열이 정렬되어 있지 않다면 Binary Search가 올바르게 작동하지 않으며, 잘못된 결과를 얻을 수 있습니다. 이러한 요구 사항이 필요한 이유는 Binary Search가 배열의 정렬 순서에 의존하기 때문입니다. 이를 통해 알고리즘은 현재 검색 공간의 중간 요소와 대상 요소를 비교하여 다음에 검색할 절반을 결정할 수 있습니다. 그래서 Sorting이 중요함..

* 문제 이해와 해결 과정 땅을 고르게 만들어야 함. 땅을 고르게 만드는 방법에는 2가지가 존재하며 각각 소요시간이 다름. 땅의 높이는 0~256이 될 수 있음. 나에게 주어지는 것은 땅의 가로, 세로 길이와 각 땅의 높이, 인벤토리에 보관 중인 블럭들임. 첫 시도는 실패했는데, 2가지 작업을 동시에 해줄 수 있다는 점과 높이가 0~256일 때의 모든 경우를 고려하여 탐색해야 한다는 점을 간과했다. 결국 문제에서 원하는 것은 최소 시간과 높이다. 높이가 0일 때 시간이 가장 적게 들 수도 있고, 높이가 256일 때 시간이 가장 적게 들 수도 있다. 1)블럭을 파내어 인벤토리에 넣는 작업과 2)인벤토리에 있는 블럭을 꺼내어 쌓는 작업을 적절하게 사용해야한다는 뜻이다. 그래서 높이가 0일때 부터 256일때 ..

https://www.acmicpc.net/problem/18110 18110번: solved.ac 5명의 15%는 0.75명으로, 이를 반올림하면 1명이다. 따라서 solved.ac는 가장 높은 난이도 의견과 가장 낮은 난이도 의견을 하나씩 제외하고, {5, 5, 7}에 대한 평균으로 문제 난이도를 결정한다. www.acmicpc.net * 해결 아이디어 N명의 사람의 15%를 구한 후, 1~30점 난이도 의견 배열의 앞과 뒤에서 1씩 빼준다. 그려면 30% 절사평균이 구현되며, 배열에 들어있는 값들을 평균내어 문제에 알맞게 출력하면 된다. #include #include #include #include #include #include #include #include #include #include #..

위와같은 두 행렬들이 있다하자 그러면 행렬 A와B의 곲 C는 다음과 같이 표현된다 그러면 아래와같이 이해될 수 있다 이 행렬의 곱 알고리즘의 시간 복잡도는 O(n^3)의 복잡도를 가진다 그래서 매우 큰 행렬들의 곱을 계산할 때는 매우 버거워진다 그의 결과로 분할정복의 한 방법인 Strassen 알고리즘이 나왔다 각 행렬들을 이렇게 4분할을 해보자 그러면 이렇게 계산해도 결과가 나온다 하지만 이건 또 결국 계산을 하다보면 O(n^3)의 복잡도를 가진다 그럼 Strassen 알고리즘은 어떻게 분할하냐? 위의 행렬들을 정의 해준다 그럼 아래와 같은 곱이 성립 한다 행렬의 곱셈을 한번 줄이고! 덧셈을 늘렸다! 그래서 O(n^3)->O(n^2) 로 수렴하게 된다 왜냐 행렬의 곱셈은 for문 골치거리이기 때문에 그..

C++ 입출력 최적화: sync_with_stdio와 cin.tie 이해하기 코딩테스트에서 표준 입출력을 사용할 때 주로 scanf/printf 또는 cin/cout을 사용합니다. C++에서는 string과 같은 편의 기능을 제공하는 cin/cout을 주로 사용하게 됩니다. 그러나 주의해야 할 점은 cin/cout을 사용할 때 시간초과를 막기 위해 특별한 조치가 필요하다는 점입니다. 1. ios::sync_with_stdio(0)과 cin.tie(0) C++에서는 입출력 버퍼를 동기화하는 작업이 기본적으로 수행됩니다. 그러나 이 작업은 입출력의 양이 많을 때 시간을 소비할 수 있습니다. 따라서, 입출력 작업이 많은 경우에는 이 동기화 작업을 해제하는 것이 좋습니다. 동기화 작업 해제를 위해 아래의 두 명..