시간 날 때, 끄적끄적

그래프와 탐색 알고리즘 그래프는 대상들의 관계를 나타낼 때 적합한 자료구조로 대상 나타내는 node 또는 vertex들과 그들의 연결 관계를 나타내는 Edge로 표현할 수 있다. 그래프는 edge가 탐색할 수 있는 방향의 존재 여부와 가중치의 여부에 따라 크게 네 가지 종류로 구분할 수 있다. 무향 그래프 : edge의 방향이 없는 그래프 유향 그래프 : edge에 방향이 있는 그래프 가중치 무향 그래프 : edge에 방향은 없으나 가중치가 있는 그래프 가중치 유향 그래프 : edge에 방향과 가중치가 있는 그래프 행렬의 행은 출발하는 node의 숫자, 열을 도착하는 node의 숫자로 그래프를 표현할 수 있다. 아래의 예는 유향 그래프를 행렬로 표현한 것을 나타낸 예시이다. 1번 node는 2와 3으로 ..

다이나믹 프로그래밍이란 dynamic programming은 최적의 답을 찾기 위한 수학적인 개념으로 복잡한 문제를 간단한 문제의 sequence로 변형해 풀이하는 divide and conquer 최적화 방법 중 하나이다. divide and conquer 방법의 단점은 동일한 계산을 반복해서 수행해야하는 단점이 있는데 중간 계산 결과를 저장해 한 번만 계산하도록 하는 memoization으로 이 문제를 극복합니다. dynamic programming을 적용할 수 있는 문제는 '최적성 원리'가 성립하는 문제다. 최적성의 원리는 문제 전체의 최적해가 작은 부분의 최적해로 구성될 때 성립한다. 이 경우 문제를 점화식 형태로 구성해 풀이한다. 피보나치 수열 피보나치 수열은 첫 두 항이 1로 시작하고, 연속된..

자료구조 자료구조는 자료들의 집합을 체계적이고 효율적으로 관리하기 위한 형식 자료구조는 자료 집합, 규칙, 조작으로 개념을 나누어 이해하는 것이 좋다. 자료 집합 : 대상이 되는 자료의 본체를 의미함. 배열, 구조체 등 자료를 저장할 수 있는 본체 규칙 : 자료 집합을 조작, 관리, 유지하기 위해 정한 규칙 조작 : 자료 집합에 직접 적용하는 처리를 의미함 stack, queue, linked list, tree 등 다양한 종류의 자료구조가 존재하고 필요와 목적에 따라 적합한 자료구조를 선택해 사용한다. Queue Queue는 C의 array나 python의 list를 자료집합으로 사용할 수 있다. python에는 collections 라이브러리에 dequeue type을 사용하면 queue를 쉽게 구현..