본문 바로가기

알고리즘&자료구조/투 포인터5

백준 1806 1.문제이해 요약 : 길이 N의 수열의 연속된 수들의 부분합에서 그 합이 S 이상이 되면서 가장 짧은 부분합 길이를 출력 ex) N = {5, 10, 7, 4} 이고 S=15 일때, 5 + 10 or 10 + 7 + 4의 부분합을 구할 수 있음 연속된 수들이기 때문에 부분합은 두 개 이상의 연속된 수로 이루어져야 함 2.문제분석 S이상이 되는 부분합을 체크하고 그 부분합의 길이가 가장 짧은 부분합 길이(minLength)라면 해당 길이로 변경 로직 1. st, en 두 개의 커서를 배열의 시작 지점부터 한 칸씩 오른쪽으로 늘리면서 2개 이상의 수의 부분합으로 이루어져 있는가? 2. 부분합이 S 이상인가? 2.1. S이상이라면 부분합의 길이가 minLength 작은가? 2.1.1. minLength 보다 .. 2024. 2. 1.
백준 2230 1. 문제이해 요약 : 배열 A에서 두 수(N)를 골랐을 때 차이가 M이상이면서 제일 작은 차이를 구함 1 ≤ N ≤ 100,000 (배열 A의 크기) 0 ≤ M ≤ 2,000,000,000 0 ≤ |A[i]| ≤ 1,000,000,000 (배열 A에 들어갈 수 있는 값) 2. 문제분석 N 크기의 배열에서 두 수를 골라서 차이가 M이상인지 확인 M이상이면 차이를 구해서 제일 작은지 확인 배열의 크기가 100,000인 경우 이중 for문으로 푼다고 하면 100,000(i) * 100,000(j) = 10,000,000,000(백억) 알고리즘 문제에서 CPU가 1억 번 연산을 하는 동안 1초가 걸린다고 가정을 해보면 제한시간이 2초인 경우 2억 번 연산을 하므로 시간초과가 발생하게 된다. 이중 for문 방식.. 2024. 1. 30.
좋은 수 구하기(백준 1253) 1. 문제이해 N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다. N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라. 수의 위치가 다르면 값이 같아도 다른 수이다. (|Ai| ≤ 1,000,000,000, Ai는 정수) -> 음의 정수, 0도 포함 예시1) N=3 일때 3, 2, 5 어떤 수가 3일때 다른 두 수 2 + 5의 조합으로 나타내지 못함 어떤 수가 5일때 다른 두 수 3 + 2의 조합으로 나타낼 수 있으니까 좋은 수로 판단 예시2) N=2 일때 0, 0 어떤 수가 0일(첫번째 있는 0)때 다른 두 수가 없으므로 조합을 만들 수 없음 자기자신을 포함해서 조합을 만들 수 있지만 자기자신이 어떤 수에 포함되는 경우에는 최소.. 2024. 1. 21.
주몽의 명령(백준 1940) 1. 문제이해 재료개수(N)를 가지고 갑옷을 만드는데 필요한 수(M)를 몇 개 만들 수 있는지 갑옷을 만들기 위해서는 두 개의 재료를 합침 ex) N=3, M=5, N의 재료 1, 3, 4 -> 1 + 4 = 5 총 1개의 갑옷을 만들 수 있음 사용된 재료는 사라짐 2. 문제분석 재료를 정렬시킨 후 투 포인터를 배열의 양쪽 끝에 위치시킴 2 7 4 1 5 3 start end 1 2 3 4 5 7 start end start와 end 포인터가 가리키는 값을 더해서 M과 동일하면 두 개의 재료를 버리고 다음 위치로 이동 start와 end를 더했을 때 M보다 작다면 start 포인터 위치를 한 칸 증가시키고 end와 더해줌 (M보다 작으니까 값을 조금씩 키워서 M과 맞추기 위해 작은 수 중에서 그 다음으로.. 2024. 1. 18.

티스토리툴바