면접준비/알고리즘

알고리즘 계산 복잡도는 다음 두 가지 척도로 표현될 수 있음시간 복잡도: 얼마나 빠르게 실행되는지공간 복잡도: 얼마나 많은 저장 공간이 필요한지좋은 알고리즘은 실행 시간도 짧고, 저장 공간도 적게 쓰는 알고리즘통상 둘 다를 만족시키기는 어려움시간과 공간은 반비례적 경향

알고리즘을 잘 작성하기 위해서는 잘 작성된 알고리즘을 이해하고, 스스로 만들어봐야 함모사! 그림을 잘 그리기 위해서는 잘 그린 그림을 모방하는 것부터 시작이번 챕터부터 알고리즘 시작입니다.!1\. 연습장과 펜을 준비하자.2\. 알고리즘 문제를 읽고 분석한 후에,3\.

다음과 같은 순서를 반복하며 정렬하는 알고리즘주어진 데이터 중, 최소값을 찾음해당 최소값을 데이터 맨 앞에 위치한 값과 교체함맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복함출처: https://en.wikipedia.org/wiki/Selection

삽입 정렬은 두 번째 인덱스부터 시작해당 인덱스(key 값) 앞에 있는 데이터(B)부터 비교해서 key 값이 더 작으면, B값을 뒤 인덱스로 복사이를 key 값이 더 큰 데이터를 만날때까지 반복, 그리고 큰 데이터를 만난 위치 바로 뒤에 key 값을 이동출처: http

고급 정렬 알고리즘엥서 재귀 용법을 사용하므로, 고급 정렬 알고리즘을 익히기 전에 재귀 용법을 먼저 익히기로 합니다.함수 안에서 동일한 함수를 호출하는 형태여러 알고리즘 작성시 사용되므로, 익숙해져야 함예제를 풀어보며, 재귀 용법을 이해해보기팩토리얼을 구하는 알고리즘을

동적계획법 (DP 라고 많이 부름)입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서, 보다 큰 크기의 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘상향식 접근법으로, 가장 최하위 해답을 구한 후, 이를 저장하고, 해당 결과값을

<font color='\* 기준점(pivot 이라고 부름)을 정해서, 기준점보다 작은 데이터는 왼쪽(left), 큰 데이터는 오른쪽(right) 으로 모으는 함수를 작성함각 왼쪽(left), 오른쪽(right)은 재귀용법을 사용해서 다시 동일 함수를 호출하여 위

탐색은 여러 데이터 중에서 원하는 데이터를 찾아내는 것을 의미데이터가 담겨있는 리스트를 앞에서부터 하나씩 비교해서 원하는 데이터를 찾는 방법최악의 경우 리스트 길이가 n일 때, n번 비교해야 함O(n)

탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법저작자 by penjee.com 이미지 출처분할 정복 알고리즘 (Divide and Conquer)Divide: 문제를 하나 또는 둘 이상으로 나눈다.Conquer: 나눠진 문제가 충분히 작고, 해결이

그래프는 실제 세계의 현상이나 사물을 정점(Vertex) 또는 노드(Node) 와 간선(Edge)로 표현하기 위해 사용노드 (Node): 위치를 말함, 정점(Vertex)라고도 함간선 (Edge): 위치 간의 관계를 표시한 선으로 노드를 연결한 선이라고 보면 됨 (li

대표적인 그래프 탐색 알고리즘너비 우선 탐색 (Breadth First Search): 정점들과 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 탐색하는 방식깊이 우선 탐색 (Depth First Search): 정점의 자식들을 먼저 탐색하는 방식BFS 방식: A -

대표적인 그래프 탐색 알고리즘너비 우선 탐색 (Breadth First Search): 정점들과 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 탐색하는 방식깊이 우선 탐색 (Depth First Search): 정점의 자식들을 먼저 탐색하는 방식BFS 방식: A -

Greedy algorithm 또는 탐욕 알고리즘 이라고 불리움최적의 해에 가까운 값을 구하기 위해 사용됨여러 경우 중 하나를 결정해야할 때마다, 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서, 최종적인 값을 구하는 방식지불해야 하는 값이 4720원 일

최단 경로 문제란 두 노드를 잇는 가장 짧은 경로를 찾는 문제임가중치 그래프 (Weighted Graph) 에서 간선 (Edge)의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적단일 출발 및 단일 도착 (single-source and single-destin

대표적인 최소 신장 트리 알고리즘Kruskal’s algorithm (크루스칼 알고리즘), Prim's algorithm (프림 알고리즘)프림 알고리즘 시작 정점을 선택한 후, 정점에 인접한 간선중 최소 간선으로 연결된 정점을 선택하고, 해당 정점에서 다시 최소 간선으

대표적인 최소 신장 트리 알고리즘Kruskal’s algorithm (크루스칼 알고리즘), Prim's algorithm (프림 알고리즘)프림 알고리즘 시작 정점을 선택한 후, 정점에 인접한 간선중 최소 간선으로 연결된 정점을 선택하고, 해당 정점에서 다시 최소 간선으

백트래킹 (backtracking) 또는 퇴각 검색 (backtrack)으로 부름제약 조건 만족 문제 (Constraint Satisfaction Problem) 에서 해를 찾기 위한 전략해를 찾기 위해, 후보군에 제약 조건을 점진적으로 체크하다가, 해당 후보군이 제약