알고리즘 개념

동적 계획법(DP)은 메모리를 적절히 사용하여 수행 시간 효율성을 향상시키는 방법이다이미 계산된 결과를 별도의 메모리 영역에 저장하여 중복계산을 막는다다이나믹 프로그래밍의 구현은 일반적으로 두가지 방식(top-down , bottom-up)으로 구성된다문제가 다음과

선택 정렬 (Selection Sort)정렬 순서주어진 리스트 중에 최소값을 찾는다그 값을 맨 앞에 위치한 값과 교체한다맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다예시코드시간 복잡도 비교

버블 정렬 (Bubble Sort)정렬 순서주어진 리스트에서 서로 이웃한 데이터를 비교하여 큰 데이터를 뒤로 보낸다리스트를 한 바퀴 돌면 가장 큰 값이 가장 뒤로 이동하게 되므로 두 번째 바퀴에는 마지막을 제외하고 1번을 반복한다예시코드시간 복잡도 비교

삽입 정렬 (Insertion Sort)리스트의 값을 하나씩 살펴보며 적절한 위치에 삽입한다정렬 순서첫 번째 숫자를 삽입한 것이라 하고 두 번째 숫자부터 확인한다현재 선택한 숫자 바로 앞부터 처음까지 왼쪽으로 이동하면서 가리킨 숫자가 선택한 숫자보다 클 시 가리킨 숫자

개념그리디 알고리즘(욕심쟁이 알고리즘)이란 매 선택에서 지금 당장 최적인 답을 선택하는 알고리즘 설계 기법이다 그리디 알고리즘을 사용하면 매 선택에서는 최적이지만 종합적으로 최적은 보장할 수 없다문제가 다음과 같은 조건일 때 그리디 알고리즘을 사용할 수 있다탐욕 선택

개념깊이 우선 탐색으로 그래프에서 깊이가 깊은 부분을 우선적으로 탐색하는 알고리즘스택 혹은 재귀를 이용한다동작현재 노드를 방문처리 한다현재 노드와 연결된 모든 노드 중 방문하지 않은 노드를 방문한다모든 노드를 방문할 때 까지 반복한다그래프 혹은 트리에서 모든 노드를

개념union-find 는 크게 union과 find로 나뉜다union(x,y) 연산은 원소 x와 y가 속해있는 집합을 입력으로 받아 2개의 집합을 합집합으로 만든다find(x) 연산은 원소 x가 속해있는 집합을 반환한다.구현

[알고리즘 개념] 최소신장트리(MST)-Prim > 개념 시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장해나간다 시작 단계에서는 시작 정점만이 신장 트리 집합에 포함된다 앞 단계에서 만들어진 신장 트리 집합에 인접한 정점들 중에서 최저 간선으로 연결된 정점을 선택하여 트리를 확장해나간다 > 인접행렬 그래프의 MST를 구하기 위한 Prim 알...

개념탐욕적인 방법으로 최소신장트리를 구한다순서간선들의 가중치를 오름차순으로 정렬한다정렬된 간선들의 리스트에서 사이클을 형성하지 않는 간선을 찾아 현재의 최소비용 신장트리의 집합에 추가한다실제로 사이클을 알기 위해서는 연결하려는 간선의 양 끝점이 동일한 집합에 없는지를

특징모든 정점이 연결되어 있으면서 사이클이 없는 트리이다그래프에 있는 n개의 정점을 n-1개의 간선으로 연결한다하나의 그래프에는 많은 신장트리가 존재 가능하다깊이 우선 탐색이나 너비 우선 탐색 도중 간선만 모으면 만들 수 있다신장 트리는 통신 네트워크 구축에 많이 사용

Longest Increasing Subsequence최장 증가 부분 수열→ 어떤 수열이 왼쪽에서 오른쪽으로 나열돼 있으면, 그 배열 순서를 유지하면서 크기가 점진적으로 커지는 가장 긴 부분수열을 추출하는 문제Brute-force 접근방법 수열의 모든 부분집합을 구하