반응형 학습공간/C, 자료구조와 알고리즘 (9) 썸네일형 리스트형 [8장] 트리 트리에 대한 문제풀이 내용이다. 트리(Tree)란? - 부모-자식 관계로 정의하고, 부모에서 자식으로 간선이 이어져 있는 유향 그래프이다. (비선형 자료구조) - 부모가 없는 최상위 노드를 루트 노드라고 한다. - 자식 노드가 2개 이상이며 최대 자식 노드가 n개인 트리를 n진 트리라고 부른다. 트리 형태의 자료구조는 일상에서도 자주 쓰이는데, 다항식의 수식을 계산하거나 검색창의 자동완성 기능이 이에 해당한다. 주로 데이터의 좌측과 우측에 자식 노드의 주소를 가리키는 연결 리스트를 이용해 이진 트리를 구현하는데, 연습문제와 함께 트리의 개념과 순회 방법을 익히고 일차원 배열 이진 트리(Binary Tree)를 구현해보자. (배열의 인덱스 값과 이진 트리의 노드 값을 일치 시키고, 부모 노드 값 n 밑에 .. [7장] 연결 리스트 II 지난 6장에서는 연결 리스트의 구현과 몇 가지 함수를 추가해 보았다. 이번 7장에서는 아래 링크의 가장 하단에 있는 연결 리스트로 구현한 스택과 큐를 리뷰하도록 해보자. #include #include typedef int element; typedef struct ListNode{ element data; struct ListNode *link; } ListNode; void error(char *message){ fprintf(stderr, "%s\n", message); } ListNode *create_node(element data, ListNode *link){ ListNode *new_node; new_node = (ListNode *)malloc(sizeof(ListNode)); if(ne.. [6장] 연결 리스트 I 연결 리스트에 대한 문제풀이 내용이다. 연결 리스트(Linked List)란? - 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다. - 메모리를 동적 할당을 기반으로 구현하여 데이터를 효율적으로 관리할 수 있는 장점이 있다. (배열 한계 극복) [데이터 | 다음 노드의 주소] → [데이터 | 다음 노드의 주소] → [데이터 | 마지막 NULL] 구조체 리스트 노드를 생성하고 삽입하고 삭제하는 것부터 연습해보고, 리스트 탐색, 합병, 역순, 대체 및 삽입의 위치를 맨앞, 맨뒤 조정하여 함수를 구현해보자. 연결 리스트(주석과 함께 한줄씩 분석) #include #include typedef int element; typedef struct ListNode{ .. [5장] 큐 큐에 대한 문제풀이 내용이다. 큐(Queue)란? - 한마디로 표현하면 선입선출, FIFO(First In, First Out) 형태의 자료구조이다. - 자동차로 비유하면 각 지방도로에서 톨게이트를 거쳐서 인라인하게 데이터가 줄지어 지는것이다. (순차적 처리) 앞서 활용한 배열 리스트 형태로 원형 큐를 구현해보자. ※ 연결 리스트 큐는 6장 연결 리스트를 선행한 뒤 참조 (배열의 인덱스 한계가 있기 때문에 마지막 인덱스에 도달하면 첫번째 인덱스를 가리키게 한다.) 원형 배열 큐 #include #include #define MAX_QUEUE_SIZE 100 typedef int element; typedef struct{ element queue[MAX_QUEUE_SIZE]; int front, rear.. [4장] 스택 스택에 대한 문제풀이 내용이다. 스택(Stack)이란? - 한마디로 표현하면 선입후출, FILO(First In, Last Out) 형태의 자료구조이다. - 주로 컴파일러에서 괄호검사를 시행할 때, '{' 중괄호는 '}' 중괄호, '('소괄호는 ')' 소괄호로 닫혀야 한다. (Syntex Check) - 여러 줄의 구문들이 섞여 있을 때 쌍쌍의 짝이 맞아 떨어져서 최종적으로 스택이 공백이 되어있어야 정상일 것이다. 예제를 통해 괄호검사 프로그램을 정적 배열로도 구현해보고, 포인터 변수를 활용한 동적 배열로도 구현해 볼 것이다. 스택을 구현하기에 앞서 사용할 배열 리스트를 학습해보자. 정적 배열 리스트 #include #include #define MAX_LIST_SIZE 100 typedef int el.. [3장] 배열, 구조체, 포인터 배열, 구조체, 포인터에 대한 문제풀이 내용이다. 배열(Arrays)이란? - 같은 형의 변수를 여러개 만드는데 사용된다. 반복 코드 등에서 배열을 사용하면 효율적 프로그래밍이 가능하다. 구조체(Struct)이란? - 하나 이상의 변수를 묶어서 좀더 편하게 사용할 수 있도록 도와주는 도구이다. - 똑같은 구조의 변수를 여러번 사용할 경우 유용하다. 포인터(Pointer)이란? - 변수의 주소를 가리키는 것이다. - 포인터 변수를 선언하여 주소를 저장하게 되면 그 변수의 주소를 가리키게 되는 것이다. 아래 문제들을 풀어보자. 01. C 언어에서의 배열에 대하여 다음 중 맞는 것은? (1) 3차원 이상의 배열은 불가능하다. (2) 배열의 이름은 포인터와 같은 역할을 한다. (3) 배열의 인덱스는 1에서부터 .. [2장] 순환 순환에 대한 문제풀이 내용이다. 순환(Recursion)이란? 알고리즘 내에서 자기 자신을 호출하는 것을 의미한다. 순환의 종류에는 직접 순환(Direct Recursion), 간접 순환(Indirect Recursion) 두 가지가 있다. 피보나치 수열, 팩토리얼 등은 함수 스스로를 호출하는 직접 순환이고, 간접 순환은 중간에 다른 함수를 거쳐서 돌아오는 것을 말한다. 이런 재귀 함수는 잘 사용하면 코드를 짧고 효율적으로 사용할 수 있겠지만, 함수가 완전히 종료되기 전까지 스택의 메모리 구조에 쌓이기 때문에 반복문을 이용해 대체하기도 한다. 아래 문제들을 풀어보자. (순환 피보나치 수열 vs 반복 피보나치 수열 수행시간 비교) 06. 다음의 순환 호출 함수에서 잘못된 점은 무엇인가? int recurs.. [1장] 자료구조와 알고리즘 빅오 표기법에 대한 문제풀이 내용이다. 빅오 표기법(big-O notation)이란? 알고리즘의 효율성을 표기해주는 표기법이다. 좀더 정확하게 설명하면, 해당 소스코드를 컴파일 했을때 시간 복잡도와 공간 복잡도(메모리)의 상한치가 어느정도 되는가를 알려주는 지표이기도 하다. 아래 문제들을 풀어보자. 08. 다음의 빅오 표기법들을 수행 시간이 적게 걸리는 것부터 나열하라. O(1) O(n) O(log n) O(n²) O(nlog n) O(n!) O(2ⁿ) --> O(1) 이전 1 2 다음 반응형
