2025.04.12

TIL(TODAY I LEARN)

---

• 오늘한 내용 : C - linked list/stack queue, 백준 - 12789
• WEEK05: C Pointer(&, * 연산자), 동적 메모리 할당, Linked List, Stack, Queue, Binary Tree, Binary Search Tree, 동적 프로그래밍, 그리디 알고리즘
• 계속해서 C언어를 공부해보자
• 한문제라도 풀자!

---

1. Linked List

(7) RecursiveReverse()

void RecursiveReverse(ListNode **ptrHead)
{
	/* add your code here */
	
	ListNode* cur = (*ptrHead)->next;
	ListNode* prev = *ptrHead;
	
	//empty or len == 1 처리
	if(prev == NULL || cur == NULL){
		return;
	}
	RecursiveReverse(&(prev -> next)); 
	//RecursiveReverse(&(cur)) <- ptr
	
	// 밑에서 올라오면서 처리
	cur->next = prev; 
	prev->next = NULL; 
	*ptrHead = cur;
}

• "값"은 같지만, "주소"가 다르다.

표현	의미	주소가?
cur = prev->next	cur는 prev->next를 가리킴	cur은 지역 변수
&cur	cur 변수의 주소 (스택에 존재)	🔴 리스트랑 연결 없음
&prev->next	리스트 상에서 실제 next 포인터의 주소	🟢 리스트 구조에 연결됨

• cur는 prev->next 값을 복사한 거고, 그 자체의 주소가 아니다.
  내가 조작하고 싶은 건 'prev->next' 그 포인터 자체니까 &를 붙여야 한다

//수정한 코드
void RecursiveReverse(ListNode **ptrHead)
{
	/* add your code here */
	//empty or len == 1 처리
	if (*ptrHead == NULL || (*ptrHead)->next == NULL){
		return;
	}

	ListNode* prev = *ptrHead;
	*ptrHead = prev->next;

	RecursiveReverse(&(*ptrHead));
	
	// 밑에서 올라오면서 처리
	prev->next->next = prev; //방향 바꿈
	prev->next = NULL; //기존 방향 끊기
}

• prtHead를 재귀 이전에 next를 표시하게 해서 미리 ptrHead를 이어준다.
• 더 직관적이고 보기 좋게 바뀌었다
• 재귀에 들어갈때 마다 cur라는 새로운 지역변수에 복사되어 처리해서 에러가 났었나? 그런 생각을 해본다.
• prev와 cur는 지역변수이기 때문에 재귀함수 하나가 끝나면 사라짐. 유지될 수 있는 인자는 ptrHead뿐.
  

2. Stack & Queue

• 링크드 리스트로 구현한 스택과 큐는 헤드에 붙은걸 빼는 방식.
  • 스택의 경우, push할 때 마다 헤드에 붙음
  • 큐의 경우, enque할 때 마다 테일에 붙음
  • 나오는건 다 헤드에서 나온다.

(1) removeOddValues()

• 큐에서 deque 후 짝수면 다시 큐에 enque

(2) removeEvenValues()

• 스택에서 pop 후 홀수면 임시 스택temp 에다가 넣음
• temp 에서 pop 해서 원본 스택에 push

---

• 스택 큐 문제는 뭔가 쉬웠다? 함수를 다줘서 그런가 체감이 연결 리스트보다 쉬웠다.
• 뭔가 바쁘니까 알고리즘 한 문제라도 풀어서 감을 잃지 말자!

12789 - 도키도키 간식드리미 - 실버3

문제 링크 - 이동

내 코드

   import sys
   
   input = sys.stdin.readline
   
   n = int(input().strip())
   
   line = list(map(int,input().split()))
   
   stk = [0]
   cur = 1
   
   for i in line:
       while(stk[-1] == cur):
           stk.pop()
           cur += 1
           
       if cur == i :
           cur += 1
           continue
       
       if cur < i:
           stk.append(i)
   
   while(stk):
       if cur == stk[-1]:
           cur += 1
           stk.pop()
       else:
           break
   
       
   if stk[-1] != 0:
       print("Sad")
   else:
       print("Nice")

---

• 스택에 들어갔을때 상단과 리스트 현재 보고 있는 부분을 처리하는 아이디어를 구현하는 게 포인트 였던 문제 같다.