[2일차] Linked List

오늘 내용은 Linked List였다. 어제 비트 연산에 배울 때도 당연히 다 아는 내용이라고 무시하기에는 뭔가 확 와닿는 게 있었는데 오늘도 그런 포인트가 좀 있었다.

 

알고리즘 문제 푸는 테크닉을 몇개 배웠다. 가장 인상 깊었던 것은 링크드 리스트의 노드를 할당할 때 사용하는 메모리 풀이었다. 메모리 풀은 알고리즘 시간에 배워서 알고 있었지만 그때는 메모리 풀을 모두 사용하면 동적 할당하고 해제는 free 함수를 호출하는 것이 아니라 그 주소 공간을 메모리 풀에 돌려주는 식으로 구현했었다. 따라서 최악의 경우엔 매번 malloc을 호출해야 했다. 하지만 오늘 배운 방법은 아예 모든 공간을 정적으로 잡아두고 할당하는 방식이었다. 리스트 노드 구조체를 저런 식으로 사용하는 방법도 있구나 싶었다.

 

리스트 순회할 때 segmtation fault가 발생하는 것을 막기 위해 리스트에 dummy node를 넣어서 문제가 발생하는 것을 막는 것도 배웠다. dummy node를 안 넣으면 순회할 때 매번 null인지 확인해야 하는데 dummy node를 넣어주면 귀찮게 매번 확인할 필요가 없다.

 

SWEA에서 리스트 기초 문제를 2개 풀었다. 하나는 single, 또 하나는 double linked list를 구현하는 문제였다. 문제자체는 따로 새로운 것을 생각하는 것은 아니었지만 리스트 자체를 오랜만에 구현하다보니 segmentation fault가 몇번 발생해서 해결하는데 시간을 좀 썼다. 또 리스트를 응용하는 문제도 2문제 더 풀었다. 한 문제는 디버깅이 조금 어렵게 되어 있어서 고생을 했다. 추가로 백준도 한문제 풀었는데 이 문제도 corner case를 처리하는데 힘들었다.

백준 문제

[BOJ] 23309 철도 공사