c++에서 vector는 ps를 할 때 상당히 많이 쓰는 자료구조입니다. 현업에서는 얼마나 많이 쓸 지 모르겠습니다만, 몰라서 손해를 볼 구조는 아닌 듯 싶습니다. 한 번에 너무 많이 쓰면 내용이 길어질 듯 싶으니, 3편에서 4편에 걸쳐서 쓰도록 하겠습니다. 오늘은, 2차원으로 선언된 2차원 vector를 어떻게 사용해야 하느냐입니다. 보통, 리턴 값이나 파라미터가 강제가 되는 코딩 테스트의 경우, vector 만 나와도 당황할 수 있어요. 오늘은 이것을 어떻게 읽어내고, 만약에 이 2차원 벡터를 리턴해야 할 일이 있을 때 어떻게 해야 되는지만 보도록 하겠습니다. 먼저 읽어내는 것은 그리 어렵지 않습니다. 어짜피 vector의 vector라고 하면, 동적 배열을 담고 있는 동적 배열이기 때문이에요. 이것..
C++ 검색 결과
C++의 sort는 어떻게 O(nlogn)의 복잡도가 보장될 수 있을까요? 저번에 compare 함수가 항상 True를 리턴할 때에 어떤 일이 일어나는가? 편에서 이 함수를 뜯은 적이 있었습니다. 그 기억을 되살려서 보도록 하겠습니다. Quick sort는 pivot을 어떻게 선택하느냐가 중요하다고 했어요. 저번에 median 값을 가지고 pivot값을 생성한다는 것을 알 수 있는데요. 이 방법을 저격하는 데이터가 있다는 것이 알려져 있어요. 그러면 이 방법을 어떻게 해결할까요? nth_element에도 적용되는 기법 중 하나인데요. 호출 깊이의 제한을 둡니다. first와 last가 다른 경우, __introsort_loop를 호출합니다. 그런데, 이것은, 3번째 인자에 이상한 __lg(__last -..
좌표 압축이라는 기술이 있다고 들었습니다. 물론, 저는 ps를 하지 않아서 잘 모르겠습니다. 좌표 압축을 위해서, 중복을 제거해야 하는데요. 그 때 많이 쓰는 함수가 sort + unique + erase 조합입니다. 아마도 그러리라 생각이 듭니다. 물론 set, map도 됩니다만. 이것은 제 전문이 아니니 논외로 하겠습니다. 이 중, unique가 어떻게 동작하는지 이해해 보도록 하겠습니다. cpp reference 코드에 나온 코드는 아래와 같습니다. 아. 보기만 해도 힘드네요. 일단, result, first, last 세 개가 있습니다. 이 셋을 기준으로 보도록 하겠습니다. 보통 unique를 쓰실 때, unique(v.begin(),v.end()) 이런 식으로 쓰실 거니, last는 자료구조의 ..
안녕하세요. chogahui05입니다. sort 함수의 비교 함수를 작성하실 때, strict weak ordering을 만족하게 작성하여야 한다는 말을 많이 들으셨을 거에요. 그렇게 작성하지 않으면 어떻게 될까요? 라는 질문은 사실 별로 의미가 없어 보입니다. 비교 함수가 무조건 true를 리턴하게 작성이 되었을 때 어떤 일이 일어날까요? 너무 멍청한 코딩인가요? 처음 비교함수를 작성하실 때, 이런 식으로 코딩하시지 않으셨나요? 위와 같이 작성이 되었을 때, 어떤 일이 일어날까요? 사실 배열에 들어간 데이터들을 보았을 때, 이 경우도 무조건 compare 함수가 true를 리턴하게 되어 있어요. 똑같은 상황인 셈입니다. se.cpp입니다. 이 프로그램의 내용을 봅시다. 이 경우에 프로그램이 어떻게 실행..
string의 c_str 함수는 제가 string을 C style의 문자열로 바꿀 때 많이 썼던 함수입니다. 이 메서드는 const char *를 리턴합니다. 내용이 변경되면 안 되는 제약 조건을 가진, char형 포인터를 리턴합니다. 일단, string의 구조에 대해서 간략하게 설명을 하고, c_str()에 대한 설명을 하도록 하겠습니다. Stri uffer, StringBuilder, C++의 String 등이 있습니다. C++의 스트링 클래스에는 capacity와 size가 있는데요. 이는 동적 배열이 있는 Class는 보통 이 두 메서드를 구현을 많이 하는 편입니다. append 100만번 하면 시간이 오래 걸리는지 안 걸리는지 체크만 해도 되고요. 실제로 내부 구조를 보면, string 클래스 ..
최근댓글