정렬의 개념 2개 이상의 자료를 작은 것부터 큰 것 혹은 큰 것부터 작은 것 순서로 재배열하는 것 키란? 자료를 정렬하는데 사용하는 기준이 되는 특정 값 정렬은 컴퓨터 공학 분야에서 가장 기본적이고 중요한 알고리즘 중의 하나이다. 정렬의 단위 레코드 정렬시켜야 할 대상 필드라고 하는 작은 단위로 나누어진다. ex) 학생들의 레코드 이름, 학번, 주소, 전화번호 등이 필드가 될 것이다. 여러 필드 중 특별히 레코드와 레코드를 식별해주는 역할을 하는 필드를 '키'라고 한다. 정렬 알고리즘의 개요 정렬 알고리즘을 평가하는 효율성의 기준 비교연산의 횟수 이동연산의 횟수 정렬 알고리즘 단순하지만 비효율적인 알고리즘 구현하기가 쉽지만 비효율적이다. 삽입정렬 선택정렬 버블정렬 복잡하지만 효율적인 알고리즘 구현하기가 ..
![]()
이중 연결 리스트 하나의 노드가 선행 노드의 대한 링크와 후속 노드의 대한 링크를 가지고 있는 구조 장점 링크가 양방향이므로 양방향 탐색이 가능하다 단점 공간을 많이 차지하므로 코드가 복잡하고 구현이 어렵다. 실제로 사용되는 연결리스트의 구조는 아래와 같다. 헤드 노드 + 이중 연결리스트 + 원형 연결리스트 이중 연결 리스트 노드의 구조 3개의 필드로 구성되어 있다. 왼쪽 링크 필드, 데이터 필드, 오른쪽 링크 필드 임의의 노드를 가리키는 포인터를 p라고 가정하면 p = p->llink -> rlink = p -> rlink -> llink 가 항상 성립한다. 단순, 원형 연결리스트와는 다르게 이중 연결 리스트는 헤드 노드를 가진다. 헤드 포인터와는 다르다는 것을 명심해야 한다. 헤드노드란? 데이터를 가..
![]()
원형 연결 리스트 개념 단순 연결 리스트와 비슷하지만 차이점은 마지막 노드의 링크가 첫번째 노드를 가리키고 있는 리스트 마지막 노드의 링크 필드가 NULL이 아닌 첫번째 노드 주소가 되는 리스트 구조 장점: 한 노드에서 다른 모든 노드로의 접근이 가능 (한바퀴 돌아서 뒤로 다시 가면 되기 때문에) 단순 연결 리스트에서 head 포인터가 맨 앞에 있으나 원형 연결 리스트에서는 head 포인터를 마지막 노드를 가리키게 하면 노드 삽입, 삭제 연산이 용이하기 때문에 대부분 head 포인터를 맨 뒤 노드에 둔다. 원형 연결 리스트 맨 앞에 삽입 새로운 노드의 링크가 첫번째 노드를 가리키게 하고, 마지막 노드의 링크가 새로운 노드를 가리키면 된다. void insert_first(ListNode** phead, ..
![]()
역순 연산 - 리스트의 노드들을 역순으로 만드는 연산 주의점 - 링크의 방향을 역순으로 바꾸기 전에 미리 뒤의 노드를 알아놓아야 한다. 이 주의점이 이해가 안된다면 해당 포스트를 이해한 뒤 다시 보길 바란다. r q p 순으로 3개의 변수를 쓰는 이유는 역순으로 바꾸기 전 미리 뒤 노드의 정보를 알아놓기 위함이다. p의 뒤 노드는 p->link가 해결해준다. ListNode* reverse(ListNode* head) { ListNode* p, * q, * r; p = head; q = NULL; while (p != NULL) { r = q; q = p; p = p->link; q->link = r; } return q; } 코드만 보면 굉장히 간단해 보이는데...꽤나 복잡하다..ㅠㅠ 연결 리스트는 위..
