공부하자

소수(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인 정점을 찾을 수 없기때문에 위상 정렬 적용 불가. 모든..

링크드 리스트 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조. 미리 연결된 공간을 예약해야 하는 배열의 단점을 극복한 자료구조. [ 기본 구조 및 용어 ] 현재 데이터와 다음 데이터의 주소값을 같이 가지고 있음. 노드(Node) : 데이터 저장 단위(데이터 값, 포인터)로 구성 포인터(Pointer) : 각 노드 안에서 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간 맨 앞에 있는 노드(head)의 주소만 알 수 있으면 전체의 주소값을 알 수 있음. [ 장·단점 ] 장점 미리 데이터 공간을 할당할 필요 없음( 배열) 단점 별도의 데이터 공간(포인터)이 필요, 저장 공간 효율이 안 좋음. 연결 정보를 찾는 시간이 필요, 접근 속도 느림 중간 데이터 삭제 시, 앞 뒤 데이터의 ..

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