문미새 개발일지

동적 계획법(Dynamic Programming) 복잡한 문제를 간단한 여러 개의 하위 문제로 분해하여 해결하는 알고리즘 설계 기법 큰 문제를 작은 문제로 나누어 해결하는 분할 정복과 비슷하지만, 다이나믹 프로그래밍은 각 하위 문제들이 서로 연관되어 있고, 작은 문제들의 해결을 통해 전체 문제를 해결한다. 동일한 하위 문제를 반복적으로 해결해야 할 경우, 해결 결과를 메모리에 저장해두고 이를 재사용함으로써 중복 계산을 피해 연산 시간을 단축시키는 것을 메모이제이션(Memoization)이라고 한다. 사용을 위한 두 가지 조건 중복 하위 문제 구조(Overlapping Subproblems) 큰 문제와 작은 문제를 같은 방법으로 해결할 수 있으며, 작은 문제의 답을 메모리에 저장하고 필요할 때마다 활용한다..

컴퓨터는 메모리를 관리하고 데이터 처리하는 등의 하위 동작들을 인코딩한 연속된 바이트인 기계어 코드를 실행한다. 컴파일러는 프로그램 언어의 규칙, 운영체제의 관례 등에 따라 기계어 코드를 생성한다. GCC C 컴파일러는 기계어 코드를 문자로 표시한 어셈블리 코드의 형태로 출력을 만들어 프로그램의 각 인스트럭션을 만들어 낸다. 그리고 어셈블러와 링커를 호출하여 어셈블리 코드로부터 실행 가능한 기계어 코드를 생성한다. 컴파일러는 전체 컴파일 순서에서 C에서 제공하는 추상화된 실행모델로 표현된 프로그램을 프로세서가 실행하는 매우 기초적인 인스트럭션들로 변환하는 대부분의 일을 수행한다. 기계어 코드 파일의 내용을 조사하려면, 역어셈블러라고 하는 프로그램이 매우 중요해진다. 역어셈블러는 기계어 코드 파일의 바이트..

LCS(Longest Common Subsequence) 공통 부분 문자열 중 가장 길이가 긴 문자열을 말하는 ‘최장 공통 부분 수열’이라고 한다. LCS는 최장 공통 문자열이라고도 불리는데 그 차이는 최장 공통 부분 수열은 문자열 안의 공통된 문자를 다 구한다 최장 공통 문자열은 문자열 안의 공통된 문자 중 연속된 문자를 구한다. 다이나믹 프로그래밍(DP)방식으로 구현된다. ​ LCS - Substring(최장 공통 문자열) 두 문자열을 비교하는 표인데 이 때, 반드시 두 문자열의 가장 앞 칸은 0으로 해야 한다. 만약 두 문자열 중 어느 것이라도 첫 번째 문자가 일치하면 그 좌표의 -1 좌표에서 값을 참조해야 하는데 [0, 0]이면 앞 칸이기 때문에 음수로 참조하게 되고 에러가 발생한다. 최장 공통 ..

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

위상정렬 알고리즘 줄 세우기 문제를 풀기 위해 학습했던 알고리즘 from collections import deque # 위상정렬 알고리즘(꼭짓점, 간선정보 매개체) def topological_sort(vertices, edges): # 각 꼭짓점에서 다른 꼭짓점으로의 간선정보를 저장할 인접리스트 만들기 # 함수를 사용할 때마다 새롭게 작성해야하므로 함수 내부에 작성 # 0은 무시하고 1부터시작해야하기 때문에 +1로 맞춤 adj = [[] for _ in range(vertices + 1)] # 꼭짓점으로 들어오는 간선의 수를 저장할 리스트 # 0은 무시하고 1부터시작해야하기 때문에 +1로 맞춤 indegree = [0] * (vertices + 1) # 간선 정보를 돌리면서 for edge in ed..

캐시 메모리를 사용하면 컴퓨터 시스템의 성능이 왜 향상될까 지역성(locality)은 프로그램이 메모리를 접근할 때 특정 부분을 집중적으로 사용하는 경향을 나타낸다. 시간적 지역성(Temporal Locality) 한 번 접근된 데이터는 가까운 미래에 다시 접근될 가능성이 높다는 원리 ex) 루프 내에서 반복적으로 사용되는 변수 공간적 지역성(Spatial Locality) 메모리의 특정 주소에 접근한 후, 그 주변 주소에 있는 데이터에 접근될 가능성이 높다는 원리 ex) 배열이나 연속적인 메모리 블록에 접근할 때 캐시 메모리는 이러한 지역성 원리를 활용해 자주 사용되거나 연속적으로 사용될 가능성이 높은 데이터를 미리 캐시에 저장하여 CPU는 필요한 데이터를 캐시에서 빠르게 찾을 수 있다. ​ 프로세스(..

힙(heap) 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 하는 자료구조 특징 a가 b의 부모노드면 a의 키값과 b의 키값 사이에는 대소 관계가 성립한다. 최소 힙 : 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙 최대 힙 : 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙 ​ 힙 자료구조 파이썬 힙 모듈은 heapq라는 알고리즘 라이브러리를 제공 내장 모듈이기 때문에 설치할 필요없이 사용가능 모든 부모 노드는 자식 노드보다 값이 작거나 큰 이진 트리 구조인데, 내부적으로는 인덱스 0에서 시작해 n번 째 원소가 항상 자식 원소들보다(2n+1, 2n+2)보다 작거나 최소 힙의 형태로 정렬 기능 heapq.heappush(heap, item) : item을 h..

sys 모듈 파이썬에서 제공하는 표준 라이브러리로 시스템과 관련된 각종 정보들을 제공하는 모듈이다. 몇 가지 기능들 sys.argv 파이썬을 실행하면서 입력된 값을 전달받아 활용할 수 있다. argv를 출력하면 입력된 값을 list형태로 저장하고 있고, 첫번째 배열 값은 항상 실행하는 파일의 이름이다. 그래서 입력된 값은 argv[0]이 아닌 argv[1]부터 시작한다. sys.path 파이썬이 설치되어 있는 경로 및 라이브러리들의 경로를 리스트에 모두 저장하고 있는 변수이다. 이 리스트에 경로를 추가해 파이썬 파일들을 import문으로 불러올 수 있다. sys.executable 현재 실행하고 있는 파이썬 실행파일의 절대경로를 알아낼 수 있다. 실행파일의 경로를 알아내야 할 때 사용 sys.platfo..