크래프톤 정글 4, 5주차 회고

TWIL이 계속 밀리고 있는데..🙁 글 하나에 너무 많은 걸 담으려다 보니 포스팅 완성하는 데 시간이 오래 걸리는 게 원인인 것 같다.. 앞으로는 TIL 작성하는 방식으로 바꿔야겠다..! 일주일동안 배운 내용을 하루동안 쓰는 건 생각보다 더 많은 시간과 노력을 들여야 하는 어려운 일이라는 것을 알게 됐다 ㅠ

 

4주차

• 알고리즘 마지막 주차! 동적 프로그래밍과 그리디 알고리즘 관련 문제들을 풀었다.
• DP의 경우, 2주차에 풀어봤던 LIS 유형과 점화식을 쉽게 찾아낼 수 있는 유형(백준 1904. 01타일)은 그래도 금방 풀 수 있었다. 하지만 전형적인 DP 문제임에도 불구하고 접근법을 알지 못해 헛다리만 짚다가 결국 구글링을 하거나 CLRS 책에서 이론부터 학습한 문제가 더 많았다.
  • 백준 9084. 동전 문제와 12865. 평범한 배낭 문제의 경우 그리디로 접근하는 동전 문제와 분할가능 배낭문제와 비슷하겠거니 하고 무식하게 덤벼들었다가 시간 좀 날렸다. 그래도 구글링한 덕분에 2차원 표로 그리면서 점화식 찾는 방법에 대해 새로 알게 되었다.
  • 11049. 행렬 곱셈 순서, 9251. 최장 공통 부분 수열 문제의 경우에는 CLRS 및 기술블로그에서 기본 개념과 접근 방식 먼저 학습했다. 학습한대로 코드를 작성하고 제출도 했지만 문제를 풀었다기보다는 새로운 것을 '배웠다'는 느낌이라.. 따로 학습 안했으면 접근 방식을 떠올리지 못했을 것 같아서 필요한 과정이긴 했지만, 다음에 또 비슷한 문제를 보면 그땐 진짜로 '문제를 풀고' 싶다!
• 그리디의 경우에는 DP에 비하면 덜 어렵게 느껴졌다.
• 일단 4주차는 문제가 그렇게 많지는 않았고, 난이도 상 문제 2개는 보류해두었기 때문에 문제풀이를 다른 주차보다 빨리 마무리를 할 수 있었다.
  • 상 문제 중 하나인 외판원 순회 문제는 최소 하루는 투자해야 어느 정도 이해를 할 수 있을 것 같았고.. 당장 C언어가 급했기 때문에 어쩔 수 없이 버리고(어쩌면 내가 외판원 순회 문제에게 버려진 걸지도!?) 월요일부터 본격적으로 C언어 학습에 들어갔다.
• 여기 들어오기 전 한 달 전부터 C언어 공부를 시작했었는데, 30일 동안 학습한 페이지 수보다 10일 동안 학습한 페이지 수가 훠어어얼씬 많았다.
• 화요일에는 이행적 폐쇄 알고리즘에 대해서 학습했다. 기괴한 네이밍에 지레 겁먹긴 했지만 CLRS 책에 설명이 다 있었고, 구현 논리 자체는 그 이름만큼 기괴하지는 않아서 괜찮았다. 이 알고리즘을 이해하기 위해 필요한 수학 개념들도 CLRS 책에 부록으로 다 설명이 되어있어서 좋았다.

 

5주차

• 레드블랙 트리의 이론에 대해 학습하고 C언어로 직접 구현해보는 게 목표였다.
• 레드블랙 트리의 이론을 빠삭하게 알고 갈 수 있다면 너무 좋았겠지만.. 일주일 안에 C언어의 기본적인 문법은 물론이고 포인터, 동적 할당, 구조체 개념을 학습하고 사용법을 익히는 것까지 모두 진행하기엔 시간과 체력이 허락하지 않을 것 같아서 둘 중 하나는 힘을 덜 들일 수 밖에 없었다. 레드블랙 트리와 C언어 중 C언어를 좀 더 비중있게 학습하기로 했다.
• 코드 자체는 CLRS에 다 있어서 .. 옮겨적기만 하면 되는 것이었지만 pseudo 코드여서 C언어에 대한 이해가 필요했다. 개념 학습 후에 코드 옮겨적을 때 노드 삽입 쪽에서 살짝 시간이 걸렸는데, 삽입 함수 내에서 새로운 노드를 생성할 때 동적 할당을 쓰지 않았던 것이 문제였다.
  • 동적 할당을 하지 않고 냅다 노드 삽입 함수 내에서 노드 구조체 변수를 선언해버려서 해당 노드가 스택에 저장된 것이 1차적 원인이었다. C언어 교재에서 지역 변수는 스택 영역에 저장된다!는 문장을 봤을 땐 당연하게 받아들이고 그냥 넘어갔는데, 왜 실전에선 이 점을 놓쳤던 것일까?
  • 그 배경에는 자바스크립트가 있었다. 나는 C언어의 구조체를 자바스크립트의 객체와 비슷한 개념이라고 (내 마음대로) 생각하고 있었다. 그리고 자바스크립트의 객체는 전역 변수로 선언하든 지역 변수로 선언하든 힙 영역에 저장된다. 그래서 구조체도 자스의 객체 쓰던 것처럼 그냥 별 생각없이 지역 변수로 선언해버린 것이다. C언어의 구조체는 그 크기가 정해져있는 반면에, 자스는 동적 타이핑 언어로 객체의 크기를 사전에 알 수 없어 힙 영역에 저장한다.
  • 무튼 이렇게 하면 이 함수가 종료될 때 해당 변수가 가리키는 노드 구조체가 메모리 영역에서 단순히 '제거'된다고 생각할 수 있겠지만 그건 아니었다. 일단 내 경우에는 삽입 함수를 처음 실행했을 때의 노드가, 동일한 함수를 두 번째 호출했을 때도 살아있어서 소름끼쳤다.(그 와중에 두 번째 노드의 행방은 불명..;) 그리고 만약 값 자체가 스택에서 제거된다고 하더라도, 제거하는 주체가 누구지? 그런 식으로 제거한다면 쓰레기 값들은 왜 있지?하고 어리둥절했는데 팀원분과 함께 인터넷에서 서치해본 결과는 다음과 같았다. : 함수가 실행되면 스택 영역이 증가하고 함수가 종료하면 스택 영역이 줄어드는데, 이때 줄어들기 전의 공간에 있던 값을 0으로 초기화를 한다거나 하는 작업은 이 시점에는 따로 하지 않는다. 그리고 함수가 또 호출되면 스택 영역이 또 증가하는데, 이때 기존에 남아있던 값(사실상 쓰레기 값인..?)에 다시 접근하게 되어서 그런 문제가 발생한 게 아닐까?하고 추측 중이다.
  • 결론적으로는 이런 이유로 노드가 트리에 정상적으로 삽입이 되지 않으면서도 에러도 발생하지 않았던 것이다.
  • 더 공부가 필요한 개념:
    • 자바스크립트 언어 단에서 메모리 관리가 구체적으로 어떻게 일어나는지
    • C언어의 메모리 동적 할당 및 반환
    • 메모리 구조