프로그램 : 자료구조 + 알고리즘 자료구조 : 접근 or 수정이 용이하도록 자료를 저장하거나 구성하는 방법을 말한다list stackQueueTreeGraph알고리즘이 성립되기위한 조건알고리즘이 유한시간 내에 종료되어야함알고리즘이 올바른 출력을 낼 수 있어야 함 알고리
빅오 표기법 연산 횟수를 대략적(점근적)으로 표기한 것으로 함수의 상한을 의미함 두 개의 함수 f(n)과 g(n)이 주어졌을 때, 모든 n≥n0에 대하여 |f(n)| ≤ c|g(n)|을 만족하는 2개의 상수 c와 n0가 존재하면 f(n) = O(g(n)) 이다.
막대기를 기준으로 왼쪽의 데이터는 이미 정렬되어있다고 가정막대기를 기준으로 오른쪽의 제일 처음 데이터가 추가되었을때 왼쪽의 데이터들중 어디에 삽입되는 것이 가장 적당한 것인지를 비교추가된 데이터는 막대기를 기준으로 왼쪽의 데이터들 중 가장 오른쪽 부터 비교해가면서 필요
합병 정렬 원소의 개수가 1개가 될때까지 분할한다 이후 병합을 시작하는데 병합을 분할의 역순이다. 합병 정렬 과정중 분할 과정을 나타낸 것이다. 재귀함수로 구성되어있고, 원소의 개수가 1이되는 지점 즉, if문이 거짓이 되는 지점에서 종료된다. 합병 정렬 과정중
계수정렬 이전의 대소를 비교하여 정렬했던 방법과는 다른 분포기반 정렬 방식이다. 특정 조건만 만족한다면 더 효율적인 알고리즘이 될 수 있다. 영문알파벳 또한 26개이기 때문에 1~26으로 키값을 정해서 계수정렬을 할 수 있다. A에서 배열이 정의되었다. N에서 각 수
외부정렬 양방향 합병정렬
앞서 배운 이진탐색은 사전에 이미 정렬되어 있음을 가정하였다.그렇다면 만약 정렬되지 않은 데이터에 대해서는 어떻게 이진탐색을 할 수 있을까? 만약 정렬을 먼저 수행한 뒤 이진탐색을 하면 효율이 높은 이진탐색에 비해 정렬의 효율이 낮아 효과적인 방법이 아니다.\-> 이것
입력: 선분 AB, 선분 CD (4개의 점 A,B,C,D)방법: A,B와 C,D 각 두 점으로부터 두 직선의 방정식을 찾고, 두 직선의 방정식으로부터 교점의 좌표를 찾는다. 그 뒤 교점이 선분 AB 또는 선분 CD에 포함되어 있는지를 확인많은 단계의 계산들이 필요해 비
알고리즘이나 함수가 수행 도중에 자기 자신을 다시 호출하여 문제를 해결하는 기법 정의 자체가 순환적으로 되어 있는 경우에 적합대표적으로 팩토리얼 값 구하기와 피보나치 수열 문제가 있다.팩토리얼 프로그래밍 (n-1)! 팩토리얼을 현재 작성중인 함수를 다시 호출하여 계산순
주어진 문제의 입력을 분할해 문제를 해결하는 기법예시 : 아주 많은 동전 더미 속에 1개의 가짜 동전이 섞여 있다. 이 가짜 동전은 매우 정교하게 만들어져 누구도 눈으로 가짜인지를 식별할 수 는 없지만, 무게가 정상적인 동전보다 약간 가볍다. 1개의 양팔 저울만을 사용
DP 활용 편집 거리 문제 삽입 ,삭제 ,대체 연산을 사용하여 스트링(문자열) S를 수정하여 다른 스트링 T로 변환하고자 할 때 필요한 최소의 편집 연산 횟수 strong -> stone DP의 일반항, E[i,j] = S의 처음 i개 문자를 T의 처음 j개
그래프 알고리즘 그래프 정점(Vertex) , 간선(Edge) , 가중치(Weight) 총 세가지 정보가 필요하다 무향 그래프 : 방향이 존재하지 않는다. 정점간 가중치가 없으며, 양방향이다 유향 그래프 : 단방향이거나, 가중치가 다른 양방향 그래프
BFS 탐색 순서 : 1->2,3->4,5,6->7,8->9->10,11->12,13 별도의 시작노드가 주어져야 한다. BFS(G,s) # G는 그래프, s는 시작 정점 for v -> V visited[v] = False
목적지까지 최단 경로를 찾기 위한 알고리즘이다. 가중치가 있는 유향 그래프까지 가능 Heuristic 함수를 이용하는 것이 특징이다.\-> 출발 지점에서 인접한 부분까지의 거리와 인접한 부분으로부터 목적지까지 거리(추정치)를 구한다.\-> 정확하지 않더라도 대충의 추정