준카판다

https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 이 문제는 두가지 방법으로 해결하였다. 첫번째는 문제 이름이 집합이길래 set으로 풀었다. 하지만, set보다 더 간편한 방법이 있었다. 어렵지만 쉬운 방법이다. 사실은 문제를 해결하고 나서 알고리즘 분류를 확인해보았는데, 당연히 set자료구조 일줄 알았지만, 처음보는 생소한 단어가 나를 맞이했다. 비트마스킹이라고 나와있었다. 검색을 해보니 집합을 비트로 표현할 수 있는 방법이 있었다. 예전에 자료구조 강의에서 비트맵이라고 주워들은..

https://www.acmicpc.net/problem/7785 7785번: 회사에 있는 사람 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 www.acmicpc.net 문제는 무난하다. 다만 새로운 자료구조를 만나서 작성한다. 문제를 보고 나는 생각했다. 삽입과 삭제의 비용이 적은 자료구조는 무엇일까? 우선 list 삽입의 경우 O(1)이지만 삭제는 O(n)이다.(연결구조이기 때문에 순차접근이다.) vector의 경우 삽입은 O(1), 삭제는 O(n)이다. (배열형태로 삭제를 하면 뒤에있는 요소를 댕겨줘야 한다) list의..