* PS 알고리즘 풀이에서 사용되는 STL Set Container 사용법에 관하여 간략하게 정리해 둔 포스팅 입니다. *잘못된 내용을 포함하고 있을 수 있으며, 수정할 내용이 있다면 댓글로 남겨주세요#1 About STL Set - Set은 수학의 집합 개념을 본따서 설계된 자료구조 이기에 중복을 허용하지 않으며, 다양한 집합 관련 연산 (교집합 _ set_intersection , 합집합 set_union , 차집합 set_difference) 을 제공한다. - STL Associative Container [연관 컨테이너] 에 속하는 set, multiset과 STL Unordered Associative Container [비정렬 연관 컨테이너] 에 속하는 unordered_set , unorde..
https://www.acmicpc.net/problem/11723 #문제접근문제를 제출한 뒤 알고리즘 분류를 보니 "비트 마스킹" 알고리즘을 사용해야 하는 문제였던 것 같다.시간제한이 1.5초인데 반해 연산의 수는 300만 개로 매우 많다.하지만 아직 비트 마스킹 알고리즘에 대해 공부하지 않았기에 set 자료구조를 사용해 문제를 풀이했다.set 자료구조를 사용해 문제를 풀이하기 위해선 가능한 모든 시간 최적화 방안을 도입해야만 했다. set 자료구조 중에 hash table로 구현된 set 을 선택하였다.hash table 은 삽입, 삭제 연산이 O(1) 만에 이루어지기에 다른 set 자료구조에 비해서 효율적이다.물론 문제 출제자가 의도적으로 최악의 해시 충돌을 강제하는 테스트케이스를 다량으로 추가..
https://www.acmicpc.net/problem/9375 #풀이 * Map 자료구조와 조합론을 사용해 풀이하였다. 각 테스트 케이스에서 n개의 의상 이름과 의상 종류가 공백으로 구분되어 주어진다. 이 때 같은 종류의 의상은 하나만 입을 수 있으며, 같은 이름을 가진 의상은 존재하지 않는다. 즉 다음과 같이 테스트 케이스가 주어졌다고 가정 시 hat headgearsunglasses eyewearturban headgear의상 종류를 기준으로 케이스를 분류하면 다음과 같다. {headgear : hat, turban} , {eyewear : sunglasses} 이제 주어진 의상을 가지고 구성할 수 있는 옷의 조합을 구하면 된다.문제에서 핵심 조건은 다음과 같다. 1. 한 번 입었던 옷들의 ..
접근1 문자열 탐색 후 폭발 문자열을 제거해 나가는 방식 입력으로 주어진 문자열 ex) mirkovC4nizCC44 에서 폭발 문자열 ex) C4 이 탐색된다면 기존 문자열에서 폭발 문자열이 탐색되지 않을 때 까지 지속적으로 삭제해 나간다.* 단순 문자열 탐색 O(N^2)* 1. 입력받은 문자열에서 폭발 문자열이 탐색 되는 지 확인* 2. 폭발 문자열이 존재한다하면 해당 문자열을 제거 후, 새로운 문자열 생성* -> 문자열이 비어 있거나, 폭발 문자열이 존재하지 않을 때 까지 다음 동작을 반복. 위와 같은 방식은 문자열 내부에서 폭발 문자열을 탐색하는 과정에서 for 문이 2번 중첩 되기에 O(N^2) 만큼 시간 복잡도가 소요되게 된다. 그러나 문제에서 제시한 문자열의 최대 길이는 1,000,000 이..