[Algorithm] 4주차 스터디 - 정렬, 다이나믹 프로그래밍, 그리디

 

---

목차

1. 개념 정리

(1) 정렬

(2) 다이나믹 프로그래밍

(3) 그리디

 

2. 4주 차 필수 문제 풀이

(1) A - 단어 정렬 (백준 1181번)

(2) B - 팔찌 만들기 (백준 25707번)

(3) C - 개발자 지망생 구름이의 취업 뽀개기 (백준 29155번)

(4) D - 피보나치 비스무리한 수열 (백준 14495번)

(5) E -  연속합 (백준 1912번)

---

 

1. 개념 정리

(1) 정렬

1 -1. Merge Sort

• 재귀적으로 수열을 나눠 정렬한 후 합치는 정렬법이다.
• 시간복잡도 O(NlogN)에 동작한다. 
• 길이 N과 길이 M 인 리스트가 만나 길이 N + M의 정렬된 리스트를 만든다. 
• 길이 N과 길이 M의 나머지 중 가장 앞에 있는 원소를 비교해 채워넣는다. O(N+M) 수행 가능
• 분할하는 과정에서 시간복잡도는 O(N) 이다. 
• 합쳐나가는 과정에서 시간복잡도는 O(NlogN) 이다. 
• Stable Sort 성질 : 우선순위가 같은 원소가 여러 개일땐 정렬한 결과가 유일하지 않을 때 원래의 순서를 따라가도록 한다. 

1-2. Quick Sort 

• * STL 대신 직접 구현해야 하는 경우 퀵소트 말고 머지소트를 쓸 것
• 맨 앞 원소를 pivot으로 두고 제자리로 둔다면 왼쪽과 오른쪽 구간을 따로 정렬하면 된다. 
• 추가적인 공간을 사용하지 않는 정렬을 In-Place Sort라고 한다. 
•  pivot 다음 원소를 L로 두고 마지막 원소를 r로 두었을 때, l을 pivot보다 큰 값이 나올 때까지 오른쪽으로 이동하고, r은 pivot보다 작거나 같은 값이 나올 때까지 왼쪽으로 이동한 후 swap 한다.  
• 시간복잡도는 O(NlogN)이다. 
• Cache hit rate 가 높지만 최악의 경우 시간복잡도가 O(N^2)이 된다. 

1-3 Counting Sort

• 각 수의 등장횟수를 저장해서 정렬하는 방식이다. 
• 미리 큰 테이블을 만들고 값을 1 증가시켜서 처리하는 방법
• 수의 범위가 제한되어 있을 때에는 구현이 간단해 활용되지만 수의 범위가 크면 사용할 수 없다. 

1-4 Radix Sort

• 자릿수를 이용해서 정렬을 수행하는 알고리즘, 카운팅 소트를 응용한 알고리즘 

1-5 STL Sort

• 최악의 경우에도 O(NlogN) 시간복잡도가 보장된다.
• Stable sort 가 아니라서 순서가 보존되지 않을 수 있어서 stable_sort 함수를 쓸 것. 
• 비교 함수는 두 값이 같을 때, 우선순위가 같을 떄 false 반환하니 주의
• 비교 함수의 인자로 STL 혹은 클래스 객체를 전달시 reference 사용하니 주의

[ 배열 프로그래밍 연습문제 ]

- BOJ 11728번 : 배열 합치기 https://www.acmicpc.net/problem/11728

- BOJ 15688번 : 수 정렬하기 5 https://www.acmicpc.net/problem/15688

- BOJ 11652번 : 카드 https://www.acmicpc.net/problem/11652

 

(2) 다이나믹 프로그래밍

: 여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘 

[다이나믹 프로그래밍 연습문제]

- BOJ 1463번 : 1로 만들기 https://www.acmicpc.net/problem/1463

- BOJ 9095번 : 1,2,3 더하기 https://www.acmicpc.net/problem/9095

- BOJ 2579번 : 계단 오르기 https://www.acmicpc.net/problem/2579

- BOJ 1149번 : RGB거리 https://www.acmicpc.net/problem/1149

- BOJ 11726번 : 2 X n 타일링 https://www.acmicpc.net/problem/11726

- BOJ 11659번 : 구간 합 구하기 4 https://www.acmicpc.net/problem/11659

- BOJ 12852번 : 1로 만들기 2 https://www.acmicpc.net/problem/12852

 

(3) 그리디

 지금 가장 최적인 답을 근시안적으로 택하는 알고리즘( = 관찰을 통해 탐색 범위를 줄이는 알고리즘)

이상적인 풀이 흐름
1. 관찰을 통해 탐색 범위를 줄이는 방법을 고안한다. 
2. 탐색 범위를 줄여도 올바른 결과를 낸다는 사실을 수학적으로 증명한다. 
3. 구현해서 문제를 통과한다.

[그리디 연습문제] 

- BOJ 11047번 : 동전 0 https://www.acmicpc.net/problem/11047

- BOJ 1931번 : 회의실 배정 https://www.acmicpc.net/problem/1931

- BOJ 2217번 : 로프 https://www.acmicpc.net/problem/2217

- BOJ 1026번 : 보물 https://www.acmicpc.net/problem/1026

- BOJ 12865번 : 평범한 배낭 https://www.acmicpc.net/problem/12865

- BOJ 1477번 : 휴게소 세우기 https://www.acmicpc.net/problem/1477

 

 

---

 

 

2. 4 주차 필수 문제 풀이

해당 주차는 C++을 사용했습니다

(1) A - 단어 정렬 (백준 1181번)

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

1181번: 단어 정렬

📢 풀이 : 정렬 알고리즘

✔️ cmp() : a와 b가 같을 때는 a < b가 false이므로 같은 문자열인 경우에도 중복을 제거할 수 있도록 정렬

✔️ 정렬된 문자열을 순회하면서 중복을 제거하고, 중복이 제거된 문자열을 출력

#include <iostream>
#include <algorithm>
using namespace std;

int cmp(string a, string b) {

	if (a.length() == b.length()) {
		return a < b;
	}

	else {
		return a.length() < b.length();
	}
}

string word[20000];

int main() {
	int N;

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> word[i];
	}

	sort(word, word + N, cmp);

	for (int i = 0; i < N; i++) {
		if (word[i] == word[i - 1]) {
			continue;
		}
		cout << word[i] << "\n";
	}

	return 0;
}

 

(2) B - 팔찌 만들기 (백준 25707번)

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

25707번: 팔찌 만들기

📢 풀이 : 정렬 알고리즘 

✔️ N개의 정수를 입력받아, 그 중에서 가장 작은 수와 가장 큰 수를 찾은 후에 두 수의 차이를 2배한 값을 반환

✔️ 각 입력된 정수(curNum)에 대해 minNum과 maxNum을 갱신하여 현재까지의 최솟값과 최댓값을 유지

#include<iostream>
#include<limits.h>
using namespace std;

int N;

int solution() {
	int minNum = INT_MAX;
	int maxNum = 0;

	for (int i = 0;i < N; i++) {
		int curNum;
		cin >> curNum;

		minNum = min(minNum, curNum);
		maxNum = max(maxNum, curNum);
	}

	return (maxNum - minNum) * 2;
}

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

	cin >> N;

	cout << solution();

	return 0;
}

 

(3) C - 개발자 지망생 구름이의 취업 뽀개기 (백준 29155번)

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

29155번: 개발자 지망생 구름이의 취업 뽀개기

📢 풀이 :

✔️ for 루프를 통해 각 시험에 대해 최적의 스케줄을 계산

✔️ 난이도가 0보다 크면 해당 난이도의 문제를 푼 것으로 간주하고 시간표를 갱신

import sys
input = sys.stdin.readline

# 입력
N = int(input())
level = list(map(int, input().split())) # 난이도별 풀 문제

exam = []
for _ in range(N):
    exam.append(list(map(int, input().split())))

exam.sort()
res = 0
before_level = 1
before_time = 0
first_clear = True

for i, j in exam:
    if level[i-1] > 0:
        res += j
        level[i-1] -= 1

        # 처음 푼 경우
        if first_clear:
            first_clear = False

        # 난이도가 같은 경우
        elif before_level == i:
            res += (j - before_time)

        # 난이도가 다른 경우
        elif before_level != i:
            res += 60

        before_level = i
        before_time = j
print(res)

(4) D - 피보나치 비스무리한 수열 (백준 14495번)
https://www.acmicpc.net/problem/14495

14495번: 피보나치 비스무리한 수열

📢 풀이 : 다이나믹 프로그래밍 

✔️ 수열의 점화식은 dp[n] = dp[n - 1] + dp[n - 3]

✔️ 반복문을 통해 dp[n]을 dp[n - 1] + dp[n - 3]으로 갱신

#include <bits/stdc++.h>
using namespace std;
long long dp[117];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n;
	cin >> n;
	dp[1] = 1, dp[2] = 1, dp[3] = 1;
	for (int i = 4; i <= n; i++) {
		dp[i] = dp[i - 1] + dp[i - 3];
	}
	cout << dp[n];
}

 

(5) E -  연속합 (백준 1912번)

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

1912번: 연속합

📢 풀이 : 그리디

✔️ 수열에서 연속된 부분 수열 중 합이 최대인 값을 찾아 출력

✔️ DP를 사용하여 각 위치까지의 최대 부분 수열 합을 계산하고, 그 중 최대값을 찾는다.

#include <iostream>
#define MAX 100001
using namespace std;
int series[MAX], dp[MAX]={0,};
int main() {
    int n, i;
    cin>>n;
    for(i=0; i<n; i++) {
        cin>>series[i];
        dp[i]=series[i];
    }
    int maxSum=dp[0];
    for(i=1; i<n; i++) {
        dp[i]=max(dp[i], dp[i-1]+series[i]);
        if(dp[i]>maxSum) {
            maxSum=dp[i];
        }
    }
    cout<<maxSum<<endl;
    return 0;
}

참고 자료 : 강좌 [실전 알고리즘] 0x0E ~ 0x11강 BaaaaaaaarkingDog