케이스윔의 개발 블로그

와 방금 알고리즘문제를 풀다가 모르는 부분이 있어서 아는 선배한테 물어봤는데 너무 신기한 알고리즘아닌 알고리즘을 들었다. 그 문제를 풀기위해 필요한게 c++에서는 해시맵이라고 친절히 알려주셔서 오늘은 해시맵 관련 컨테이너들을 공부하도록 하겠다! (이 글을 써둔게 2018.5.17 였는데 이어서 추가 및 수정한다.) 해시맵은 연관 컨테이너 중 하나이다. 예를 들어 vector나 list와 같은 컨테이너는 순서에 따라 값을 저장하지만 연관 컨테이너는 어떠한 key와 짝을 이루어서 값을 저장한다. 따라서 값을 넣고, 찾을 때에는 key가 필요하다! 대량의 자료를 저장하고 빠르게 검색하기 위해 사용된다고 한다. hash table을 만들어두면 O(1)로 검색을 할 수 있듯이 비슷한 것같다.(아니 그 개념을 적용..

STL의 여러 컨테이너를 사용해보면서 내부적으로 어떻게 구현이 되어있는지에 대한 고민을 해보지 않았던 것 같다. 그래서 vector를 사용해서 push_back()을 할 때에는 당연히 삽입이므로 시간복잡도가 O(1)일 거라 생각했다. 이번에 한 문제를 풀면서 O(N)이라는 걸 알게 됐다. STL에서 삽입, 삭제에 시간복잡도가 O(1)로 사용할 수 있는 컨테이너는 list다. list는 들어만 보고 vector나 queue를 쓰면 되니까 크게 필요성을 느끼지 못했었다. 그런데 시간복잡도에 대한 고려를 해보면서 시간제한이 있는 문제를 풀 때는 list를 써야된다는 것을 알았다. list 는 시퀀스 컨테이너이고, 노드 기반의 컨테이너이다. (vector와 deque는 배열 기반 컨테이너)따라서 list는 중간..

작년부터 C++공부를 해야지 하고는 벡터나 큐와 같은 STL만 공부했었는데 드디어 C++에서의 표준입출력을 공부한다!입출력 할 때에 타입이나 이런거에 대한 명세없이 사용할 수 있다고 들어서 편하다는 걸 알면서도 계속 scanf와 printf만 썼다. 이제 좀 새로운 걸 받아들이는 것을 거부하지 말아야겠다 ㅠㅠ C++에서도 헤더파일 cstdio을 통해서 C언어에서 제공하는 함수들을 사용할 수 있다. 하지만 이제는 cin과 cout을 써보도록 하겠다!cin과 cout을 위해서는 iostream 을 헤더파일로 포함하고 std name space를 사용해야한다. cout은 cout

오늘 공부하고 사용해볼 부분은 c++의 pair 클래스 이다. 말 그대로 쌍을 표현할 때 사용을 하는데, 두개의 객체를 하나의 객체로 취급할 수 있게 묶어주는 클래스이다. 앞에 벡터를 이용해서 여러문제를 풀 때 두개의 int형을 하나의 객체로 쓰고 싶을 때 pair를 공부하지 않아서 구조체로 정의해서 썼었는데 오늘 이후로는 pair를 이용해서 문제를 푸는 데 도움이 될 것 같다. 기본적인 부분에 대해서 차례대로 정리를 해보겠다.헤더파일은 utility에 존재한다.pair p; 를 통해 해당 타입의 클래스 p를 선언한다.pair ptr; 와 같이 이차원 좌표평면에서의 좌표를 나타낼 수 있도록 사용해볼 수 있다.pair 클래스를 위와 같이 정의한 다음 p = make_pair(변수1, 변수2); 를 통해 변..

오늘 공부할 부분은 STL(Standard Template Library)의 우선순위 큐(priority queue)이다. 우선순위 큐는 말 그대로 큐이지만, pop을 할 때 가장 큰 값이 빠져나온다. 또는 임의의 우선순위를 주는 함수를 만들어서 해당 우선순위에 해당하는 값이 먼저 pop 하여 사용할 수 있다. 차례대로 선언방법과 기본적인 사용법을 알아보겠다.헤더 파일은 queue를 사용한다.선언은 priority_queue pq; 와 같이 한다.pq.push([input]); 와 같이 값을 넣는다.pq.pop(); 을 수행하면 우선순위가 가장 높은 값이 빠져나온다.(위의 선언에서는 가장 큰 값이 빠져나온다.)pq.empty(); 를 통해서 우선순위 큐가 비어있는지를 확인할 수 있다. 비어있다면 1이 반..

DFS는 vector로 구현도 해보고 문제도 몇개풀어봤으니 이제는 queue로 BFS를 구현해보려한다 DFS는 한 우물만 계속해서 파니까 쭉쭉 들어가기위해서 스택이 필요했고, BFS는 짧게짧게 갈 수 있는 모든 곳을 들러야하니까 FIFO(선입선출)인 큐가 필요하다 1. queue의 사용 #include을 해줘야한다queue Q; : int형으로 Q라는 이름의 큐 선언Q.push(값) : 해당값을 큐 Q에 넣는다Q.pop() : 큐 Q의 front를 삭제한다Q.front() : 큐의 제일 앞 값을 리턴한다(삭제되지않음)Q.back() : 큐의 제일 마지막 값을 리턴한다(삭제되지않음)Q.size() : 큐 Q의 원소 개수를 리턴한다 Q.empty() : 큐가 비어있는지를 확인한다. 비어있으면 1 비어있지않으..

백준 2294번 문제를 푸는데 int형으로 배열을 선언하니 범위가 벗어나서 답이 틀렸다고 나왔다. 그래서 오랜만에 검색해서 데이터 타입을 찾아봤다. - int, long long 둘다 정수형 데이터 타입이다. - int 는 32비트 정수형이고 (-2,147,483,648 ~ 2,147,483,647) - long long(signed long long)은 64비트 정수형이다 (-9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 )- long long 타입을 출력할려면 %lld, %lli, %llo, %llu, %llx 중에 사용하면된다. * 사실 써본적이 없었는데 방금 문제풀면서 처음 써봤다. 문제를 풀 때 연산에 필요한 정수가 10억정도를 넘어갈 것 같을때..

구현하기에 어렵지 않지만 계속해서 자주 써야하니까.. 귀찮으니까.. 1. c에서는 기본적으로 제공하지 않기때문에 삼항연산자로 가장 깔끔하게 쓰는방법 #define min(x, y) (x) x, y중에 작은값 반환#define max(x, y) (x) > (y) ? (x) : (y) -> x, y중에 큰값 반환 2. c++에서는 라이브러리로 제공 #includemin(a, b) -> a와 b중 작은값 반환max(a, b) -> a와 b중 큰값 반환