공부하자

소수(Prime Number)란? 1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수 소수를 판별하는 데는 2가지 방법이 있다. 특정 수 N이 소수인지 알기위해, 2부터 N-1까지의 수로 N을 나눠보고, 어떤 수로도 나눠 떨어지지 않는 다면 N은 소수. 에라토스테네스의 체를 이용하는 방법 1. 2부터 n-1까지의 수로 n을 나눠보기 첫번째 방법을 코드로 나타내면 다음과 같다. def isPrime(n): for i in range(2, n): if n % i == 0: return False return True 이 코드는 2부터 n-1까지 모든 숫자를 확인하며 소수인지 판별하는 방법이기 때문에 시간 복잡도가 O(n)이 나온다. 숫자가 커질수록 오래걸린다. 여기서 약수의 특성인 대칭성을 사용하면 연..

문제 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N (10 ≤ N import sys input = sys.stdin.readline n, s = map(int, input().split()) arr = list(map(in..

알고리즘을 문제를 풀다보면 코테에 엄청 자주 나오지는 않지만 간혹가다 나오곤 하는 알아두면 좋은 투 포인터 알고리즘에 대해서 알아봅시다! 투 포인터 알고리즘이란 무엇일까? 1차원 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가면서 원하는 답을 얻는 알고리즘이다. 그렇다면 이 알고리즘은 언제 쓰면 좋을까? 알고리즘 문제를 완전탐색으로 풀었을 때, 시간초과가 나면 하나의 대안으로 투 포인터 알고리즘을 쓸 수 있다. 자세한 활용 방법은 투 포인터 예시 문제 중 하나이고 투 포인터에 대해서 가장 이해하기 쉬웠던 문제를 통해 알아보자. 문제 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고,..

문제 선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다. 함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 첫 번째 수를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다. 함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 수를 버리는 함수이다. 배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 최대 100이다. 각 테스트 케이..

문제 지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다. 지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다. 큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그..

위상 정렬 위상 정렬은 순서가 정해져 있는 작업을 차례로 수행해야 할 때, 순서를 결정해주는 알고리즘 DAG(Directed Acyclic Graph)그래프여야 함. 방향성이 있고, 사이클이 없는 그래프 위상 정렬의 시간 복잡도는 O(V + E)로 문제를 해결할 수 있음. 힙 자료구조와 함께 적용하면 쉽게 문제를 풀 수 있음. 위상정렬 알고리즘 순서 1) 진입 차수(Indegree, 자기 자신으로 오는 간선을 의미)가 0인 정점을 큐에 삽입한다. 2) 큐에 원소를 꺼내 해당 원소와 간선을 제거한다. 3) 제거 이후에 진입 차수가 0이 된 정점을 큐에 삽입한다. 4) 큐가 빌 때까지 2) ~ 3) 과정을 반복한다. * 사이클이 존재하면 진입차수가 0인 정점을 찾을 수 없기때문에 위상 정렬 적용 불가. 모든..

문제 두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다. 출력 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. 최대공약수와 최소공배수는 3가지 방법으로 구할 수 있다. 1) 최대공약수는 더 작은 값을 하나씩 줄여가며 for문을 돌립니다. a를 i로 나눴을 때, b를 i로 나눴을 때 둘다 나머지가 0인 값이 나오면 바로 출력해주고 for문을 끝냅니다. 이 때 출력되는 값이 가장 큰 공약수, 즉 최대공약수입니다. 최소공배수도 비슷한 방법으로 for문을 이용해서 코드를 짜면 됩니다. 달라지는 ..

문제 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다. 자연수 N이 주어졌을 때, g(N)을 구해보자. 입력 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 100,000)가 주어진다. 둘째 줄부터 테스트 케이스가 한 줄에 하나씩 주어지며 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 출력 각각의 테스트 케이스마다, 한 줄에 하나씩 g(N)를 출력한다. import sys ans = [..