본문 바로가기

algorithm/기초
7

소수 판별하기: 기본, 제곱근, 에라토스테네스의 체 / Python / 예제 - Programmers 소수찾기 Prime Number, 소수1보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 자연수  소수 판별하기기본 알고리즘: 완전탐색2부터 x-1 까지 모든 수에 대하여 나누어 떨어지는지 확인모든 수를 확인해야하므로 시간복잡도는 O(X)def is_prime_number1(x: int):for i in range(2, x): # 2부터 x-1 까지의 모든 수를 확인 if x % i == 0: # x가 해당 수로 나누어 떨어진다면 return False # 소수가 아님return True # 소수임제곱근을 이용하기  약수는 배수의 특징을 가지고 있다. 가운데 약수(제곱근)을 기준으로 곱셈 연산에 대해 대칭을 이룬다. 따라서, 특정 자연수 x가 소수인지 판별하기 위해서는 제.. 2025. 3. 24.
이분탐색(이진탐색, Binary Search) / Python / 프로그래머스 입국심사 Binary Search(이진/이분 탐색)이름에서 알 수 있듯이, 배열을 둘로 나누어 탐색하는 것이다.정렬된 배열을 반으로 나누고, target의 값이 중앙값 보다 크면 탐색 시작지점을 중앙값 다음으로 옮기고, 작다면 탐색 종료 지점을 중앙값보다 이전으로 옮긴다.위의 과정을 target 값을 찾을 때까지 반복한다. 중앙값이 target값과 같다면 탐색을 종료한다.시간복잡도는 O(logN)코드로 구현해보기  1. 배열을 정렬한다  2. 시작점과 종료점을 설정하고, 중앙값을 계산한다.  3. 중앙값을 타겟값과 비교한다      3-1) 타겟값이 중앙값과 같다면 탐색을 종료한다.      3-2) 타겟값이 중앙값보다 크다면 시작점을 중앙값 다음으로 옮긴다.      3-3) 타겟값이 중앙값보다 작다면 종료점을.. 2025. 3. 20.
그리디 알고리즘: 거스름돈, 만들 수 없는 금액(이코테 예제) 그리디 알고리즘(Greedy Algorithm)탐욕적으로 문제를 푸는 알고리즘현재 상황에서, 탐욕적으로 좋은 것(최적해)를 선택하는 방법단순하게 탐욕적으로 최적해를 선택한다.예제 1: 거스름돈거스름돈으로 사용할 수 있는 금액은 500원, 100원, 50원, 10원짜리 동전이며 무한히 존재한다. 손님에게 거슬러줘야 할 돈이 N원일 때, 거슬러줘야 할 동전의 최소 개수를 구하라. 단, 거슬러줘야할 돈 N원은 항상 10의 배수이다. 예제의 아이디어는 '가장 큰 화폐단위부터' 탐욕적으로 선택하며 돈을 거슬러주는 것이다. 동전의 최소 개수를 구해야하므로, 가장 큰 화폐단위를 선택해야 동전의 개수를 줄일 수 있다. 가장 큰 화폐단위부터 거슬러줘야할 돈을 나눈 후, 나누어 떨어지지 않으면 작은 화폐단위로 넘어가는 것.. 2024. 10. 16.
정렬 알고리즘1: 선택 정렬(Selection Sort) 선택 정렬(Selecition Sort)데이터가 무작위로 여러 개 있을 때, 이 중 가장 작은 데이터를 맨 앞 데이터와 바꾸는 것을 반복하는 방식가장 원시적인 방법으로 매번 가장 작은 것을 선택한다는 의미에서 선택정렬 알고리즘이라고 한다.선택정렬은 매번 가장 작은 수를 찾기 위한 비교연산이 필요하므로, 시간복잡도는 O(N^2)이다.연산 횟수N + (N - 1) + (N - 2) + ... + 2N * (N + 1) / 2N^2 + N / 2O(N^2)동작 원리최솟값을 찾아 원소의 위치를 바꾼다.주의점은, 최솟값을 선택하여 앞으로 삽입하는 것이 아니라, '위치를 바꾸는 것'이다.더 작은 값을 선택하여 위치를 바꾸는 과정을 N-1번 반복하면 정렬이 완료된다.아래의 예시는 [7, 5, 9, 0, 3]을 선택정.. 2024. 9. 9.

최근댓글

최근글

skin by © 2024 ttuttak

티스토리툴바