미리 알아가자.  1. 소수 판별 알고리즘 특정 N이 소수인지 아닌지 판별  특정 수가 소수인지 아닌지 알아 보려면 for문을 써야한다! # 소수 판별 함수ef is_prime_number(n): end = int(n**(1/2)) for i in range(2, end+1): if n % i == 0: return False return Trueprint(is_prime_number(4)) # 4는 소수가 아님print(is_prime_number(7)) # 7은 소수임 약수의 성질을 생각했을 때 약수(제곱근)까지만 확인하면 된다.  모든 약수가 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이루는 것을 알 수 있다예를 들어 16의 약수는 1, ..

투 포인터 문제집 : https://www.acmicpc.net/workbook/view/8709 문제: https://www.acmicpc.net/problem/1806 문제10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.입력첫째 줄에 N (10 ≤ N 출력첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.예제 입력 110 155 1 3 5 10 7 4 9 2 8예제 출력 12  입력 범위는 굉장히 크고 시간 제한은 굉장히 짧다.  이전에 2230번: 수 고르기 문제  https://hyundoil..

투 포인터 문제집 : https://www.acmicpc.net/workbook/view/8709 문제: https://www.acmicpc.net/problem/2230 문제N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오.예를 들어 수열이 {1, 2, 3, 4, 5}라고 하자. 만약 M = 3일 경우, 1 4, 1 5, 2 5를 골랐을 때 그 차이가 M 이상이 된다. 이 중에서 차이가 가장 작은 경우는 1 4나 2 5를 골랐을 때의 3이 된다.입력첫째 줄에 두 정수 N, M이 주어진다. 다음 N개의 줄에는 차례로 A[1], A[2], …, A[N]이 ..

문제집: https://www.acmicpc.net/workbook/by/BaaaaaaaaaaarkingDog 문제: https://www.acmicpc.net/problem/13711 이전 문제:LCS https://hyundoil.tistory.com/357LCS2 https://hyundoil.tistory.com/369LCS3 https://hyundoil.tistory.com/370 LCS 문제 모음 : https://www.acmicpc.net/workbook/view/5080문제LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.예를 들어, [1, 2, 3]과 [1, 3,..

문제집: https://www.acmicpc.net/workbook/by/BaaaaaaaaaaarkingDog 문제: https://www.acmicpc.net/problem/1958 이전 문제:LCS https://hyundoil.tistory.com/357LCS2 https://hyundoil.tistory.com/369LCS 문제 모음 : https://www.acmicpc.net/workbook/view/5080 문제문자열과 놀기를 세상에서 제일 좋아하는 영식이는 오늘도 문자열 2개의 LCS(Longest Common Subsequence)를 구하고 있었다. 어느 날 영식이는 조교들이 문자열 3개의 LCS를 구하는 것을 보았다. 영식이도 도전해 보았지만 실패하고 말았다.이제 우리가 할 일은 다음과..

문제집: https://www.acmicpc.net/workbook/by/BaaaaaaaaaaarkingDog 문제: https://www.acmicpc.net/problem/9252 이전 문제: LCS https://hyundoil.tistory.com/357 LCS 문제 모음 : https://www.acmicpc.net/workbook/view/5080문제LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.입력첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자..