[BOJ알고리즘, C++]#11399_ATM, 정렬, 병합 정렬, 퀵 정렬

2024. 1. 26. 15:25· 문제 풀이/BOJ 문제 풀이
목차
  1. #1. 문제
  2. #2. 풀이
  3. 1. 병합 정렬
  4. 2. 퀵 정렬
  5. 3. 오름차순 정렬, 누적 합 계산!
  6. #1. 코드(병합 정렬)
  7. #2. 코드(퀵 정렬)

 

#1. 문제

https://www.acmicpc.net/problem/11399

 

11399번: ATM

첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)

www.acmicpc.net

 


 

#2. 풀이

 

1. 병합 정렬

 

[알고리즘]#3_정렬 알고리즘

#1. 개념 1. 정렬 알고리즘 [정의] : 정렬 알고리즘은 데이터를 특정한 순서로 재배치하는 알고리즘입니다. 정렬 순서는 일반적으로 오름차순(ascending order/less) 또는 내림차순(descending order/greater)으

webddevys.tistory.com

 

[정의] : 병합 정렬은 분할-정복에 기반한 정렬 알고리즘으로, 주어진 배열을 더 이상 나눌 수 없는 작은 크기까지 분할하고, 병합 과정에서 정렬 작업을 재귀적으로 수행하여 최종적으로 하나의 정렬된 배열을 얻습니다.

 

2. 퀵 정렬

 

[알고리즘]#3_정렬 알고리즘

#1. 개념 1. 정렬 알고리즘 [정의] : 정렬 알고리즘은 데이터를 특정한 순서로 재배치하는 알고리즘입니다. 정렬 순서는 일반적으로 오름차순(ascending order/less) 또는 내림차순(descending order/greater)으

webddevys.tistory.com

 

[정의] : 퀵 정렬 알고리즘은 분할-정복에 기반한 알고리즘으로, 주어진 배열을 피벗 원소를 기준으로 왼쪽은 피벗 원소보다 작은 원소들, 오른쪽은 큰 원소들로 정렬 및 분할 작업을 더 이상 나눌 수 없는 Base Case까지 재귀적으로 수행하여, 최종적으로 하나의 정렬된 배열을 얻습니다. 

 

3. 오름차순 정렬, 누적 합 계산!

 

  1. 먼저, 돈을 인출하는데 필요한 시간을 기준으로 오름차순 정렬해줍니다.
  2. 그리고, 해당 배열을 차례대로 순회하며 누적 합을 계산해 줍니다!

 


 

#1. 코드(병합 정렬)

 

// #1. 병합 정렬

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int N;
vector<int> v;

void Merge(vector<int>& arr, int left, int mid, int right)
{
    int leftSize = mid - left + 1;
    int rightSize = right - mid;
    
    vector<int> leftHalf(leftSize);
    vector<int> rightHalf(rightSize);
    
    for(int i=0; i<leftSize; ++i)
        leftHalf[i] = arr[left+i];
    
    for(int i=0; i<rightSize; ++i)
        rightHalf[i] = arr[mid+1+i];
    
    int leftIdx = 0;
    int rightIdx = 0;
    int resIdx = left;
    
    while(leftIdx < leftSize && rightIdx < rightSize)
    {
        if(leftHalf[leftIdx] <= rightHalf[rightIdx])
            arr[resIdx++] = leftHalf[leftIdx++];
        else
            arr[resIdx++] = rightHalf[rightIdx++];
    }
    
    while(leftIdx < leftSize)
    {
        arr[resIdx++] = leftHalf[leftIdx++];
    }
    
    while(rightIdx < rightSize)
    {
        arr[resIdx++] = rightHalf[rightIdx++];
    }
    
}

void MergeSort(vector<int>& arr, int left, int right)
{
    if(left < right)
    {
        int mid = left + (right-left)/2;
        
        MergeSort(arr, left, mid);
        MergeSort(arr, mid+1, right);
        
        Merge(arr, left, mid, right);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    
    while(N--)
    {
        int tmp;
        cin >> tmp;
        
        v.push_back(tmp);
    }
    
    // 병합 정렬
    MergeSort(v, 0, v.size()-1);
    
    // 누적 합 계산 및 결과 출력
    long long res = 0;
    for(int i=0; i<v.size(); ++i)
    {
        if(i != 0)
            v[i] += v[i-1];
        res += v[i];
    }
    
    cout << res;
    
    return 0;
}

 

#2. 코드(퀵 정렬)

 

// #2. 퀵 정렬

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int N;
vector<int> v;

int Partition(vector<int>& v, int l, int r)
{
    int piv = v[r];
    int i = l-1;
    
    for(int j=l; j<r; ++j)
    {
        if(v[j] <= piv)
        {
            i++;
            swap(v[j], v[i]);
        }
    }
    swap(v[i+1], v[r]);
    
    return i+1; 
}

void QuickSort(vector<int>& v, int l, int r)
{
    if(l < r)
    {
        int piv = Partition(v, l, r);
        
        QuickSort(v, l, piv-1);
        QuickSort(v, piv+1, r);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    
    v.resize(N);
    
    for(int i=0; i<N; ++i)
        cin >> v[i];
    
    // #1. 퀵 소트 수행
    QuickSort(v, 0, N-1);
    
    // #2. 결과 출력
    int res = v[0];
    for(int i=1; i<N; ++i)
    {
        v[i] = v[i-1] + v[i];
        res += v[i];
    }
    
    cout << res;
    
    return 0;
}

 


 

 

 

 

저작자표시 (새창열림)

'문제 풀이 > BOJ 문제 풀이' 카테고리의 다른 글

[BOJ알고리즘, C++]#11656_접미사 배열, 정렬, 퀵 정렬, 병합 정렬  (0) 2024.02.05
[BOJ알고리즘, C++]#2752_30, 정렬 알고리즘, 퀵 정렬, median-of-three  (1) 2024.01.26
[BOJ알고리즘, C++]#2217_로프, 정렬 알고리즘, 병합 정렬  (0) 2024.01.26
[BOJ알고리즘, C++]#1956_운동, 최단 경로, 플로이드, 플로이드 워셜  (1) 2024.01.26
[BOJ알고리즘, C++]#2665_미로 만들기, 최단 경로 알고리즘, 다익스트라 알고리즘  (1) 2024.01.26
  1. #1. 문제
  2. #2. 풀이
  3. 1. 병합 정렬
  4. 2. 퀵 정렬
  5. 3. 오름차순 정렬, 누적 합 계산!
  6. #1. 코드(병합 정렬)
  7. #2. 코드(퀵 정렬)
'문제 풀이/BOJ 문제 풀이' 카테고리의 다른 글
  • [BOJ알고리즘, C++]#11656_접미사 배열, 정렬, 퀵 정렬, 병합 정렬
  • [BOJ알고리즘, C++]#2752_30, 정렬 알고리즘, 퀵 정렬, median-of-three
  • [BOJ알고리즘, C++]#2217_로프, 정렬 알고리즘, 병합 정렬
  • [BOJ알고리즘, C++]#1956_운동, 최단 경로, 플로이드, 플로이드 워셜
Hardii2
Hardii2
Hardii2
개발 블로그
Hardii2
전체
오늘
어제
  • 분류 전체보기
    • 알고리즘
    • 웹 개발
      • Node.js
      • React
    • 게임개발
      • DirectX12
      • 관련 지식
      • Unreal C++
      • Unreal 블루프린트
    • 언어
      • Effective C++
      • Basic C++
      • 디자인 패턴
      • 자료구조
      • 기술 질문
    • 문제 풀이
      • BOJ 문제 풀이
      • Programmers 문제 풀이
      • geeksForgeeks 문제 풀이
    • 수학
      • 확률과 통계
      • 게임수학
    • 개인프로젝트
    • 그룹프로젝트
      • PM
      • Dev
    • Github

블로그 메뉴

  • 홈
  • 글쓰기

공지사항

인기 글

태그

  • dfs
  • BOJ
  • stl
  • DP
  • 트리
  • Effective C++
  • 개발
  • 알고리즘
  • 최단 경로
  • set
  • Unreal Blueprint
  • unreal
  • 디자인 패턴
  • programmers
  • 우선순위 큐
  • C++
  • 정렬
  • 기술 질문
  • 그래프
  • BFS

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
Hardii2
[BOJ알고리즘, C++]#11399_ATM, 정렬, 병합 정렬, 퀵 정렬
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.