미새문지

가장 긴 부분수열 수열 A가 입력되면 가장 긴 증가하는 부분 수열 구하기 import sys input = sys.stdin.readline def longLCS(a): # 받은 문자열의 길이를 체크 length = len(a) # 처음 시작을 1로 해야 원소가 처음 나올때 1이 체크된다. list = [1]*length # 처음껀 비교대상이 없기 때문에 1부터 시작 for i in range(1, length): # i 이전 수들끼리 비교해야 하기 때문에 i까지 반복 for j in range(i): # i값이 j값보다 크고(증가 수열) 리스트에 i를 넣었을 때 기존 리스트보다 길면 갱신 if a[i] > a[j] and list[i] < list[j]+1: list[i] = list[j]+1 # 리스..

스택과 레지스터의 용도와 장점 스택 프로시저 호출 시 지역 변수와 매개변수를 저장하기 위한 메모리 공간이며, LIFO(Last in First Out)이라는 마지막에 들어온 값이 먼저 나가는 구조를 가지고 있다. 용도 함수의 로컬 변수 저장 : 각 함수 호출 시 그 함수의 로컬 변수들이 스택에 저장된다. 함수의 제어 흐름 관리 : 함수가 다른 함수를 호출할 때, 반환 주소와 이전 함수의 스택 프레임 정보가 스택에 저장된다. 장점 동적으로 메모리를 할당하고 해제할 수 있다. 구현이 간단하며, 메모리 관리의 오버헤드가 낮다. 레지스터 프로세서 내부의 고속 작동 메모리로, 프로시저 실행 중 자주 접근하는 변수나 중간 계산값을 저장하기 위해 사용 용도 중간 연산 결과 저장 : 연산 중 생성되는 중간 값을 빠르게..

피보나치2 피보나치를 재귀방식이 아닌 DP방식으로 풀기(동적 프로그래밍) import sys def fibo(n): list = [0, 1] + [0]*(n-1) for i in range(2, n+1): list[i] = list[i-1] + list[i-2] return list[n] n = int(sys.stdin.readline()) print(fibo(n)) 01타일 1또는 00만을 이용해서 n개의 타일을 깔수있는 경우의 수를 구하기(동적 프로그래밍) import sys n = int(sys.stdin.readline()) pibo = [0, 1] m1 = 0 m2 = 0 i = 0 while i != n: m1 = pibo[0] + pibo[1] m2 = pibo[1] pibo[0] = m2 ..

그리디 알고리즘(Greedy algorithm) - 탐욕법 가장 직관적인 형태의 알고리즘이며, 눈 앞에 보이는 최적의 상황만을 쫓는 알고리즘이다. 항상 최적의 결과를 뽑지는 못하지만, 확률 상 최적의 결과에 근사한 값을 빠르게 구할 수 있다. 즉, 특정한 상황에서 최적의 해를 보장하는 극한의 효율충 알고리즘 효율충인만큼 자원에 접근할 때 무조건 큰 경우, 긴 경우 등의 조건으로 문제를 극단적으로 접근하기 때문에 정렬 기법이 함께 사용되는 경우가 많다. 예시는 크루스칼 알고리즘으로 '모든 간선을 정렬한 이후에 짧은 간선으로 연결하는' 최소 신장 트리 알고리즘이 있다. 예시 문제로 일정 금액을 동전을 사용하여 낼 때 최소한의 개수로 낼 수 있는지 확인하는 문제 import sys # 금액을 입력받고 n = ..