본문 바로가기

What would life be If we had no courage to attemp anything?

Problem Solving/ALGORITHM7

에라토스테네스의 체 (소수 구하기) #에라토스테네스의 체 (소수 구하기) #소수 - 1과 자기 자신만으로 나눌 수 있는 수 #입력 받은 후 입력받은 숫자가 소수인지 아닌지 출력! #힌트 2부터 자기자신 -1 까지 나누었을 때 나머지가 0이면 안됨 #입력값을 받아 소수인지 판별하시오. #내 코드 n = int(input()) for i in range(2,n): if n%i ==0: print('소수 안됨') break else: print('소수 됨') #입력 50 #출력 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 #에라토스테네스의 체 (소수 구하기) #소수 - 1과 자기 자신만으로 나눌 수 있는 수 #입력 받은 후 입력받은 범위까지의 소수를 찾기 a = int(input()) answer=[] check=[.. 2022. 6. 1.

유클리드 호제법 (최대공약수), 최소공배수 유클리드 호제법 의미: 최초의 알고리즘 유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. (출처:wikipedia) 최대공약수 구하기 1. a,b 각각의 약수를 구해 공통되는 약수 중 가장 큰 값 찾기 2. 유클리드 호제법 숫자 a,b가 존재할 때, a를 b로 나눈 나머지와 b의 최대 공약수는 a와 b의 최대공약수가 같음. 따라서, 계속해서 a를 b로 나누어 b를 a에, 나눈 나머지를 b에 대입시켜 b가 0이 될 때까지 반복하면 남는 a값이 최대 공약수가 된다! def gcd(a,b): while b>0: a,b = b,a%b return a 최소공배수 서로 다른 수 a,b의 배수중에서 공통.. 2022. 6. 1.

deque deque 데크(deque)의 개념 - 보통의 큐(queue)는 선입선출(FIFO)로 작동 - deque는 양방향큐! - 앞, 뒤 양쪽 방향에서 element를 추가하거나 제거 가능 - 데크는 양 끝 element의 append와 pop이 압도적으로 빠름 - 컨테이너의 양끝 element에 접근해 삽입 또는 제거를 할 경우, 일반적인 리스트(list)가 이러한 연산에 O(n)이 소요되는데 반해, 데크(deque)는 O(1)로 접근 가능 데크(deque) 사용법 - deque는 import해서 사용해야한다! from collectinos import deque deq = deque() #item을 데크의 왼쪽 끝에 삽입 deq.appendleft(item) #item을 데크의 오른쪽 끝에 삽입 deq.ap.. 2022. 5. 31.

그리디 알고리즘(Greedy Algorithm) 그리디(Greedy) 알고리즘 🎈개념 - 탐욕 알고리즘이라고 불리며, 여러 경우 중 하나를 결정해야 할 때 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 방법 - 그리디 알고리즘은 최적 해를 구하는데 사용되는 근시안적인 방법 - 각 선택의 시점에서 이루어지는 결정은 지역적으로는 최적이지만, 그 선택들을 통해 최종적인 해답을 만들었다고 해서 그것이 최적이라는 보장이 없는 계획법 🎈그리디 알고리즘의 조건 탐욕스러운 선택 조건 - 탐욕적인 선택은 항상 안전하다는 것이 보장되어야 함. "안전하다"라는 의미는 이 선택으로 인해 전체 문제의 최적해를 반드시 도출할 수 있어야 한다는 것. 그리디 알고리즘을 사용해 결과 도출 시 최적해가 무조건 나오나? - 그리디 알고리즘.. 2022. 5. 13.

순열/가지치기 #back tracking #처음에 2가 나오면 안되는 경우 만들기 n = int(input()) arr = [1,2,3,4,5,6] path=['']*n used=[0]*6 def abc(level): if path[0] == 2: return #back tracking if level == n: for i in range(n): print(path[i],end=' ') print() return for i in range(6): # if level == 0 and arr[i] == 2: # continue path[level] = arr[i] abc(level+1) path[level]=0 abc(0) #back tracking n = int(input()) arr = [1,2,3,4,5,6] pa.. 2022. 3. 15.

브루트포스 알고리즘 (완전 탐색 알고리즘) 브루트포스 알고리즘 Brute(무식한) + Force(힘) 브루트 포스는 완전 탐색 알고리즘으로, 가능한 모든 경우의 수를 탐색하고 조건에 충족되는 결과만을 가져옴! 무식하게 모든 경우를 탐색하기 때문에 100% 확률로 정답을 출력. 알고리즘이 기본적으로 해가 존재할 것으로 예상되는 범위를 탐색하기 때문에, 설계시 '해가 하나 이상 존재한다'는 가정을 세우고 모든 범위를 탐색! but, 시간이 오래 걸림! 브루트 포스의 종류 선형구조 순차탐색 비선형구조 BFS(넓이 우선 탐색),DFS(깊이 우선 탐색) 순차탐색 1) 주어진 문제를 구조화 2) 구조화된 공간을 적절한 방법으로 해를 찾을 때 까지 탐색 BFS,DFS 두 가지 모두 그래프를 탐색하는 방법! 그래프란? node(정점)과 그 정점을 연결하는 ed.. 2022. 3. 11.

DAT, Count Sorting # practice 1 a = [4, 9, 1, 4, 4, 2] b = [1, 3, 4, 2, 5, 6, 7, 8, 9] for i in range(len(b)): c = 0 for j in range(len(a)): if a[j] == b[i]: c = 1 break if c == 1: print('O',end=' ') else: print('X',end=' ') # practice 2 -DAT a = [4, 9, 1, 4, 4, 2] b = [1, 3, 4, 2, 5, 6, 7, 8, 9] bucket = [0]*20 # O,X를 담을 바구니 for i in range(len(a)): # a에 있는 애들을 먼저 바구니에 체크 해주기 index = a[i] # 여기의 index는 바구니의 index 번.. 2022. 2. 10.

이전 1 다음

티스토리툴바