목록C,C++/STL (4)
오답노트
https://www.acmicpc.net/problem/13414 13414번: 수강신청 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 과목의 수강 가능 인원 K(1 ≤ K ≤ 100,000)와 학생들이 버튼을 클릭한 순서를 기록한 대기목 www.acmicpc.net - 문제파악 K명 수강가능한 강의에서 L명(L명 중에 같은 사람이 있을수도 있다)이 수강신청하려고 한다. 수강신청은 다음과 같은 규칙이 있다. 첫째 수강신청을 하면 대기열에 올라간다. 둘째 대기열에 올라간 사람이 다시 수강신청을 누르면 대기열에서 마지막으로 밀려난다. 세번째 대기열에 올라간 사람들중 순서가 가장 빠른 순으로 K명 수강신청이 완료된다. 수강신청 버튼을 누른 학생들의 학번..
해시란? 임의의 길이의 데이터를 특정 길이의 데이터로 대응시키는 자료구조를 뜻한다. 예를들어 어떤 학생의 학번과 이름을 컴퓨터에게 기억하게 하고 싶은데 만약 학번이 너무 길다면 학번의 일부분만을 이용해 Key를 만들어 학생의 이름을 저장한다. 그리고 STL에서는 해시 자료구조들을 지원하고 있다. 1. unodered_set unodered_set : unodered_set은 선언부에서 입력된 자료형을 Key로 가지는 해시 자료구조이다. 특징으로는 중복을 허용하지 않는다. #include #include using namespace std; void unordered_set_func() { unordered_set unset; unset.insert(10); unset.insert(100); unset.i..
이분탐색(이진탐색)이란? 상대방이 속으로 생각한 숫자를 찾는 '업다운' 게임의 규칙은 다음과 같다. 상대방은 제한된 범위 안에서 숫자를 생각하고 또 다른 사람은 숫자를 부르며 그 숫자보다 생각한 수가 크면 업, 작으면 다운으로 상대방이 생각한 수를 맞추는 게임이다. 이분탐색은 '업다운' 게임과 같이 배열의 가장 중간의 값을 선택하고 그 수가 우리가 찾는 수보다 크면 중간 위치 부터 마지막 위치까지, 작으면 처음 위치부터 중간 위치까지를 반복하여 탐색 범위를 좁혀가며 원하는 수를 찾는 방법이다. 하지만 이를 위해서는 무조건 배열의 오름차순 정렬이 선행되어야 한다. 그리고 이런 이분탐색을 친절하게도 STL에서 제공한다. algorithm.h 를 코드에 추가하면 아래 함수들을 사용할 수 있다. 1. binar..
- next_permutation 오름차순 정렬된 컨테이너를 받는다 입력 컨테이너의 다음 순열을 입력 컨테이너에 입력한다. 다음 순열이 존재하면 true, 존재하지 않으면 false #include // std::cout #include // std::next_permutation, std::sort using namespace std; int main() { vector vnt = { 1,2,3 }; while (next_permutation(vnt.begin(), vnt.end())) { for (auto& i : vnt) cout