그간
마지막 업데이트로부터 많은 것을 배웠다. 자바스크립트 고급 문법을 마무리하고 jQuery를 공부했다. jQuery를 이용해 영화진흥위원회 API와 카카오 이미지 검색 API를 활용한 일일 박스오피스 웹앱도 작성했다.
강의는 강의대로 들으면서 정처기 필기 공부와 알고리즘 공부도 틈틈히 했다. 그렇지만 하루에 하는 것이 많을수록 TIL 쓰기의 부담은 컸다. 그동안 하루 공부 내용 중에서 인상깊었던 것, 어려웠던 것을 재차 정리하는 방식으로 TIL을 정리했기 때문인 것 같다. 하루가 끝나가는 마당에 새로운 글을 시작하는 것은 적지 않은 부담이 되었다.
앞으로는 배운 것을 약술하여 소개하고, 공부하던 중 작성한 필기나 메모를 링크하는 방식으로 간단하게 TIL을 쓰려고 한다. 느낀 점이나 학습의 방향과 같이 주관적인 내용을 늘리고, 이미 필기로 정리해놨던 학습 내용은 걷어내어 부담을 줄여본다.
연결리스트
자바로 알고리즘 문제를 푸는 것이 번거로운 점이 많아서, 알고리즘 한정으로 C++을 다시 쓰기로 했다. 바킹독의 알고리즘 강의도 다시 듣기 시작했다.
오늘은 연결 리스트(Linked list)를 공부했다. 메모리 상에 연속적으로 데이터를 저장하는 배열과 달리, 각 노드에 대해 이전 노드와 다음 노드의 메모리 주소를 기록하여 논리적으로 연속적인 데이터 구조를 구현하는 것이 연결 리스트이다.
연결리스트는 임의의 위치에 새로운 노드를 추가하거나, 특정 위치의 노드를 제거할 때의 시간복잡도가 O(1)이다. 배열은 노드를 추가할 때 빈 공간을 만들기 위해 특정 위치부터의 모든 노드를 한 칸씩 옮겨야 하며, 삭제할 때에는 빈 공간을 없애기 위해 끝 노드부터 특정 위치까지 한 칸씩 올겨야 하므로 시간복잡도가 O(N)이 된다.
따라서 중간 위치에서 데이터의 삽입과 삭제가 많이 일어나는 에디터 등을 구현해야 할 때 적용할만 하다.
관련 문제로 백준 1406번을 풀었다. 연결리스트를 (간략화 버전으로) 직접 구현하여 풀어보기도 했고, CPP의 list 라이브러리(연결 리스트의 구현체)를 이용하여 풀어보기도 했다.
전반적으로 어렵지 않게 해결할 수 있었으나, list 라이브러리를 사용한 풀이에서 어려움을 겪었다. 계속해서 예기치 않은 세그먼트 오류가 발생했고, 디버거를 켜보니 데이터를 삭제(erase)하는 부분 이후 다시 데이터를 추가(insert)할 때 오류가 발생하였다. 고민해보니 삭제 부분에서 수정이 필요함을 알 수 있었다. 삭제 부분은 기존에 아래와 같이 구현했다.
// list<char> li;
// } else if (cmd == 'B') {
li.erase(cursor);
// }
멤버 함수인 erase를 호출하고 다른 처리는 하지 않았는데, 문제는 삭제 후에도 이터레이터(cursor)의 값이 변경되지 않았다는 점이다. if문을 나간 후 다음 for문으로 들어왔을 때, 이터레이터는 여전히 삭제된 항목의 위치를 가리키게 된다. 따라서 이후 해당 이터레이터로 리스트에 접근하면 오류가 발생하는 것이다.
// list<char> li;
// } else if (cmd == 'B') {
if(cursor != li.begin()) {
cursor--;
cursor = li.erase(cursor);
}
// }
이 문제는 위와 같이 수정하여 해결해야 한다. erase 멤버함수는 리스트에서 해당 이터레이터에 해당하는 데이터를 삭제한 후 그 바로 다음 데이터 위치에 해당하는 이터레이터를 반환한다. 이후 반환받은 이터레이터를 참조하면 safe한 처리가 가능하다.
양방향 텍스트로서의 프로그래밍 언어
로버트 나이스트롬(Robert Nystrom)의 Crafting Interpreters를 읽기 시작했다.
얼마 전 자바스크립트의 클로져 개념을 공부하는 도중, 답답한 마음에 V8 엔진의 소스코드를 뜯어보려고 시도했다. 자바스크립트 엔진은 클로져를 어떻게 처리하는지 궁금했기 때문이다.
결과는 실패였다. 코드는 너무나도 방대했고, 문서는 소스코드 자체를 설명해주는 글이 아니라 소스코드를 빌드하여 라이브러리로 활용하기 위한 방법을 안내하는 가이드같았다.
그러나 완전히 허탕을 친 것 만은 아니다. 이를 계기로 프로그래밍 언어로 씌여진 소스코드가 양방향의 텍스트라는 것을 자각하게 되었다. 코드는 1차적으로 1인 이상의 개발자가 쓰고 읽는다. 그러나 그 전에 코드는 컴퓨터에 대한 명령문이다.
즉, 코드는 두 부류(인간과 기계)의 독자를 염두에 두고 쓰여지는 텍스트라는 점에서 양방향 텍스트라고 할 수 있다. 우리는 컴퓨터가 처음 개발된 당시, 즉 이진 코드로 직접 장치를 제어했던 시대를 겪지 못했기 때문에 쉽게 자각하지 못하지만 말이다.
현재의 프로그래밍 언어는 인간과 기계가 모두 참조할 수 있는 공통의 텍스트를 만들기 위한 선배 개발자들의 노력의 결과물이라고 할 수 있다. 이들은 두 목적을 모두 실현하기 위해 정형화된 형식에 의해 조직되는 형식적 언어로 프로그래밍 언어를 구성하게 된 것이다.
다시 말해, 결과적으로 프로그래밍 언어는 양방향으로의 번역이 모두 용이한 중간 형태를 띄게 되었다. 개발자는 이진 코드를 직접 작성하는 것보다 적은 노력을 들여 소스코드를 작성하고 읽을 수 있으며, 컴파일러나 인터프리터를 통해 소스코드를 변환하기만 하면 기계도 그 명령을 수행할 수 있다.
자바스크립트와 정처기에 신물이 났던 모양인지 이 일련의 과정에 관심이 꽂혀서, 오토마타 이론과 컴파일러에 대한 자료를 마구 찾아보기 시작했다. 그러나 당장 내일 Vue.js 수업을 듣게 될 예정인 문과 비전공자 입장에서는 진입장벽이 너무 높았고, 대신 후기가 좋은 나이스트롬의 책을 읽어보려고 한다.
이 책은 Lox 언어 인터프리터를 단계적으로 직접 개발해보는 내용을 담고 있다. Lox 언어는 저자가 디자인한 것으로, 자바스크립트와 비슷하게 생긴 C Family 프로그래밍 언어이다. 나를 괴롭혔던 클로져를 구현하는 내용도 실려있다. 하나 하나 실습해보고 소소하게 정리해보자.