J.Althea

문득, 트리 구조(Tree)로 이루어진 set과 해쉬 테이블(Hash Table)로 이루어진 unordered_set의 속도 차이를 손쉽게 경험할 수 있을 것 같아서 기존의 코드를 수정하고 제출해보았다. * 수정 전 실행 결과(set을 이용) : * 수정 후 실행 결과(unordered_set을 이용) :  모든 테스트 케이스에 대해서 유의미한 속도 향상을 보였다. 아래는 수정한 코드이다. https://github.com/JAlthea/Algorithm/blob/master/BFS/Programmers%20%EB%B8%94%EB%A1%9D%20%EC%9D%B4%EB%8F%99%ED%95%98%EA%B8%B0.cpp #include <vector> #include <queue> #include <unordered_set> #include <algorithm> using namespace std; struct hashFuction {     size_t operator()(const vector<int> &a) const {         int resultA = 0;         int digit = 1;         for (int i=0; i<4; i++)         {             resultA += a[i] * digit;             digit *= 10;         }         return resultA;     } ...

연속된 데이터를 출력문에 대한 코드를 작성하다보면, 마지막 출력의 경우에는 줄바꿈을 하고 싶을 경우가 있다. for (int i=0; i<n; i++)     if (i == n - 1)         cout << a[i] << "\n";     else         cout << a[i] << " "; 위와 같이 작성하는 경우가 많은데, 이것을 for (int i=0; i<n; i++)     cout << a[i] + " \n "[i==n-1]; 이렇게 바꿔서 작성할 수 있다. const char* tmp = " \n"; 형태로 볼 수 있고,  tmp[0], tmp[1]을 사용하듯이 " \n"[0], " \n"[1]로 보는 것이다. 특정 규칙을 갖는 문자열을 작성해두고, 인덱스를 넣어서 활용하는 방법도 있다. 예) "122333444455555..."[n%k];

map이 내부 구조가 트리(레드-블랙트리) 형태로 되어 있기 때문에 기본 로직에 따라 자동 정렬되므로 logN의 시간이 추가된다. 반면에, unordered_map(hash_map)은 hash-table 구조로 되어 있기 때문에 데이터를 넣어도 자동으로 정렬되지 않으므로 logN의 시간을 아낄 수 있다. 그러나, 내부 hash-function에 의해서 성능이 저하되는 경우에 (특히, 문자열) map보다 오래 걸릴 수도 있다. 정리해보면 기본적인 경우에는 둘 다 'key-value' 형식으로 되어있으므로 key를 이용하여 정렬된 결과를 얻을 것이 아니면 unordered_map을 이용하는 편이 나은 것 경우가 많다. (대부분의 경우의 우리가 원하는 것은 key를 이용해 바로 value를 가져오고 싶기 때문) 물론 경우에 따라서 hash-function을 작성하기 나름이다. 아래 링크는 참고한 사이트 http://veblush.blogspot.com/2012/10/map-vs-unorderedmap-for-string-key.html unordered_map을 적절히 사용하여서 해결할 수 있는 문제는 다음과 같다. (map을 사용하였을 때와 unordered_map을 사용하였을 때, 시간 차이를 느낄 수 있다.) https://programmers.co.kr/learn/courses/30/lessons/60060

C에서의 구조체(struct)는 기존의 개념과 같다. '사용자 정의 자료 구조' 같거나 서로 다른 데이터 타입(구조체 자기 자신도 포함)을 묶어서 사용할 수 있게 한다. C++에서 struct는 기존의 구조체 개념에 더해서 class의 개념까지 갖는다. class처럼 멤버 함수를 가질 수 있고, 상속을 비롯한 나머지 성격을 갖는다. 사실상 C++에서 struct와 class의 차이는 기본 접근 제어자를 빼고는 같다고 볼 수 있다. (struct는 디폴트 값으로 public이고, class는 디폴트 값으로 private인 차이)

각종 언어에서 for문을 어떻게 쓰느냐에 따라 속도가 다른 것들이 있는 것 같다. C++로 예를 들면, //Classic for loop for (int i=0; i<m.size(); ++i)   //Range-based for loop 1 for (auto i : m)     간편하게 쓰려고 위와 같이 사용하기 쉬운데, 저 위의 i는 값 복사로 인해 할당 받은 변수이다. 따라서 기존의 참조하던 방식과 비교해서 속도 차이가 벌어질 수 있다. //Range-based for loop 2 for (auto &i : m) 으로 사용하면 해결된다. 다른 언어에서도 내부 동작은 마찬가지로 생각할 수 있다.