오전 팀원 코어 타임을 가졌습니다. 퀴즈를 진행하는 날입니다.
BST, B-Tree 에 대해서 서로 공부한 내용을 공유하는 시간을 가졌습니다.
오늘 배운 BST내용은 따로 포스팅하도록하겠습니다.
코어타임
BST 대해…
시연님 git 블로그 참고
https://github.com/sihyun10/data_structures_docker/wiki/BST-(Binary_Search_Tree)
*연산자가 -> 연산자보다 우선순위가 높기때문에 괄호를 써야한다.
ex)(node)->left)
이중포인터를 왜 쓰는가?
구조체에서 포인터(->)로 언급 됐을때, 구조체(ll) 안의 포인터로 호출(next)로 되어있을때
구조체 안의 포인터를 호출하고 싶을때는 이중 포인터(**ll)를 쓴다.
WEEK 05 퀴즈
금일 퀴즈를 진행했습니다. B-Tree 예찬님을 통해 모두 이해하여 다른 분들께 신나게 설명해드렸지만, 정작 퀴즈에서 문제 잘못읽어서 틀린 것이 마음이 굉장히 아픕니다...
퀴즈와 관련된 내용은 추후 포스팅 하겠습니다.
5. C언어 Linked List 5번
[문제 내용]
5. frontBackSplitLL
설명:
하나의 연결 리스트를 앞 절반과 뒤 절반으로 분할하는 함수 작성
※ 원소 수가 홀수일 경우, 앞 리스트에 하나 더 포함시킴
함수 원형:
void frontBackSplitLL(LinkedList *ll, LinkedList *resultFrontList, LinkedList *resultBackList);예시:
입력: 2, 3, 5, 6, 7
→ frontList: 2, 3, 5
→ backList: 6, 7
[풀이 방법]
하나의 연결 리스트에서 앞,뒤 절반을 나눠서 앞리스트, 뒷리스트를 출력하면 된다. 만약, 홀수라면 앞 리스트에 하나를 더 쓴다. 리스트를 받고 나눈다.
[코드와 해설]
void frontBackSplitLinkedList(LinkedList *ll, LinkedList *resultFrontList, LinkedList *resultBackList)
{
/*
하나의 연결 리스트에서 앞,뒤 절반을 나눠서 앞리스트, 뒷리스트를 출력하면 된다.
만약, 홀수라면 앞 리스트에 하나를 더 쓴다.
리스트를 받고 나눈다.
*/
if(ll == NULL || ll->head == NULL){
return;
}
int totalSize = ll->size ; // 전체 노드의 수를 저장
int frontSize = (totalSize + 1) / 2; // 홀수 일시 앞에 하나 더
// 애초에 홀수 일시 +1을 하여 사이즈를 늘림(짝수 일때 +1해도 값은 같음)
int i;
// 총 사이즈(인덱스)를 0부터 올리며 하나씩 찾는다.
for (i = 0; i< totalSize; i++) {
ListNode *curNode = findNode(ll,i); // 입력 리스트 ll에서 i번째 노드 가져옴.
// findNode는 연결리스트를 처음부터 따라가면서 i번째 위치에 있는 노드를 반환.
if(curNode == NULL) continue; // 유효한 노드가 없으면 건너뛰고 다음 노드 탐색(예외처리)
if(i < frontSize) { // 앞에 미리 계산한 앞 사이즈보다 작으면 앞 리스트에 배정
insertNode(resultFrontList, resultFrontList->size, curNode->item);
} else { // 그렇지 않으면 뒷 리스트에 배정
insertNode(resultBackList, resultBackList->size, curNode->item);
}
}
}6. C언어 Linked List 6번
[문제 내용]
6. moveMaxToFront
설명:
연결 리스트에서 가장 큰 값을 가진 노드를 찾아 맨 앞으로 이동시키는 함수 작성
※ 리스트 전체를 최대 한 번만 순회해야 함
함수 원형:
int moveMaxToFront(ListNode **ptrHead);예시:
입력: (30, 20, 40, 70, 50)
결과: (70, 30, 20, 40, 50)
[풀이 방법]
리스트에서 가장 큰 요소가 앞에 위치해서 출력하면 된다.
입력 받은 리스트에서 max인 값을 뽑아서 맨 앞으로 보내기 위해
temp에 저장하고 나머지 값을 차례대로 입력하여 출력하면 될 것 같다.
헤드를 순회하면서 제일 높은 값을 추출해야 좋을 것 같다.
→ GPT한테 물어보니 연결만 바꿔주면 된다고 한다. 생각보다 간단한데, 코드는 안간단하다.
[코드와 해설]
int moveMaxToFront(ListNode **ptrHead)
{
/*
리스트에서 가장 큰 요소가 앞에 위치해서 출력하면 된다.
입력 받은 리스트에서 max인 값을 뽑아서 맨 앞으로 보내기 위해
temp에 저장하고 나머지 값을 차례대로 입력하여 출력하면 될 것 같다.
헤드를 순회하면서 제일 높은 값을 추출해야 좋을 것 같다.
GPT한테 물어보니 연결만 바꿔주면 된다고 한다.
*/
if(ptrHead == NULL || *ptrHead == NULL || (*ptrHead)->next == NULL){ // 만약에 빈 리스트이거나 노드 1개일때 처리
return 0;
}
ListNode *maxNode = *ptrHead; // 최대값을 가진 노드를 저장할 포인터, 처음엔 head로 시작
ListNode *maxPrev = NULL; // 최대 노드의 이전 노드를 저장할 포인터 (연결 변경용)
ListNode *prev = NULL; // 현재 노드의 이전 노드 추적용 포인터
ListNode *curr = *ptrHead; // 현재 순회 중인 노드를 가리키는 포인터
// 최대값 찾기
while(curr != NULL) {
if(curr->item > maxNode->item){
maxNode = curr; // 더 큰 값을 발견하면 maxNode 갱신
maxPrev = prev; // 그리고 그 노드의 이전 노드도 기억해둠(전 노드로 이동시 사용)
}
prev = curr; // prev를 현재 노드로 이동
curr = curr->next; // 다음 노드로 이동
}
// 최댓값이 이미 맨 앞(head)에 있다면 그대로 진행
if(maxPrev == NULL) {
return 0;
}
// maxNode를 기존 위치에서 제거 (이전 노드의 next를 다음 노드로 연결)
maxPrev -> next = maxNode -> next;
// maxNode를 리스트 맨 앞에 삽입
maxNode->next = *ptrHead;
*ptrHead = maxNode;
return 1; // 작업 성공 시 1 반환
}7. C언어 Linked List 7번
[문제 내용]
7. recursiveReverse
설명:
재귀적으로 연결 리스트를 역순으로 뒤집는 함수 작성
※ 포인터를 변경하여 리스트 순서를 바꿈
함수 원형:
void recursiveReverse(ListNode **ptrHead);예시:
입력: (1, 2, 3, 4, 5)
결과: (5, 4, 3, 2, 1)
[풀이 방법]
받은 리스트의 값을 거꾸로 출력되게만 하면된다.
그렇기 위해선 받았던 값을 재귀를 통해 역순으로 다시 출력하면되지 않을까 싶다.
[코드와 해설]
void RecursiveReverse(ListNode **ptrHead)
{
/*
받은 리스트의 값을 거꾸로 출력되게만 하면된다.
그렇기 위해선 받았던 값을 재귀를 통해 역순으로 다시 출력하면되지 않을까 싶다.
*/
if(*ptrHead == NULL || (*ptrHead)->next == NULL){
return;
}
ListNode *first = *ptrHead; // 현재 head로 앞 노드를 의미한다.
ListNode *rest = first->next; // first를 제외한 나머지 리스트
RecursiveReverse(&rest); // rest를 역순으로 처리합니다. 호출 종료시 rest는 뒤집힌 리스트의 새로운 head가 됩니다.
first->next->next = first; // first->next는 현재 rest의 마지막 노드가 되고 있는데, 그 노드의 next를 first로 연결 -> 역방향 연결
first->next = NULL; // first는 맨끝에 오니 처리
*ptrHead = rest; // 뒤집힌 리스트의 새로운 head(rest)를 원래 head에 갱신
// 1->2->3->NULL 이 3->2->1->NULL 로 바뀝니다.
}이후의 Stack and Queue 문제에 대해서 다음 포스팅으로 옮겨적도록 하겠습니다!
