본문 바로가기

Algorithm

 (31)
리스트 (선형 리스트 / 단일 연결 리스트) 연결 리스트 단일 연결 리스트 원형 연결 리스트 이중 연결 리스트 리스트에서 처리할 수 있는 연산 길이 : 리스트의 길이를 구하는 연산 접근 : 리스트의 내용을 조사하거나 변경하기 위해 위치를 찾는 연산 검색 : 리스트의 노드들 중에서 필요한 노드 (i번째)를 찾는 연산 저장 : i번째에 노드에 새로운 값을 기억시키는 연산 삽입 : 리스트에 새로운 노드를 삽입시키는 연산 삭제 : 리스트에서 노드를 제거하는 연산 복사 : 리스트의 전체 또는 일부를 복사하여 새로운 노드(리스트)를 만드는 연산 정렬 : 어떤 기준으로 리스트를 정렬(오름차순/내림차순)하는 연산 병렬 : 둘 또는 그 이상의 리스트를 하나의 리스트로 합치는 연산 분리 : 한 리스트를 둘 또는 그 이상의 리스트로 나누는 연산 선형 리스트 (line..
분할과 정복 기법 (Divide and Conquer) 분할과 정복 기법 (Divide and Conquer) : 하향식 설계 기법 : 문제의 크기를 작게 나누어서 좀 더 쉽게 해결할 수 있는 상태로 변환하여 문제를 해결하는 방법 : 하나의 문제를 여러 개의 작은 문제로 나누어 각각에 동일한 해결 기법을 계속적으로 적용한 후, 결과들을 연합하여 원래의 문제를 해결 : 분할된 부분의 문제들의 크기가 커서 해결이 여전히 쉽지 않을 경우, 각 부분의 문제들에 대해 다시 분할과 정복 기법 적용 : 각 부분의 문제들이 간단히 해결될 수 있는 상태에 이를 때까지 반복 (순환 : recursion) 재귀함수 : 분할과 정복 기법을 위한 구현 기술 : 처리 과정이 분할된 작은 문제들에 서로 동일한 로직이 여러 번 발생하는 것을 방지하기 위해 동적 프로그래밍 기법 사용 재귀..
알고리즘의 시간 복잡도 알고리즘의 성능 : 프로그램이 실행되는 동안 요구하는 공간적 및 시간적 자원량에 따라 결정됨 : 자원을 적게 요구할수록 성능이 좋은 알고리즘 공간적 자원 - 컴파일된 프로그램을 이루는 명령어 저장 공간 (하드 디스크) - 프로그램이 실행되는 동안 필요한 데이터 저장 공간 (메모리) - 프로그램의 제어 정보와 임시 정보 저장 공간 시간적 자원 - 알고리즘이 구현된 프로그램이 시작되어 종료될 때까지 걸리는 시간 알고리즘의 시간 복잡도 : 알고리즘의 시간적 성능을 분석하기 위해 입력 크기 n에 대한 기본 연산의 실행 횟수를 함수 형태로 나타낸 것 : 같은 입력에 대해 같은 결과를 가지는 연산이더라도, 알고리즘 구현 방법에 따라서 시간복잡도가 달라질 수 있음 예시 - T(n) = n - T(n) = n - 1 ..
알고리즘 기본 개념 알고리즘 : 주어진 문제 해결을 위해 논리적 절차에 의해 계획한 해결 방안을 정형적이고 체계적으로 기술한 것 : 구체적인 작업에 들어가기 전, 어떤 구조 및 방법으로 문제를 해결해 갈 것인지를 생각하는 기본적인 설계 : 문제 해결을 위해 단계별로 명확하게 기술하여 나열한 일련의 명령어 들의 모임 알고리즘 종류 재귀적 알고리즘 최대값/최소값 찾기 유클리드 알고리즘 최대공약수) 팩토리얼 피보나치 수열 합계 탐색 알고리즘 순차 탐색 (선형 탐색) 이진 탐색 레드 블랙 트리 정렬 알고리즘 선택 정렬 버블 정렬 퀵 정렬 삽입 정렬 쉡 정렬 힙 정렬 병합 정렬 기수 정렬 해시 알고리즘 해시 테이블 그래프 알고리즘 그래프 순회 (깊이 우선 검색, 넓이 우선 검색) 그래프 탐색/검색 최소 신장 트리 (크루스 칼의 알고..
퀵 정렬 (Quick Sort) 퀵 정렬 (Quick Sort) : 기준 데이터 (pivot)을 설정하고, 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 정렬 방법 : 일반적으로 첫 번째 데이터를 pivot으로 설정함 : 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나 : 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘 -> (일반적으로 표준 정렬 라이브러리 제공 시, 최악의 경우에도 시간복잡도 nlog₂n을 보장할 수 있는 형태로 구현됨) : 재귀적으로 수행되며, 정렬이 수행될 때마다 정렬 범위가 점점 좁아짐 : 이상적인 경우 분할이 절반에 가깝게 일어남 -> 빠른 속도 : pivot 값 설정에 따라 분할이 한 쪽 방향으로 편향된 분할을 가지는 경우, 최악의 시간 복잡도 = n^2 퀵 정렬의 과정..
삽입정렬 (insertion sort) 삽입정렬 (insertion sort) : 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입하는 정렬 알고리즘 : 매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 넣음 : 손 안의 카드를 정렬하는 방법과 유사 새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입 -> 새로 삽입될 카드의 수 만큼 반복하여 정렬 : 선택정렬에 비해 구현 난이도는 높지만 효율적 : 현재 리스트의 데이터가 거의 정렬되어 있는 상태일수록 빠르게 동작 : 비교적 많은 레코드들의 이동을 포함하기 때문에 레코드 수가 많거나 레코드의 크기가 큰 경우 적합하지 않음 삽입 정렬의 과정 1. 두 번째 자료부터 시작 (= key) -> 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치 지정 2. 해당 위치에 자..
선택 정렬 (Selection Sort) 선택 정렬 (Selection Sort) : 처리되지 않은 데이터 중, 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복하는 정렬 알고리즘 = 매번 현재 범위에서 가장 작은 데이터를 골라 가장 앞쪽으로 보내는 과정을 반복 : 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘 : 과정이 반복될 수록 탐색 범위 줄어듦 : 알고리즘이 단순하다는 장점 : 정렬 과정에서 정렬을 위한 비교 횟수는 많지만, 실제 값이 교환되는 횟수는 적음 -> 교환이 잦은 자료 정렬에 효율적 : 배열 안에서 교환하는 방식 -> 추가적인 메모리 공간 필요로 하지 않음 (제자리 정렬 = in-place sorting) : 불안정 정렬이라는 단점 존재 선택 정렬의 과정 1. 주어진..
이진 탐색 트리 (Binary Search Tree) 이진탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료구조의 일종 전체 노드에 대하여 왼쪽 자식 노드는 부모노드보다 값이 작고, 오른쪽 자식 노드는 부모노드보다 값이 큰 값을 가지도록 이진트리 구성 (왼쪽 자식 노드 찾는 원소가 더 작다면 왼쪽/크다면 오른쪽 방문 2번 과정 반복하다가 원소를 찾으면 탐색 종료 (이상적인 경우 탐색 범위가 절반 가까이..
Tree Tree (트리) 자료의 항목(node)들이 가지(dege)로 연결되어 구성된 구조 계층적인 구조 표현 시 사용 부모-자식 관계의 노드들로 구성 트리 관련 용어 노드 (node) : 트리를 구성하는 각 자료 항목 근 노드 (root node) 부모가 없는 최상위 노드 트리 구조를 시작하는 노드 제일 상위 계층에 존재하는 하나의 노드 자식 노드 : 임의의 노드에 연결된 다음 레벨의 노드들의 집합 부모 노드 : 임의의 노드에 연결된 상위 계층의 노드 단말 노드 : 자식 노드가 없는 노드 차수 (degree) 각 노드의 자식 방향으로의 간선 개수 한 노드에 연결된 가지의 수 노드가 갖고 있는 자식 노드의 개수 레벨 : root node 레벨을 0으로 하고, 그 아래 가지로 연결된 노드들의 레벨 1씩 증가 트리..

티스토리툴바