최신글
-
[42서울] ft_containers[4] - 맵 구현
서론 key-value의 형태의 pair를 정렬된 순서로 저장하는 컨테이너. 각 key는 전부 고유한 값을 가지며, 검색과 삽입 삭제가 전부 O(log n)으로 효율적이다. 내부의 자료구조가 tree(주로 rbtree)로 구현되어있다. 서브젝트에서 얘기하듯이 배열 같은 ‘적합하지 않은’ 자료구조로 구현해서는 안되며, 20배 이상 차이가 나면 안 된다고 되어있기 때문에 BST 같은 지나치게 단순한 tree를 선택해도 안되고 자체적으로 밸런싱 기능이 있는 tree를 자료구조로 사용해야 한다. 맵의 항목들을 보면서 필요한 함수들을 트리에 구현하면 조금 더 편하다. 들어가야 하는 구성요소 Member types key_type: 맵의 키(Key) 유형 mapped_type: 맵의 값(Value) 유형 value..
더보기
-
[42서울] ft_containers[3] - 트리 구현
서론 원래 rbtree를 이용해서 구현하고 싶었는데, 제대로 이해하지 못한 상태로 대충 구현하고 나서 테스트를 해보니 map의 테스트에서 일부분 문제가 생겼다.(어느 부분인지는 map에서 설명) 내가 그걸 못고치는걸 보면서 이건 내가 이해한게 아니라고 생각해서 다른 bst를 찾아봤는데, splay tree라고 하는 간단하게 밸런싱을 하는 트리를 발견해서 그걸로 구현했더니 역시 문제가 생겼다. splay tree는 선형 체인에서 O(n)이어서 30만 개 선형 체인 테스트를 std::map보다 20배 이상 느려져서 통과하지 못했다. 그래서 그냥 힙스터 기질은 접고 다른 사람들처럼 avl tree로 구현하게 되었다. https://www.cs.usfca.edu/~galles/visualization/AVLtr..
더보기
-
[42서울] ft_containers[2] - 벡터 구현
서론 https://jhnyang.tistory.com/230 [자료구조STL vector 1탄]벡터란? 배열 vs 벡터 비교/장단점/ 특징, 다양한 백터 선언 및 초기화 방법, 안녕하세요 오늘은 C++ 자료구조 컨테이너 중 하나인 vector 라이브러리에 대해 살펴봅시다. [1탄 목차] 1. 벡터란 무엇인가? 2. 벡터의 구조와 특징 (장단점) 3. 언제 벡터를 사용하는가 4. 벡터를 사 jhnyang.tistory.com 동적 배열구조 클래스. 배열이지만 크기를 자유자재로 수정할 수 있는 배열이라고 생각하면 된다. 동적으로 메모리를 늘려주기 때문에 편해서 배열보다 더 자주 쓰인다. 각각의 원소를 [] 연산자를 통해 쉽게 접근할수있고, 임의의 순서로 메모리에 접근가능하다. 단점은 중간에 많은 데이터를 ..
더보기
-
[42서울] ft_containers[1] - 스택 구현
서론 스택이란 LIFO(last-in first-out 후입선출)로 동작하는 자료구조로, cpp module에서(그리고 조금 다르지만 푸시스왑에서) 이미 가볍게 다뤄봤듯이 컨테이너의 한쪽 끝에서만 입력하고 출력하는 자료구조이다. 다른 컨테이너를 가져와서 그 컨테이너 위에서 동작하도록(캡슐화) 되어 있는데, 이 과제에서는 내가 만든 벡터를 이용하여 구현해야 한다. 하지만 우선 std::vector를 사용하여 구현을 먼저 하고 나중에 내가 만든 ft::vector로 바꾼 다음 정상적으로 동작하는지를 확인하면 될 거라고 생각했다. 이게 가장 쉽기도 하지만 구현 내용 자체가 많지 않고, 서브젝트상 추가로 구현해야 하는 내용이 없어서 가장 마음 편하게 접근할 수 있을 거라고 생각한다. 아래 기능을 지원하는 컨테이..
더보기
인기글
-
[42서울] 철학자(Philosophers)에게 밥을 먹이자
서론 이번 과제는 생각보다 오래 걸려서 8~9일 정도 소요되었던 것 같다. 완성은 해놓고 집에 내려갔다 오느라 블랙홀 2일 남기고 평가를 받았는데, 내 코드를 4일 만에 다시 봄 + 평가에 문제 생기면 블랙홀 12시간 남기고 재평가받아야 함이라는 두 가지 요소로 인해 평가 내내 정신이 나갈 것 같았다. 다음부터는 이런 식으로 평가받지 말아야겠다. 철학자 과제는 운영체제에서 유명한 문제인 "식사하는 철학자 문제"를 직접 구현해보는 과제이다. 식사하는 철학자 문제는 대표적인 “동시성 제어” 문제로 하나의 젓가락(또는 포크)를 두 명이 동시에 잡지 못하도록 하면서(상호 배제), 각자 하나의 젓가락을 들고 다른 사람의 젓가락을 요구하는 데드락을 피해야 한다. 상호 배제는 뮤텍스를 통해서 구현하고, 데드락은 예방..
더보기
-
[42서울] 미니쉘(minishell) 파싱, 그 후회와 참회의 기록.
서론 라 피씬 이후에 처음으로, 코드에 한이 맺히고 내가 이 길을 가는 게 맞나 하는 생각이 한 번씩 들 정도로 힘든 과제였다. 평소와 달리 코드의 깔끔함을 추구하지 못하고 3천 줄이 넘는 코드를 리팩터링 할 엄두가 안 나서 그냥 제출했다. 가장 크게 실수했다고 생각한 부분은 코드를 짤 때 처음부터 norminette 규정을 생각하고 만들었어야 했는데, 먼저 코드를 만든 다음에 노미넷을 지키려고 한 부분과 구조에서 문제가 발생했을 때 바로 갈아엎었어야 했는데 계속 하나씩 수정하다가 나중에는 갈아엎기도 애매하고 계속 수정하기도 애매한 구석에 밀렸던 게 후회된다. 그런데 지나고 나서 생각을 해보니 이런 부분들이 결국 내가 스스로 불러온 재앙이었다는 걸 알게 되었다. 그래서 그 부분들을 중심으로 미니쉘 과제의..
더보기
-
[42서울] CPP Module 01 - 클래스와 레퍼런스
서론 cpp 과제는 과제보다 평가가 두배는 더 힘든 느낌이다. 평가받아야 하는 횟수 자체도 압도적으로 많은데, 카뎃 대부분은 C++을 모르다 보니 설명을 하려면 굉장히 먼데부터 설명해야 한다. 본론으로 들어가면, cpp module 01 과제는 제목에서처럼 클래스와 레퍼런스를 사용해보는걸 중점으로 하고 있다. 객체 지향 언어의 기본이자, C++의 꽃이라고 할 수 있는 부분이기 때문에 깊게 공부할수록 좋다. ex00 Zombie 클래스를 만든다. 디버깅, 평가 등을 위해 소멸자에 메시지를 넣는다. Zombie 클래스에는 본인의 이름과 BraiiiiiiinnnzzzZ... 를 출력하는 announce 기능이 있다. Zombie가 적절할 때 소멸되도록 만들고, 그에 따라 스택 영역과 힙 영역에 할당하도록 한다..
더보기
-
[42서울] CPP Module 04 - 다형성과 추상클래스
서론 서브젝트 첫 페이지에 나오듯이 다형성과 추상 클래스, 그리고 인터페이스를 구현해보는 과제이다. 여담으로 cpp 03 이후에 04부터 08까지 한번에 끝낸 다음에 평가를 받았는데, 평가를 받으면서 보니 별로 좋은 생각은 아니었다. 평가를 받으면서 무슨 생각으로 이렇게 만들었는지를 까먹고 평가자와 같이 고민하게 되는 큰 문제가있었다. ex00 모든 exercise에서는 최대한 완벽한 테스트를 제공할 수 있도록 노력해야 한다. 모든 생성자와 소멸자는 클래스에 따라 다른 이름이 나와야 한다. 시작은 Animal 클래스 하나만 구현한다. protect로 string 타입의 type 변수 하나만 보유한 클래스이다. Dog 클래스와 Cat 클래스를 만들어서 각자 이름에 맞는 type를 가지도록 한다. Dog는 ..
더보기