IT 방랑기

1. Hash란? Hash 함수는 어떤 값의 범위를 다시금 0~X까지로 매핑하는 역할을 수행한다. 이러한 Hash 함수의 역할을 통해서 범위에 비하여 값이 너무 sparse했던 애들을 압축할 수 있다. 혹은 전체 범위 중 특정 값에 몰려 있던 것을 퍼트리는 역할도 수행하 수 있다. 예를 들면 어떤 값은 알파뉴메릭 최대 30자 문자열이 10만개 있다고 하자. 그러면 이 값의 범위는 a-zA-Z0-9이므로 62^30승 ~= (2^6)^30 ..... 그렇다고 이 값을 full scan하기에는 최악의 경우에는 10만 * 30자 총 300만번의 search cost가 발생한다. 그러나 해당 문자열 값을 hash 함수를 이용하여 5000개로 나누어 담을 수 있다면, 한 해쉬 값당 20개씩 문자열이 저장된다. 그렇..

1. 단방향 Linked list Linked list는 하나의 단위로 구성된 Node에 다음 혹은 이전의 Node에 대한 주소 값을 저장하여 연결하는 list를 뜻한다. 배열과 달리 서로 인접하지 않은 메모리 영역에 노드를 저장할 수 있다. 또한 다음 값을 저장하고 있기 때문에 추가나 삭제시에 해당 값만 변경하면 되는 잇점이 있다. 물론 장점만 있는 것은 아니다. 만약 정렬된 상태일 때 배열의 경우 binary search와 같은 기법으로 O(n)의 탐색 시간을 O(logn)까지 떨어트릴 수 있지만, linked list의 경우 full scan을 해야 한다. 물론 여기서도 역량테스트 (Certi) B형(Pro) 기준으로, malloc과 같은 동적 할당 없이 구현한다. (free도 없다.) 2. 기본 ..

삼성 SW 역량테스트 B형/Pro 대비 - C, C++ 큐 만들기 1. 큐 큐는 First In, First Out 자료 구조로, 입력된 순서대로 출력되는 자료구조이다. 역량테스트 (Certi) B형(Pro)에서는 STL 사용이 불가능하고 최적화하는 단계가 필요하기 때문에 동적 할당 없이 전역으로 처리해야한다. 2. 기본 구조 함수 동작 Push 큐에 넣기(push back) Pop 큐에서 빼기 (pop front) Size 크기 반환 Empty 비어있는지 여부 반환 일반적으로 Pro(B형)에서는 속도에 따른 제한을 많이 두기 때문에 활용할 수 있는 최대한의 크기를 잡고, 큐가 오버플로우 되지 않음을 가정하고 작성한다. 3. 소스코드 #include #define Q_SIZE 5 int st, en; t..