Jin's Study

- Back Tracking(되돌아가며 풀어보기)백트래킹 알고리즘 : 해를 찾는 과정에서 해를 더 이상 얻지 못하면 바로 직전 상태로 되돌아가서 다른 것을 시도하며 해를 찾는다.백트래킹 알고리즘은 최적화 문제와 결정 문제를 해결결정 문제 : 문제에 대한 해의 존재 여부(즉, 해가 '있다' 또는 '없다')를 답하는 문제백트래킹은 해 탐색 순서가 깊이 우선(Depth First)으로 수행분기 한정(Branch-and-Bound) 알고리즘 - 한정 값(bound)을 이용하여 한정 값이 가장 좋은 것 부터 최선 우선(Best First)탐색하는 방식으로 탐색 범위를 상당히 줄여서 해를 찾는다. - M-coloring 백트래킹 알고리즘인접한 영역을 서로 다른 색으로 칠하는 지도 색칠지도를 Graph를 활용하여 보..

- 동적 계획법(Dynamic Programming)동적 계획법은 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법이다.문제를 작은 것부터 풀어본다는 것은 작은 문제들을 먼저 풀어서 그 해를 이용하여 문제를 해결하는 것이다.작은 문제란 원래 주어진 문제와 같은 문제이며, 작은 문제를 부분 문제라고 한다. 작은 문제의 입력은 원래 문제의 입력의 일부분이다.- 대표적인 DP문제가장 긴 증가 순서서열 정렬합이 최대 K 되는 숫자배낭문제 - 가장 긴 증가 순서숫자가 일렬로 나열되었을 때 가장 긴 증가 순서(Longest Increasion Subsequence)를 찾는다.증가 순서는 숫자들이 반드시 이웃해야만 하는 것은 아니다.일렬로 주어진 숫자들로 만든 그래프에서 어떻게 가장 긴 경로를 ..

- 욕심내어 풀어보기그리디 알고리즘이란?최적화(Optimization) 문제 : 최솟값(또는 최댓값)을 찾는 문제욕심내어 해결하는 것 : 알고리즘이 수행하는 과정에서 항상 가장 작은것(또는 문제에 따라서 가장 큰 것)을 선택하는 방식으로 문제의 해를 계산하는 것그리디 알고리즘은 문제의 해를 계산하는 과정에서 항상 '욕심내어' 해를 선택하고 이렇게 선택한 해를 모아서(축적하여) 최종적인 해를 찾는 알고리즘이다. - 태스크 스케줄링일반적인 태스크 스케줄링(Task Scheduling) : 각 태스트가 시작과 종료 시각을 가질 때, 태스크를 처리할 프로세서에 수행 시간이 겹치지 않게 태스크들을 할당하는 문제- 구간 스케줄링Interval Scheduling예를 들어 대학교에서 동아리들이 중앙도서관의 미팅룸을 ..

- 나누어 풀어보기선택 정렬(Selection sort) : 가장 작은 숫자가 적힌 카드를 찾아 맨 왼쪽에 놓고, 나머지 카드 중에서 가장 작은 숫자를 찾아 맨 왼쪽 카드 다음에 놓고, 이를 반복하여 모든 카드를 정렬한다. 버블 정렬(Bubble sort) : 첫 번째 숫자와 두 번째 숫자를, 두 번째 숫자와 세 번째 숫자를, 세 번째 숫자와 네 번째 숫자를 ,... 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다.힙 정렬(Heap sort) : 정렬해야 할 n개의 요소들로 최대 힙(완전 이진 트리 형태)을 만들고 한 번에 하나씩 요소를 힙에서 꺼내서 배열의 뒤부터 저장한다. 삭제되는 요소들(최댓값부터 삭제)은 값이 감소되는 순서로 정렬되게 된다. 퀵 정렬(Quic..

- 그래프그래프는 정점(Vertex)과 간선(Edge)의 집합으로 하나의 간선은 2개의 정점을 연결그래프는 G=(V,E)로 표현. V=정점의 집합 / E=간선의 집합무방향 그래프(Undirected Graph) : 간선에 방향이 없는 그래프방향 그래프(Directed Graph) : 간선에 방향이 있는 그래프정점 a와 b를 연결하는 간선 : (a,b)정점 a에서 b로 간선의 방향이 있는 경우 :  경로(path) : 시작점 u부터 도착점 v까지의 정점을 나열하여 표현사이클(cycle) : 시작점과 도착점이 같은 단순 경로가중치(Weighted) 그래프 : 간선에 가중치가 부여된 그래프부분 그래프(Subgraph) : 주어진 그래프의 정점과 간선의 일부분으로 이루어진 그래프트리(Tree) : 사이클이 없는..

- 트리(Tree)루트(root) - 트리의 최상위에 있는 노드자식(child) - 노드 하위에 연결된 노드부모(parent) - 노드 상위에 연결된 노드잎(leaf) - 자식 없는 노드형제(sibling) - 동일한 부모를 가지는 노드조상(Ancestor) - 루트까지의 경로상에 있는 모든 노드후손(Descendant) - 노드 아래로 매달린 모든 노드서브트리(Subtree) - 노드 자신과 후손으로 구성된 트리레벨(Level) - 루트는 레벨1, 아래층으로 내려가며 레벨 1씩 증가높이(Height) - 트리의 최대 레벨키(Key) - 탐색에 사용되는 노드에 저장된 정보내부노드 - 잎이 아닌 노드외부노드 - 잎 - 이진 트리empty이거나, empty가 아니면 루트와 2개의 이진 트리인 왼쪽 서브트리와..

- 자료구조란?일련의 동일한 타입의 데이터를 정돈하여 저장한 구성체- 왜 자료구조가 필요할까?정돈하는 목적 : 저장된 데이터에 대해 탐색, 삽입, 삭제 등의 연산을 효율적으로 수행하기 위해서자료구조는 [데이터] + [데이터에 관련된 연산] 함께 고려하여 만들어야 한다. - 알고리즘과 자료구조의 관계효율적인 알고리즘을 위해입력 데이터를 위한 효율적인 자료구조알고리즘의 수행 과정에서 만들어지는 데이터도 효율적인 자료구조에 저장되어야 - 순환(Recursion)함수 / 메소드의 실행 과정 중 스스로를 호출하는 것함수가 순환 호출할 때 무한 호출을 방지해야더보기def recurse():     print('*')     recurse() recurse() 재귀 종료조건을 설정해야 함순환으로 구현된 함수 / 메소..

- 알고리즘이란?문제를 해결하는 유한한 수의 단계적 절차로서 입력에 대해 컴퓨터에서 수행 가능한 연산을 통해 수행 결과인 해(또는 답)를 출력한다.- 알고리즘의 속성정확성(correct) : 알고리즘은 주어진 입력에 대해 올바른 해를 주어야수행성(excutable) : 알고리즘의 각 단계는 컴퓨터에서 수행이 가능하여야유한성(finite) : 알고리즘은 유한 시간 내에 종료되어야 - 알고리즘의 성능 분석시간 복잡도(Time Complexity) - 수행 시간공간 복잡도(Space Complexity) - 알고리즘이 수행되는 동안 사용되는 메모리 공간의 크기더보기대부분의 경우 시간 복잡도 사용 : 대부분의 알고리즘들이 비슷한 크기의 메모리 공간을 사용하기 때문- 알고리즘의 분석 종류최악 경우 분석(Worst..