1. 문제 https://www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net 2. 풀이 아이디어 제한 시간이 2초인 만큼 모든 수를 선형탐색해도 시간이 넉넉하다. 따라서 1부터 N까지 반복문을 다음 수를 만들면 된다. 분해합이 N이 되는 순간 반복문을 멈추고 바로 답을 출력하면 통과 시간을 최대한 빠르게 할 수 있다. 분해합을 구하는 과정은 [자릿수 분해] 알고리즘을 사용한다. 알고리즘 순서 1 ~ N까지 반복문을 돌며 현재의 숫자의..

최적화(최대 or 최소)문제를 결정 문제로 바꾸어서 푸는 기법이다. 의심: 완전탐색, DP, 그리디로도 해결할 수 없는 최적화문제의 경우에 두 데이터간의 관계가 단순 비례 반비례에 따른 증감이며 Parameteric Search를 의심해볼 수 있다. 보통 감을 잡기가 매우 어려워서 나중에 돌아와서 떠올리면 베스트 파라메트릭 서치는 STL을 직접 이용할 수 있는 이분탐색과 달리 직접 변수를 설정하고 관계에 따라서 탐색의 범위를 지정해주어야 한다. ??? 예제: 랜선 자르기 백준 1654 주의 사항: 1. 무한 루프 주의: mid를 기준으로 선택의 범위가 균등한지 만약 균등하지 않다면 mid+1로 보정해줘서 무한루프를 방지해줘야함 2. 두 변수간의 관계주의: parameter과 target간의 관계(비례 반..

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억번 연산하는데 약 1초가 걸린다. 하지만 알고리즘 문제를 해결하다 보면 입력이 1억번 이상 주어지는 경우가 있다. 이때에는 모두 탐색할 경우 시간 초과가 날 가능성이 크다. 따라서 더 빠른 풀이방법을 생각해야 한다. 이런 경우 보통 이분탐색을 쓴다. 선형 탐색의 시간 복잡도를 O(lon N)으로 만들어준다. [반복문으로 구현한 이분 탐색] while(L arr[M]) L = M + 1; else if(target < arr[M]) R = M - 1; else { result = true; break; } } lower_bound upper_bound

https://jeonyeohun.tistory.com/86 [알고리즘 정리] 배낭 문제(Knapsack Problem) Knapsack Problem Knapsack Problem, 배낭문제는 다이나믹 프로그래밍에서 매우 유명한 문제이다. 어떤 배낭이 있고 그 배낭안에 넣을 수 있는 최대 무게가 K라고 하자. 배낭에 넣을 수 있는 N개의 물건이 jeonyeohun.tistory.com 예제로는 [백준 12865번] 평범한 배낭을 참고한다. 이 문제는 NP-hard문제이다. optimazation problem 모든 경로를 탐색하여 최적해를 찾는 문제!! DP를 이용해야겠지?? 경로: 해당 무게로 만들 수 있는 조합 값: V가치 1. top - down 방식 2. bottom - up 방식 tabulat..

1. 문제 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 중복을 허락하여 해당 동전을 만들 수 있는 경우이므로 자연수 분할, 즉 중복 조합문제이다. 2. 풀이 아이디어(시행착오) 동전 n개로 k원을 만들 수 있는경우의 수를 구하는 문제이다. 언뜻 보기엔 일반적인 DFS로 재귀를 이용한 top - down방식으로 풀 생각이 들 수 있다. 예들 들어 1, 2원짜리 동전을 가지고 4원을 만드는 경우 3원(4 - 1원)에 1원을 더한 것과 2원(4 -..

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