본문 바로가기

공부기록/자료구조

재귀 알고리즘 _ 하노이 타워 문제 '윤성우의 열혈 자료구조'의 Ch.2 재귀(Recursion)를 보면서 요약한 내용입니다. 재귀 알고리즘에서는 다음 두 가지를 잘 생각해야 한다. 1. 재귀의 탈출 조건 2. 반복되는 패턴 [EX 1] 팩토리얼 구하기 👇 소스코드 더보기 #include int recursive_factorial(int nb) { if (nb 공부기록/자료구조 2020. 12. 8.
이진탐색 알고리즘의 시간 복잡도 그리고 빅-오 표기법 '윤성우의 열혈 자료구조'의 Ch.1 을 보면서 요약한 내용입니다. 알고리즘의 시간복잡도 (Time Complexity)는 최악의 경우를 기준으로 계산한다. [EX] 이진탐색 알고리즘의 시간복잡도 계산해보기 n개의 데이터에 대해 이진탐색을 진행할 때, 최악의 경우는 데이터가 한 개 남을 때 까지 찾는 경우이다. 연산 횟수를 표현하면 다음과 같다. n이 1이 될 때까지 2로 나눈 횟수 : k 데이터가 한 개 남았을 때 마지막으로 비교연산 1회 진행 시간 복잡도 계산해보기 $ T(n) = k + 1 $ $k$ 구하기 n 이 1이 될 때까지 2로 나눈 횟수가 k 라면 식으로 다음과 같이 표현할 수 있다. $ n \times (\frac{1}{2})^{k} = 1 $ $ n \times 2^{-k} = 1 $ .. 공부기록/자료구조 2020. 12. 7.
배열리스트와 연결리스트 비교 장단점 비교 배열 기반 리스트의 장점 데이터의 참조가 쉽다. 인덱스 값을 기준으로 어디든 한 번에 참조가 가능하다. 배열 기반 리스트의 단점 배열의 길이가 초기에 결정되어야 한다. 변경이 불가능하다. 삭제의 과정에서 데이터의 이동(복사)가 매우 빈번히 일어난다. 👆 이거 반대가 연결리스트의 장점이다. 메모리를 동적으로 할당해 리스트의 길이를 유연하게 조절할 수 있다. 연결리스트의 노드를 표현하는 구조체 typedef struct _node { LData data; struct _node *next; } 연결리스트를 의미하는 구조체 (한 프로그램 안에 여러개의 연결리스트가 존재할 수 있으니, 이를 다루는 별도의 구조체를 정의해야함) typedef struct _linkedList { Node *head; .. 공부기록/자료구조 2020. 4. 21.
[자료구조] 연결리스트 head에 추가, tail에 추가, dummy node 활용 '윤성우의 열혈 자료구조'의 Ch4. 연결리스트를 공부하면서 정리한 내용이다. 연결리스트에서 노드를 추가할 때, 뒤에 추가하는 방법과, 앞에 추가하는 방법이 있다. 두 코드에서 핵심적인 부분들만 가져왔다. 아래의 코드에서 사용하는 구조체는 이렇게 생겼다. tail 에서 추가되는 연결리스트 head에서 추가되는 연결리스트 tail에서 추가되는 방법은 tail 포인터가 움직이고, head에서 추가되는 방법은 head 포인터가 움직인다는 점이 다르다. 두 방법의 장단점 비교 tail head 장점 저장된 순서가 유지된다. 포인터변수 tail이 불필요하다. 단점 포인터변수 tail이 필요하다. 저장된 순서를 유지하지 않는다. Dummy Node 활용 위에서 본 방법은, 노드를 추가, 삭제, 조회 하는 방법에 있.. 공부기록/자료구조 2020. 3. 18.

티스토리툴바