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