![]()
✨ 그리디 알고리즘(Greedy algorithm)최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식 ex)백준 1715번https://www.acmicpc.net/problem/1715 import sysimport heapqsum=0hq=[]for i in range(int(sys.stdin.readline().rstrip())): heapq.heappush(hq,int(sys.stdin.readline().rstrip())) sum=0if(len(hq)==1):print(0)else: while hq: a=heapq.heappop(hq) b=heapq.heap..
✨누적 합(Prefix sum) 주어진 배열에서 각 위치까지의 합을 미리 계산하여 배열에 저장해 놓는 알고리즘 빠른응답속도 추가 메모리 사용 ex) 백준 11659번 구간 합 구하기 4 https://www.acmicpc.net/problem/11659 import sys N,M=map(int,sys.stdin.readline().rstrip().split(" ")) li=list(map(int,sys.stdin.readline().rstrip().split(" "))) li2=[0] sm=0 for i in li: sm+=i li2.append(sm) for i in range(M): a,b=map(int,sys.stdin.readline().rstrip().split(" ")) sys.stdout.w..
![]()
✨동적 계획법(dynamic programming) 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. 재귀,메모이제이션을 이용한다. ✨메모이제이션(Memoization) ‘중복 계산'을 피하기 위한 기법 이전에 계산한 값을 메모리에 저장한다. ✨탑다운방식 재귀적으로 호출함 큰문제를 작은문제로 나눔 ✨바텀업방식 반복문을 사용함 작은 문제로 큰문제를 해결함 예시) 백준 알고리즘 수업 - 피보나치 수 1 https://www.acmicpc.net/problem/24416 제귀함수로 작성한 피보나치 def fib(n): if(n
![]()
✨백트래킹(backtracking) 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법 주요 개념은 해를 얻을 때까지 모든 가능성을 시도 트리를 검사하기 위해 깊이 우선 탐색을 사용 ✨ 예시문제) 백준 N과 M(1) https://www.acmicpc.net/problem/15649 끝나는 조건:리스트의 길이가 M이 되었을때 -> 정답목록에 해당 리스트를 추가, 종료 수열의 조건: 방문했던 숫자에 다시 방문하면안됨 ->방문 리스트 V를 만들어서 체크 전체 코드 import sys def back(n,li): if(n==M): answer.append(li) #종료조건 return for j in range(1,N+1,1): if(V[j]==0): V[j]=1 back(n+1,li+..
![]()
✨ 합병정렬(merge sort) 합병 정렬은 O(n log n) 비교 기반 정렬 알고리즘이다. 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다. (분할정복:그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법) ✨ 과정(2-way 합병 정렬) 길이가 1이하임을 확인(1이하인경우 정렬완료상태) 분할: 리스트를 절반으로 나눈다. 정복:각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬 결합:두 부분 리스트를 다시 하나의 정렬된 리스트로 합병( 임시배열에 저장 ) 복사:임시 배열에 저장된 결과를 원래 배열에 복사 def merge_sort(arr): #길이 1이하확인 if(arr
![]()
✨팩토리얼(factorial) 그 수보다 작거나 같은 모든 양의 정수의 곱 python 코드 import sys n=int(sys.stdin.readline().rstrip()) su=1 for i in range(1,n+1,1): su*=i sys.stdout.write(str(su)) ✨순열(permutation) 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산 n개의 요소에서 k개를 뽑는다. itertools의 permutations코드 from itertools import permutations n=[1,2,3,4] k=2 print("개수:"+str(len(list(permutations(n,k))))) for i in permutations(n,k):print(i, end="") #결과..
✨ 유클리드 호제법(Euclidean algorithm) 유클리드 알고리즘은 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나이다. ✨과정 a,b 두개의 자연수가 있다 (a>b) a/b -> 나머지 r1 a/r1 -> 나머지 r2 3번을 반복 a/r -> 나머지 0 일때 r은 a,b의 최대공약수다. A,B=list(map(int,sys.stdin.readline().rstrip().split(" "))) if (B>A):A,B=B,A num=A r=B while True: r1=num%r if(r1==0): break num=r r=r1 print(r) 🎈참고자료 https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%9..
✨Set(집합) 1.순서가 없다.(비순차적) 2.중복이 허용되지않는다.(중복 들어갈경우 하나의 값만 저장) ✨python 집합 set A= set(list) A= {1,2,3,4} A.add(5) A.update(6,7,8) A.remove(8) A.discard(9) #KeyError 발생 안함 print(1 in A) #True print(A.pop()) #임의의 요소 하나 제거 ✨교집합(and) A & B A.intersection(B) ✨합집합(or) A | B A.union(B) ✨차집합(-) A - B A.difference(B) ✨대칭 차집합(XOR) A^B A.symmetric_difference(B) 🎈참고자료 https://data-marketing-bk.tistory.com/entry..
