공부/자료구조 & 알고리즘

[알고리즘] 정렬

정렬은 왜 필요할까? 우리가 사전에서 단어를 쉽게 찾을 수 있는 것처럼 컴퓨터도 정렬되어 있는 데이터에서 보다 효율적으로 탐색할 수 있기 때문이다. ◆ Bubble Sort, 거품정렬 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘 ◇ 과정 1회전에 첫번째 원소와 두번째 원소를, 두번째와 세번째, 세번째와 네번째 ... 이런 식으로 비교하며 조건에 맞지 않다면 서로 교환한다. 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 제외되고, 2회전을 수행하고 나면 끝에서 두번째 원소까지는 정렬에서 제외된다. 이렇게 제외되는 원소가 늘어난다. ● 시간복잡도 데이터의 개수가 N이라 할 때, 비교횟수는 N-1, N-2, N-3..

[자료구조] 여러 자료구조들

◆ 자료구조란? 자료구조란 데이터를 표현하고 저장하는 방식이다. 자료구조는 다음과 같이 분류할 수 있다. ◎ 선형 자료구조 배열 연결리스트 스택 큐 ◎ 비선형 구조 트리 힙 그래프 ◆ 목적 자료를 더 효율적으로 저장하고, 관리하기 위해 사용한다. 잘 선택된 자료구조는 실행시간을 단축시켜 주거나 메모리 용량의 절약을 이끌어 낼 수 있다. ◇ 리스트List (배열Array, 연결리스트Linked List) 리스트는 선형적으로 값을 가지고 있는 자료구조이며, 보통 ①배열(Array)과 ②연결리스트(Linked List)로 나뉜다. 그중 배열은 같은 자료형의 요소들이 순서를 갖고 나열되어 있는 집합으로 메모리에 연속적으로 저장되며, 논리적 저장 순서와 물리적 저장 순서가 일치한다. 연결리스트는 메모리의 동적할당..

자료구조 - 2. 리스트

리스트 특징 데이터를 나란히 저장한다. 데이터가 일직선으로 구성된 선형 구조다. 일반적으로 리스트 하면 배열을 의미하지만 구현방식에 따라 다음 두가지로 나뉜다. 순차리스트 : 배열을 기반으로 구현된 리스트 (=배열) 연결리스트 : 메모리의 동적할당을 기반으로 구현된 리스트 순차리스트 단점 배열의 길이가 초기에 결정되어야 한다. 변경이 불가능하다. 삽입, 삭제의 과정에서 데이터의 이동이 매우 빈번히 일어난다. 복잡하다 순차리스트 장점 데이터의 참조가 쉽다. 인덱스 값을 기준으로 어디든 한번에 참조가 가능하다. 연결리스트 장점 삽입이 간단하다. 연결리스트 단점 데이터를 참조하는데 시간이 오래걸린다. 최대 O(n)의 시간이 걸린다. 즉, 데이터의 크기가 고정되어있고 참조를 많이 하면 배열이 좋고, 데이터의 크..

자료구조 - 1. 재귀

자료구조란? 데이터의 표현 및 저장방법 재귀함수란 재귀함수란 함수 내에서 자기 자신을 다시 호출하는 함수를 의미한다. 함수가 아직 끝나지 않았는데 다시 호출할 수 있는가? 할 수 있다. 재귀함수의 흐름을 이해하기 힘들다면 함수의 원본이 따로 있고 해당 재귀함수에서 재귀함수가 호출될 때마다 함수의 복사본이 만들어져서 그 복사본이 실행된다고 생각하면 이해하기 쉽다. 재귀함수의 예 : n 팩토리얼 int Factorial(int n) { if(n == 0) return 1; else return n * Factorial(n-1); } Factorial(4);을 실행하면 Factorial(4) 함수 내부에서 Factorial(3)을 호출하고 다시 그 안에서 Factorial(2)를 호출하고 다시 Factoria..