중간에서 만나기3 - 부분집합의 합이 s가 되는 경우의 수를 세는 놀라운 방법

1. 중간에서 만나기(meet in the middle) 중간에서 만나기 알고리즘은, 다익스트라 알고리즘처럼 전형화된 그런 알고리즘은 아니다. 다이나믹 프로그래밍 같은 알고리즘이라고 해야할까 완전탐색의 시간복잡도가 매우 높을 때, 이를 절반으로 줄이는 기법이다. 가능한 경우의 수를 절반씩 나누어 탐색한 뒤 그 결과를 조합하여 정답을 찾는 방식이다. 예를 들어 브루트포스가 $O(2^{N})$으로 매우 높은 경우, $O(2^{N/2})$로 줄일 수 있을때 효과적이다. N = 40인 경우만 해도 아예 불가능한 정도가 $10^{6}$정도로 가능해진다 예를 들어 주어진 수열 A에서 부분집합의 합이 S가 되는 경우의 수는 몇가지일까? 부분집합의 개수는 $2^{N}$이므로, 시간복잡도는 $O(2^{N})$ 1)..

• format_list_bulleted 알고리즘/중간에서 만나기
• · 2025. 7. 4.
• textsms

중간에서 만나기2 - 홀수 위치 자리수들과 짝수 위치 자리수들의 곱이 서로 같은 n자리 자연수 찾는 마법같은 방법

14108번: Umnozak (acmicpc.net) n자리 자연수중에서 짝수 위치의 자리수들의 곱과 홀수 위치의 자리수들의 곱이 서로 같게되는 그러한 자연수들의 개수를 구하는 문제 첫번째 자리는 홀수 위치라고 가정 1자리 자연수는 홀수 위치밖에 없으니 0개 2자리 자연수는? 11,22,33,44,55,66,77,88,99로 9개 3자리 자연수는? 100부터 999까지 전수조사해보는게 나을 것 같다 count = 0for i in range(100,1000): s = str(i) a = 1 b = 1 for j in range(len(s)): if j % 2 == 0: a *= int(s[j])..

• format_list_bulleted 알고리즘/중간에서 만나기
• · 2024. 7. 24.
• textsms

중간에서 만나기1 - 현재 위치의 수가 앞에 있는 3가지 수들의 합과 같은 경우를 세는 방법

5624번: 좋은 수 (acmicpc.net) 정수 배열에서 현재 위치 i번째 수 앞에 있는 수들 중 세 수의 합이 현재 위치 i번째 수와 같게 되는 경우, 그러한 수의 개수를 구하는 문제 "세 수"는 중복해서 선택해도 좋다 예를 들어 [-1,2,0]이면 0은 -1 -1 + 2 = 0이므로 이 조건에 만족하는 수이다 n이 최대 5000인데, 단순하게 짜면 $O(N^{4})$이라 매우 느리다 대충 이런 느낌 for i in range(n): a = A[i] for j in range(i): for k in range(i): for w in range(i): ..

• format_list_bulleted 알고리즘/중간에서 만나기
• · 2024. 6. 10.
• textsms

[Java]HashMap 응용력 키우기2 -두 수의 합과 세 수의 합 그리고 네 수의 합-

1. 문제 n개의 정수가 입력으로 주어지고, 이 중 서로 다른 위치에 있는 두 개의 수를 뽑아 더했을 때 k가 되는 가짓수를 구하는 프로그램을 작성해보세요. 2. 풀이 가장 쉬운 방법은 $O(N^{2})$으로 해결하는 것이다. 배열에 N개의 정수를 모두 저장하고, 2중 for문을 돌아서 모든 쌍을 검사해서 합이 k가 되는지 검사해보는 것이다 하지만 N의 제한이 최대 10만이라면? 당연히 $O(N^{2})$의 알고리즘을 요구하는 문제는 아닐 것이다 합이 k가 되는 두 원소는 어떻게 선택할 수 있을까? 배열에서 한 원소를 골랐을때, 다른 원소는 무조건 k - (이전에 고른 원소)를 골라야할 것이다. 그러므로, HashMap에 배열의 모든 원소의 정보를 저장해두고, 배열에서 한 원소를 고르는 작업을 O(N)에..

• format_list_bulleted 알고리즘/중간에서 만나기
• · 2023. 3. 27.
• textsms