최대공약수 math 내장 함수 사용하기 math.gcd(n, m) 유클리드 호제법 | a와 b 의 최대공약수는 (a를 b로 나눈 나머지)와 b 의 최대공약수와 같다. # a a) : a,b = b,a while(b!=0): a=a%b a,b=b,a 큰 수를 작은 수로 나누고 나누어 떨어질 때까지 계속 반복 최소공배수 math 내장 함수 사용하기 math.lcm(n, m) python 3.9부터 지원된다! 직접 구현하기 import math def lcm(a,b): return (a * b) // math.gcd(a,b)

에라토스테네스의 체 다수의 자연수에 대하여 소수 여부를 판별 1. 2부터 N까지의 모든 자연수를 나열한다. 2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다. 3. 남은 수 중에서 i의 배수를 모두 제거한다.(i는 제거하지 않는다.) 4. 더 이상 반복할 수 없을 때까지 2번과 3번의 과정을 반복한다. 이후 남아있는 수들은 모두 소수가 된다. python 구현 코드 import math n = 1000 array = [True for _ in range(n + 1)] # 소수일 경우 True, 소수가 아닐 경우 False로 표현 for i in range(2, int(math.sqrt(n)) + 1): if array[i] == True: j = 2 while i * j m c. a >..

최단 경로(Shortest Path) 가장 짧은 경로를 찾는 알고리즘 한 지점에서 다른 특정 지점까지의 최단 경로 구하기 모든 지점에서 다른 모든 지점까지 최단 경로 구하기 간선 간의 가중치가 있을 경우 활용 그리디, DP의 한 유형 다익스트라(Dijkstra) 특정 한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로 계산 ⭐️ 음의 간선이 없는 경우 사용 현실 세계의 프로그래밍을 할 때 많이 사용 매 상황 가장 비용이 적은 노드를 선택하므로 그리디 알고리즘으로 분류하기도 한다. 한번 방문한 노드일 경우 이후에 해당 노드에 대해 최단 경로가 다시 갱신되는 일은 없다. 1. 출발 노드 설정 2. 최단 거리 테이블 초기화(기본 무한) 3. 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 선택 4. 해..

다이나믹 프로그래밍(DP) 동적 계획법 💡 프로그래밍 분야의 '동적 메모리 할당'과 같은 '동적'의 의미가 아님을 유의 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장 └ 불필요한 계산을 줄임 사용 조건 최적 부분 구조(Optimal Substructure) 큰 문제를 작은 문제로 나눠 작은 문제의 답을 모아 큰 문제를 해결 중복되는 부분 문제(Overlapping Subproblem) 동일한 작은 문제를 반복적으로 해결 Example. 피보나치 수열 $ a_n=a_{n-1}+a_{n-2}, a_1 = 1, a_2 = 1 $ 피보나치 수열의 점화식 피보나치 수열처럼 수열 형태로 나타나는 경우가 많으므로 배열이나 리스트를 이..

개념 순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 정렬된 리스트에서만 사용이 가능하다. 시간복잡도는 O(lg n) 을 갖는다. 보통 시작점, 중간점, 끝점을 갖는 변수를 할당하여 값을 구한다. 💡 탐색 범위가 2,000만을 넘어가면 이진 탐색으로 접근해보자! 동작원리 중간점과 찾는 값을 비교하여 중간점을 기준으로 오른쪽(찾는 값이 더 큰 경우)에 있는 지, 왼쪽(찾는 값이 더 작은 경우)에 있는 지 비교한다. 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 lg N에 비례한다. 시간복잡도 : O(lg N) 이진 탐색(재귀) def binary_s..

정렬(Sorting) 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 선택 정렬(Selection Sort) 가장 작은 것을 선택해서 앞으로 보내는 과정을 반복 수행하는 방법 array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array)): min_index = i # 가장 작은 원소의 인덱스 for j in range(i + 1, len(array)): if array[min_index] > array[j]: min_index = j array[i], array[min_index] = array[min_index], array[i] # Swap print(array) 시간복잡도 $$ O(N^2) $$ 삽입 정렬(Insertion Sort) 특정한..

자료구조(Implementation) 데이터를 표현하고 관리하고 처리하기 위한 구조 대표적인 자료구조로는 스택과 큐가 있다. 이는 오버플로와 언더플로를 유의하며 사용해야한다. 오버플로(Overflow) 수용가능 데이터 범위를 벗어나, 이미 가득 찬 상태에서 삽입 연산을 수행할 때 발생 언더플로(Underflow) 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산 수행할 때 발생 스택(Stack) 선입후출(First In Last Out) or 후입선출(Last In First Out) stack = [] # 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제() stack.append(5) stack.append(2) stack.append(3) sta..

Reference 더보기 What’s New in Python 2.3 — Python 3.10.2 문서 This article explains the new features in Python 2.3. Python 2.3 was released on July 29, 2003. The main themes for Python 2.3 are polishing some of the features added in 2.2, adding various small but useful enhancements to the core language, and expanding docs.python.org 파이썬에서 슬라이싱으로 간격을 지정해서 표현할 수도 있다. 기본적인 인덱스 슬라이싱 방법 ex_list = [0, 1, ..

구현(Implementation) 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제 사소한 조건 설정이 많을 경우 구현하기가 까다로움 알고리즘은 간단한데 코드가 지나칠 만큼 길어니는 문제 실수 연산을 다루고 특정 소수점 자리까지 출력해야 하는 문제 문자열을 특정한 기준에 따라서 끊어 처리(파싱)해야하는 문제 적절한 라이브러리를 찾아서 사용해야하는 문제 Ex. Itertools 라이브러리 : 모든 순열이나 조합을 찾는 라이브러리 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야하는 문제 유형 변수의 표현 범위 : 파이썬에서는 기본적으로 큰 수의 연산을 지원해주기 때문에 변수의 표현 범위를 명시적으로 지정해주..