본문 바로가기

cpp46

[무기] Container <SET> 이란? - CPP SETContainer 은 내부적으로 이진 검색 트리로 구현되어 있어 효율적인 삽입, 삭제, 탐색이 가능하다.SET은 키와 값이 동일한 이라고 생각하면 편하다. 따라서 중복되는 키 값이 없다.SET은 주로 키가 string이고 string의 사용 유무를 판단하는 문제에서 사용하면 좋을 것 같다.따라서 알고리즘 문제에서 key가 이름, string으로 사용되야 하는 문제에서 주로 사용하면 좋다. 중요 기능1. s.begin();- 맨 첫번째 원소를 가리키는 반복자를 리턴한다.- ex) iter = s.begin(); 2. s.end();-맨 마지막 원소를 가리키는 반복자를 리턴한다.- ex) iter = s.end(); 3. s.empty();- set이 비어있는 상태인지 확인한다. (bool) 4. s... 2024. 7. 29.
[개쉬운 풀이] 백준 2346 풍선 터뜨리기 https://www.acmicpc.net/problem/2346 생각왼쪽 오른쪽으로 이동하는 것을 deque를 이용하여 값들을 이동시켜 pop_front를 통해 값을 가져오고 제거하기로 했다.deque의 pop()은 O(1) 이기 때문에 원하는 값 만큼 풍선을 옮겨도 시간복잡도가 O(n)이기 때문에 시간초과는 발생하지 않을 것 같다.풀이deque를 pair로 생성하여 로 만들어 주었다.이후 풍선 안의 값이 + 인지 - 인지 확인하여 isPlus와 isMinus로 나누어주었다.isMinus는 맨 뒤값을 앞으로 가져오는 방식으로 인덱스를 조절하였다.isPlus는 앞값을 뒤로 보내는 방식으로 인덱스를 조절하였다.이후 target 풍선을 제거해준다** 이때 다음 풍선값 : nextNumber는 음수가 나올 .. 2024. 7. 25.
[개쉬운 풀이] 백준 11866 요세푸스 문제 0 https://www.acmicpc.net/problem/11866  문제요세푸스 문제는 다음과 같다.1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다.N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오. 생각1. 처음에는 원형 테이블이니까 vector를 통해서 index+k % n방법으로 접근하려고 했습니다. 그러나 타겟이 매번 제거되면 벡터의 크기.. 2024. 7. 15.
[개쉬운 풀이] 백준 10815 숫자 카드 https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 문제 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오. 생각 1. 숫자 카드가 최대 500,000 개가 있으므로 정렬을 해야한다. 2. 최대 500,000번을 서치해야 하므로 바이너리 서치를 구현해서 시간을 단.. 2024. 4. 8.

티스토리툴바