목록분류 전체보기 (129)
끄적끄적
출처 : https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 우선순위 큐를 사용해서 푸는 문제 점수가 높은 순으로 정렬해준다음, 과제를 하루에 하나씩 할 수 있다고 했으므로 각 과제를 할 날을 지정한다. 해당 일자에 다른 과제를 이미 하기로 했으면(방문한 적이 있다면), 날짜를 줄여가면서 찾기. + 배열을 선언할 때 전역으로 선언하면 초기화 해주지 않아도 되지만, 로컬로 선언할 경우 쓰레기값이 들어가서 초기화해줘야함.
출처 : https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 우선순위큐 vector에 입력된 값을 정렬하지 않고 풀었더니 틀렸다고 떠서 정렬을 해주었다. 끝난 시간도 우선순위큐에 넣음으로써 정렬시켜주지만, 시작시간도 먼저 시작된 순으로 들어가야하기 때문에 벡터 정렬을 해줘야 하는 것 같다.
출처 : https://www.acmicpc.net/problem/2002 2002번: 추월 입력은 총 2N+1개의 줄로 이루어져 있다. 첫 줄에는 차의 대수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 대근이가 적은 차량 번호 목록이 주어지고, N+2째 줄부터 N개의 줄에는 영식이 www.acmicpc.net 해시
출처 : https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 우선순위큐를 이용하여 푸는 문제 우선순위큐는 디폴트가 내림차순이기 때문에, 오름차순을 이용하기 위해서는 priority_queue pq; 와 같이 사용해야함. 또한, 숫자 입력 최대가 백만이고, 카드수는 최대 1000장이므로 int로 하면 연산하다가 초과될 수 있으므로 전부 long long으로 선언해주어야 함.
출처 : https://www.acmicpc.net/problem/10546 10546번: 배부른 마라토너 마라토너라면 국적과 나이를 불문하고 누구나 참가하고 싶어하는 백준 마라톤 대회가 열린다. 42.195km를 달리는 이 마라톤은 모두가 참가하고 싶어했던 만큼 매년 모두가 완주해왔다. 단, 한 명 www.acmicpc.net 해시를 이용하여 풀어야하는 문제 unordered_map을 이용 map_name[key] = value 탐색 방법 index로 접근할 수 없고, iterator로 접근 key : iter -> first, iter -> second map과 unordered_map의 차이 unordered_map은 해쉬테이블로 구현한 자료구조로 탐색 시간복잡도 O(1) map 은 binary s..
출처 : https://www.acmicpc.net/problem/20301 20301번: 반전 요세푸스 첫째 줄에 정수 $N$, $K$, $M$이 주어진다. ($1 \leq N \leq 5\ 000$, $1 \leq K, M \leq N$) www.acmicpc.net 처음에 요세푸스 0 문제와 비슷하게 풀다가 너무 복잡해져서 deque로 다시 풀었다. 기존 요세푸스 순열과 같은 방식으로 진행된다면 K-1번만큼 반복하며 앞에서부터 순차적으로 하나씩 뒤로 보내며 K번째 인걸 pop해서 ans에 넣어주면 된다. 반면, 반전 요세푸스 순열에서처럼 방향이 반대로 바뀌면 뒤에서부터 순차적으로 앞으로 보내주면 된다. 앞뒤 모두 사용해야하므로 deque를 사용해서 해결하는 문제였다. M번째일때 방향이 바뀌므로 re..
출처 : https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net queue v.erase(v.begin() + 인덱스 ) v.size()가 0일 때 % 연산을 적용하면 코드가 종료되어서 분기처리를 하였다.
출처 : https://www.acmicpc.net/problem/15662 15662번: 톱니바퀴 (2) 총 8개의 톱니를 가지고 있는 톱니바퀴 T개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 덱과 큐를 이용하여 구현 num-1을 해준 이유는 인덱스가 0부터 시작하기 때문 계속해서 방문하는 것을 막기 위해 방문여부 체크