오일러 피 오일러 피 함수 P[N]의 정의는 1부터 N까지 범위에서 N과 서로소인 자연수의 개수를 뜻한다. 오일러 피 함수는 증명 과정을 공부해야 완벽하게 알 수 있다고하지만 실제 코딩 테스트에 사용하기 위한 구현 부분만 알아보겠다. 오일러 피의 핵심 이론 오일러 피 함수의 원리는 에라토스테네스의 체와 비슷하다. 오일러 피 함수의 원리 1 구하고자 하는 오일러 피의 범위만큼 리스트를 자기 자신의 인덱스값으로 초기화한다. 2 2부터 시작해 현재 리스트의 값과 인덱스가 같으면(= 소수일 때) 현재 선택된 숫자(K)의 배수에 해당하는 수를 리스트에 끝까지 탐색하며 P[i] = P[i] - P[i]/K 연산을 수행한다(i는 K의 배수). 3 리스트의 끝까지 과정 2 를 반복하여 오일러 피 함수를 완성한다. 수학..

백준 2750 - 수 정렬하기 문제 https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 답안 코드 : N = int(input()) A = [0]*N for i in range(N): A[i] = int(input()) for i in range(N-1): for j in range(N-1-i): if A[j] > A[j+1]: temp = A[j] A[j] = A[j+1] A[j+1] = temp for i in range(N): print(A[i]) ..

소수 소수 구하기의 핵심 이론 소수를 구하는 대표적인 판별법으로는 에라토스테네스의 체를 들 수 있다. 에라토스테네스의 체 원리는 다음과 같다. ① 구하고자 하는 소수의 범위만큼 1차원 리스트를 생성한다. ② 2부터 시작하고 현재 숫자가 지워진 상태가 아닌 경우 현재 선택된 숫자의 배수에 해당하는 수를 리스트에서 끝까지 탐색하면서 지운다. 이때 처음으로 선택된 숫자는 지우지 않는다. ③ 리스트의 끝까지 ②를 반복한 후 리스트에서 남아 있는 모든 수를 출력한다. 에라토스테네스의 체를 사용할 때 시간 복잡도 일반적으로 에라토스테네스의 체를 구현하려면 이중 for문을 이용하므로 시간 복잡도가 O(N^2) 정도라고 판단할 수 있다. 하지만 실제 시간 복잡도는 최적화의 정도에 따라 다르겠지만, 일반적으로 O(Nlo..

백준 11286 - 절댓값 힙 문제 https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 답안 코드 : from queue import PriorityQueue import sys print = sys.stdout.write input = sys.stdin.readline N = int(input()) myQueue = PriorityQueue() for i in range(N): request = int(input()) if ..

그리디 그리디 알고리즘은 현재 상태에서 볼 수 있는 선택지 중에 최선의 선택을 하는 알고리즘이다. 그리디 알고리즘은 동적 계획법보다 구현하기 쉽고 시간 복잡도가 우수하다. 하지만 항상 최적의 해를 보장하지 못한다... 그래서 코테에서는 그리디 알고리즘 사용 전에 항상 그리디 알고리즘을 적용할 때의 논리 유무를 충분히 살피라고 한다. 그리디 알고리즘의 핵심 이론 그리디 알고리즘 수행 과정 1. 해 선택: 현재 상태에서 가장 최선이라고 생각되는 해 선택 2. 적정설 검사: 현재 선택한 해가 전체 문제의 제약 조건에서 벗어나지 않는지 검사하기 3. 해 검사: 현재까지 선택한 해 집합이 전체 문제를 해결 가능한 지 검사 만약 전체 문제를 해결 못할거 같으면 1로 돌아가 과정 반복 문제 풀면서 익히는게 가장 좋다..

백준 2164 - 카드2 문제 https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 답안 코드 : from collections import deque N = int(input()) myQueue = deque() for i in range(1, N+1): myQueue.append(i) while len(myQueue) > 1: # 카드가 1장 남을 때까지 myQueue.popleft() # 맨 위의 카드를 버림 myQueue.append(myQu..