프로그래밍 알고리즘 정리

선택 정렬 / 재귀 / 퀵정렬 / 해시테이블 => 이전 글에서 작성함.

너비 우선 탐색

가중치가 없는 균일 그래프에서 최단 경로를 계산하는 데 사용

• 방향 그래프 (=사이클)
• 무방향 그래프

다익스트라 알고리즘

그래프의 간선에 가중치(weight)를 준 가중 그래프(weighted graph)에서 최단 거리를 계산하는 데 사용

모든 가중치가 양수일 때만 정상적으로 동작.
음의 가중치를 가진 간선이 있으면 다익스트라 알고리즘은 사용 불가. => 벨만-포드 알고리즘을 사용해야 함.
※ 일단 어떤 정점을 처리하면 그 정점에 도달하는 더 싼 경로는 존재하지 않아야 하기 때문에

1. 가격이 가장 싼 정점, 즉 도달하는 데 시간이 가장 적게 걸리는 정점을 찾는다.
2. 이 정점의 이웃 정점에 대해 현재의 가격보다 더 싼 경로가 존재하는지 확인한다. 만약 존재한다면 가격을 수정한다.
3. 그래프 상의 모든 정점에 대해 이러한 일을 반복한다. (가격 테이블 작성)
4. 최종 경로를 계산한다. (목적지 정점부터 시작해서 가격 테이블의 부모 열을 역행)

• 가중치(weight)
• 가중 그래프(weighted graph)
• 균일 그래프(unweighted graph)
• 사이클(cycle) : 그래프가 어떤 정점에서 출발해서 한 바퀴를 돌아 같은 정점에서 끝나는 것. (=최단경로 불가능)
  ※ 다익스트라 알고리즘은 방향성 비순환 그래프(DAG, Directed Acyclic Graph) 또는 사이클을 가진 경우에는 가중치가 양수일 때만 적용됨.

[Python]

#아직 처리하지 않은 가장 싼 정점을 반환
def find_lowest_cost_node(costs):
	lowest_cost = float("inf")
	lowest_cost_node = None
	for node in costs:
		cost = costs[node]
		if cost < lowest_cost and node not in processed:
			lowest_cost = cost
			lowest_cost_node = node
	return lowest_cost_node

#그래프
graph = {}
graph["start"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2

graph["a"] = {}
graph["a"]["fin"] = 1

graph["b"] = {}
graph["b"]["a"] = 3
graph["b"]["fin"] = 5

graph["fin"] = {}

#가격
infinity = float("inf");
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["fin"] = infinity

#부모
parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["fin"] = None

#처리한 정점 추적
processed = []

node = find_lowest_cost_node(costs)
while node is not None:
	cost = costs[node]
	neighbors = graph[node]
	for n in neighbors.keys():
		new_cost = cost + neighbors[n]
		if costs[n] > new_cost:
			costs[n] = new_cost
			parents[n] = node
	processed.append(node)
	node = find_lowest_cost_node(costs)

print (parents)
print (costs)

#실행결과
{'a': 'b', 'b': 'start', 'fin': 'a'}
{'a': 5, 'b': 2, 'fin': 6}

탐욕 알고리즘

각 단계에서 최적의 수를 탐색한다. 간단한 구현으로 (완벽하지는 않으나) 정답에 가까운 답을 얻고자 할 때 사용

근사 알고리즘

정확한 답을 계산하는 데 시간이 너무 많이 걸릴 때 빠르게 최적해를 찾는 알고리즘

[Python] - 집합 커버링 문제(set-covering problem)

#방송해야 하는 주 집합
states_needed = set(["mt", "wa", "or", "id", "nv", "ut", "ca", "az"])

#방송국 목록
stations = {}
stations["kone"] = set(["id", "nv", "ut"])
stations["ktwo"] = set(["wa", "id", "mt"])
stations["kthree"] = set(["or", "nv", "ca"])
stations["kfour"] = set(["nv", "ut"])
stations["kfive"] = set(["ca", "az"])

#방문할 방속국 목록
final_stations = set()

#가장 넓은 주를 커버하는 최적의 방송국 찾기
while states_needed:
	best_station = None
	states_covered = set()
	for station, states in stations.items():
		covered = states_needed & states  #교집합
		if len(covered) > len(states_covered):
			best_station = station
			states_covered = covered
	
	states_needed -= states_covered   #방송한 주 제거
	final_stations.add(best_station)  #방문 방송국 추가

print (final_stations)

#실행결과
{'kone', 'ktwo', 'kthree', 'kfive'}

• NP-완전 문제
  모든 가능한 경우를 다 따져서 최단/최소를 구해야 하는 문제.
  빠른 해답이 알려지지 않았기 때문에, NP-완전 문제에서는 근사 알고리즘은 쓰는 것이 최선.
  (ex: 집합 커버링 문제, 외판원 문제)
  
  
• 외판원 문제
  들려야 할 도시의 수가 n개일 경우, (출발 가능한 도시 개수 n * 출발 가능한 도시가 n-1개일 경우의 경로)
  이전의 연산 결과에 도시의 개수(n)을 곱하는 팩토리얼 함수 형태. (=재귀)
  +) 외판원 문제의 근사화
     일단 아무 출발 도시를 선택한 후, 아직 방문하지 않은 가장 가까운 도시를 다음 방문지로 선택.
     완벽한 최단 거리는 아닐지 모르지만, 짧든 시간에 최선의 해를 찾을 수 있음.

동적 프로그래밍

큰 문제를 작은 하위 문제로 나누어 푸는 방법. (하위 문제 풀이 결과를 이용해 큰 문제를 풀이)
제한 조건이 있는 경우에 무언가를 최적화할 때 유용

• 동적 프로그래밍을 풀 때는 격자(grid)를 사용
• 격자의 각 칸에는 최적화하고자 하는 값을 기재  (=각 칸은 원래 문제의 하위 문제)
• 행이 새로 추가, 행의 순서 변경, 실수 단위 계산 가능
• 하위 문제가 서로 의존하지 않는 경우에만 사용 가능
• 배낭 채우기 문제, *cell[i][j]의 최대값 = 1. 지금까지 구한 cell[i-1][j]의 값 중에서 가장 최대값
                                                    2. 현재 물건의 가치 + 남은 공간의 가치
• 여행 일정 최적화 문제
• 최장 공통 부분 문자열(LCS, Longest Common Substring) : 두 단어에서 공통적으로 가지는 가장 긴 문자열.
• 최장 공통 부분열(Logest Common Subsqeunce) : 두 단어에서 순서가 바뀌지 않고 공통으로 들어간 글자
  = 검색어에 오타가 있을 때 무슨 단어를 찾으려 했는지, 문자열의 유사성 측정
  ex) 생명과학 분야 DNA 가닥 유사점 탐색, 레벤슈타인의 거리(Levenshtein distance)

#최장 공통 부분 문자열
if word_a[i] == word_b[j]:
	cell[i][j] = cell[i-1][j-1] + 1
else :
	cell[i][j] = 0
    
#최장 공통 부분열
if word_a[i] == word_b[j]:
	cell[i][j] = cell[i-1][j-1] + 1
else :
	cell[i][j] = max(cell[i-1][j], cell[i][j-1])

KNN 알고리즘

K-nearest neighbors Algorithm, k개의 가장 가까운 이웃 데이터를 이용하여 분류와 회귀 분석을 수행
기준 데이터와 이웃 데이터 사이의 거리를 계산해서 유사도(similarity) 파악. *좌표가 있어서 거리 계산 가능

• 분류 : 그룹으로 나누는 작업
• 회귀 : 숫자로 된 반응을 예측
• 두 점 사이의 거리 : 두 숫자 집합의 유사도, 두 대상이 얼마나 비슷한가
  1. 피타고라스 정리 = 두 벡터 사이의 거리
  2. 코사인 유사도 =  두 벡터 사이의 각도
• 특징 추출
  1. 여러가지 데이터를 살펴본 뒤 해당 데이터의 특징을 뽑아낸다.
  2. 새로운 데이터가 주어지면 그 데이터의 특징을 뽑아서 가장 가까운 것들을 살펴본다.
• ex) 넷플릭스 콘텐츠 추천 시스템(콘텐츠 평점 내역이 비슷한 고객의 데이터 이용), 해당 고객의 평점 예측
       광학적 문자 인식(OCR, Optical Character Recognition), 음성 인식, 얼굴 인식 등 머신러닝 분야.
• ex) 나이브 베이즈 분류기(Naive Bayes Classifier) = 스팸 필터
      메일 제목을 단어로 쪼갠 뒤, 각 단어마다 그 단어가 스팸메일에 나타날 확률을 계산
• 데이터에서 선택한 이웃의 수가 적으면 적을수록 결과가 왜곡될 수 있다.
• 보통 N개의 데이터가 있을 때, sqrt(N)개의 이웃을 설정한다. (*sqrt :제곱근)
• KNN을 사용할 때 중요 데이터에 가중치를 더 많이 줄 수 있다.

이진 탐색 트리

• B-트리(B-tree) : 데이터베이스에서 데이터를 저장하는 데 주로 사용
• 레드-블랙 트리(red-black tree) : 스스로 트리의 균형을 맞춤
• 힙(heaps)
• 스플레이 트리(splay tree)

역 인덱스

사용자가 입력한 검색어(key)가 포함된 웹 페이지(value)를 해시테이블에서 찾아 반환하는 방식의 검색 엔진에 사용.

퓨리에 변환

하나의 노래를 여러 개의 개별적인 주파수들로 분리, 저음/고음 조정 가능 = 신호처리에 특화됨
음향 파일을 개별 음파로 분리한 다음 각 음파에 전체 노래에 어느 정도 기여하는지를 계산해서 별로 중요하지 않은 음파는 제거하는 식으로 음악 압축 가능(.mp3), 다양한 파일 압축
지금 나오는 음악이 어떤 음악인지 알아 맞추는 앱

병렬 알고리즘

여러 개의 코어에서 동시에 돌아가도록 병렬 실행

• 병렬화를 관리하는 데 들어가는 부담 : 각 코어에서 분담해서 처리한 작업결과를 하나로 합치는 부담
• 로드 밸런싱 : 각각의 코어의 작업량 및 작업시간이 비슷하도록 균등하게 작업 분배

맵리듀스 알고리즘

여러 대의 컴포터에서 돌아가는 분산 알고리즘의 일종. 아파치 하둡과 같은 오픈 소스 툴을 통해 사용할 수 있다.
맵 함수, 리듀스 함수 두 개념을 이용해서 여러 대의 컴퓨터에 분산되어 있는 데이터에 대한 질의를 수행.
ex) 데이터가 수입억 개의 레코드(대용량 데이터)로 이루어져 있는 데이터베이스에서의 SQL 질의

• 맵 함수(map function)
  : 배열을 입력으로 받아서 모든 원소에 같은 함수를 적용하는 것.
  

  arr1 = [1, 2, 3, 4, 5]
  arr2 = map(lambda x: 2*x, arr1)
  
  #실행결과
  [2, 4, 6, 8, 10]

  
  ex) 일련의 URL을 배열로 입력 받은 뒤 각 페이지를 다운로드해서 그 내용을 새로운 배열에 저장
       맵 삼수에서 이 작업을 모든 컴퓨터에 골고루 분배하여 분산 작업.
  
  
• 리듀스 함수(reduce function)
  : 리스트 전체의 원소를 하나의 원소로 축소하는 것.

  arr1 = [1, 2, 3, 4, 5] 
  reduce(lambda x, y: x+y, arr1)
  
  #실행결과
  15

블룸 필터

확률론적인 자료구조로 매번 옳은 답을 주지는 않는다.
새로운 항목이 들어오면 이 항목이 집합에 이미 있는지, 없는지를 확인하고자 할 때 사용

• 틀린 답을 맞다고 할 수도 있다. = 악성코드가 없지만, 이 사이트는 악성코드가 있을 수도 있다고 판단. (O)
• 다만, 맞는 답을 틀리다고 하지는 않는다. = 악성코드가 있지만, 이 사이트는 악성코드가 없다고 판단 (X)
• 해시테이블에 비해 저장 공간을 적게 차지함.
• ex) 악성 웹 사이트 주소 목록 체크, 웹 페이지 크롤링 여부 체크 등..

하이퍼로그로그

집합에 있는 똑같은 원소의 개수를 대략적으로 카운트할 수 있다. (=확률론적 방법)
정확한 값을 주지는 않지만, 정확한 값을 주기 위해 필요한 메모리의 아주 일부분만 사용해서 근사값을 산출해냄.

SHA알고리즘

SHA(Secure Hash Algorithm : 보안 해시 알고리즘)

• 해시 테이블용 해시함수 : 문자열(key)을 받아 배열 인덱스(숫자)를 출력
• SHA 함수 : 문자열을 받아서 그 문자열에 대한 해시값(문자열)을 출력 
  • 단방향 해시, 문자열에서 해시값을 얻을 수 있지만, 해시값에서 문자열을 얻을 수 없음
  • 파일 비교 - 두 파일에 대한 SHA 해시값을 비교하여 두 파일이 같은 파일인지 체크
  • 패스워드 확인 - 패스워드에 대한 SHA해시값만 저장해두고 비교 (=문자열을 밝히지 않고 두 문자열을 비교)
  • SHA-0, SHA-1, SHA-2, SHA-3 / 현 패스워드 해시함수 표준 : bcrypt

지역 민감 해싱

• 지역 민감적 : 두 개의 입력 문자열이 비슷하면 출력되는 해시값도 비슷해진다.
  지역 민감적이지 않으면 기존 문자열에서 한 글자만 바꾸어 다시 해시값을 생성하면 완전히 다른 값이 출력됨.
• Simhash : 지역 민감 해싱, 문자열이 조금 바뀌면 해시값도 조금 바뀌기 때문에 비슷한 항목을 찾아낼 때 사용.
  
  • 논문 및 레포트 표절 검사, 웹 사이트 중복 체크, 저작물 검사 등

디피-헬만 키 교환

• 공개키(public key)를 이용해서 암호화한 파일은 개인키(private key)를 이용해 해독 가능.

선형 프로그래밍

주어진 제한 조건하에서 무언가를 최대화할 때 사용 (ex: 정해진 시간, 예산 등으로 최대의 수익을 창출)

• 심플렉스 알고리즘(Simplex algorithm)

---

출처 : Hello Coding 그림으로 개념을 이해하는 알고리즘 / 야디트야 바르가바 / 한빛미디어