1. 문제 https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 2. 접근 방법 그리디를 떠올릴 수만 있다면 아주 쉬운 문제입니다. 하지만 그리디를 떠올리기 쉽지 않으므로 항상 일관된 알고리즘적 사고가 필요한 것 같습니다. 따라서 평소처럼 일관된 방법으로 접근했습니다. 아이디어 완전 탐색으로 생각해볼 때 나올 수 있는 모든 가지수는 1000!입니다. 팩토리얼의 허용 범위는 11이므로 불가능합니다. 완전 탐색이 불가능하여 DP로 접근해보았습니다. 이 문제의 조건을 보니 조합이 아니..

[목차] 1. 다익스트라 알고리즘이란? 알고리즘 알고리즘 원리 구현 O(n²) O(ElogE) 알고리즘 분석 의의 다익스트라는 일종의 그리디 이다. 왜? 매 순간 다음 정점을 선택할 때 가중치가 최소인 정점을 선택하기 때문이다. 하지만 그리디의 특성상 부분 최적해가 전체의 최적해를 보장해야 위의 선택이 합리적이라고 할 수 있다. 그렇다면 매 순간 최소 가중치를 가진 정점을 선택하면 항상 최소가 보장될까? 직관 이를 귀류법으로 증명해보자. 반례 [원시적인 다익스트라 알고리즘] #include #include #include #define F first #define S second using namespace std; typedef pair PII; int V, E, st, en; int d[10001];..

1. 문제 https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 2. 풀이 아이디어 완전 탐색으로 로프의 모든 조합을 비교하면 부분집합의 개수를 구하는 문제와 같아진다. 이런 경우 2ⁿ의 가지수가 생긴다. 최대 N이 10⁵이므로 완전 탐색을 이용할 경우 무조건 시간 초과가 발생한다. DP를 사용하여 memoization한다고 해도 O(N²)의 시간 복잡도를 가지므로 제한 시간내에 통과할 수 없다. 따라서 더 빠른 풀이를 생각해야 한다. 그러..

이번 글에서는 그리디 알고리즘에 대해 다루어 보겠습니다. 가장 대표적인 예제인 동전 문제와 회의실 배정 문제와 함께 다룰 예정이니 참고해 주세요 1. 탐욕법이란? 탐욕법이란 미래를 고려하지 않고 현재 가장 최선의 선택을 하는 알고리즘입니다. 쉽게 말하면 한 번 선택하고 난 후 앞이나 뒤를 전혀 돌아보지 않는 알고리즘입니다. 2. 특징 그리디 알고리즘에서는 다음의 특징을 가집니다. 그리디 선택 속성(Greedy Choice Property) 현재 선택은 미래의 선택에 영향을 미치지 않습니다. 이를 그리디 선택 속성이라고 합니다. 최적 부분 구조 현재 선택들이 모여 전체의 최적해를 보장해야만 믿고 현재 최선의 선택을 할 수 있습니다. 앞에서 말했듯이 미래의 선택을 고려하지 않고 과거도 돌아보지 않기 때문에 ..

1. 문제 https://www.acmicpc.net/problem/28323 28323번: 불안정한 수열 $N$개의 자연수가 좌우 일렬로 놓여 있다. 왼쪽에서 $i$ ($1 \le i \le N$)번째에 놓여 있는 자연수는 $A_i$다. 여러분은 이 중 몇 개의 자연수를 원하는 만큼 고를 수 있다. 단, 아무 자연수도 고르지 않 www.acmicpc.net 2023년 정보올림피아드 초등부 1번 문제이다. 2. 풀이 문제에서 정의한 불안정안 수열이란 이웃한 두 숫자의 합이 모두 홀수인 수열을 말한다. 자연수의 배열이 주어졌을 때 최대 몇개의 숫자로 불안정한 수열을 만들 수 있는지 구하는 문제이다. 불안정한(이웃한 두 수의 합이 모두 홀수인) 수열을 만들려면 수열을 탐색하며 이웃한 두 수의 합이 짝수가 되..