기로에 서다

문제 www.acmicpc.net/problem/16566 16566번: 카드 게임 첫째 줄에 세 개의 자연수 N, M, K가 주어진다. (1 ≤ M ≤ N ≤ 4,000,000, 1 ≤ K ≤ min(M, 10,000)) 다음 줄에 카드의 번호를 나타내는 M개의 자연수가 주어진다. 각각의 수들은 1 이상이고 N 이하이며 서로 www.acmicpc.net 풀이 낼 수 있는 카드를 정렬해둔 후, upperbound를 통해 낼 카드 번호를 바로 구할 수 있을 것 같지만 낸 카드는 버리기에 사용한 카드의 유무를 저장하는 배열을 사용해 항상 사용하지 않은 카드를 내는 식으로 해결할 수 있습니다. $O((m + k)logm)$ 코드 #include using namespace std; int n, m, k, x,..

문제 www.acmicpc.net/problem/7045 7045번: Tree Cutting After Farmer John realized that Bessie had installed a "tree-shaped" network among his N (1

문제 www.acmicpc.net/problem/5867 5867번: Scrambled Letters Farmer John keeps an alphabetically-ordered list of his N cows (1 > n; miv.resize(n), mav.resize(n); for (int i = 0; i > s; sort(all(s)); miv[i] = s; low.push_back(s); reverse(all(s)); mav[i] = s; high.push_back(s); } sort(all(low)), sort(all(high)); for (int i = 0; i < n; i++) { p1 = lower_bound(all(high), miv[i]) - high...

문제 programmers.co.kr/learn/courses/30/lessons/72415 코딩테스트 연습 - 카드 짝 맞추기 [[1,0,0,3],[2,0,0,0],[0,0,0,2],[3,0,1,0]] 1 0 14 [[3,0,0,2],[0,0,1,0],[0,1,0,0],[2,0,0,3]] 0 1 16 programmers.co.kr 풀이 0. 어떤 종류의 카드를 제거한다고 할 때, 종류가 같은 카드 두 개를 찾으려고 매번 맵 전체를 순회하지않기 위해 카드의 종류별로 두 카드의 위치를 담아줍니다. [ line 86 ] 1. 모든 카드를 종류별로 제거해야하고 그 순서에 따라 움직이는 거리가 달라지기에 제거할 종류들의 순서를 next_permutation으로 구해줍니다. [ line 99 ~ 103 ] 2...

문제 programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 풀이 1. N이 200이하로 작으므로 플로이드 와샬을 사용하여 $O(N^3)$내에 모든 정점..

문제 programmers.co.kr/learn/courses/30/lessons/72412 > s) { if (iinfo[0] q) { if (counter == 0) iinf..

문제 programmers.co.kr/learn/courses/30/lessons/72411 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr 풀이 1. 우선 각각의 손님이 주문한 음식들로부터 음식들을 조합하여 원하는 길이(course[])만큼의 메뉴구성을 해주고, map의 key엔 메뉴구성을 value엔 그 개수를 담아 메뉴구성을 카운트합니다. 2. map을 순회하며 그 값(가능한 조합의 개수)가 2이상인 것들만 선택하여 길이를 인덱스로 갖는 벡터(cand)에 메뉴구성을 넣어줍니다. 3. 마지막으로 course..

문제 programmers.co.kr/learn/courses/30/lessons/72410 코딩테스트 연습 - 신규 아이디 추천 카카오에 입사한 신입 개발자 네오는 카카오계정개발팀에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. 네오에게 주어진 첫 업무는 새로 가 programmers.co.kr 풀이 문제에서 구현하라는대로 그대로 따라 구현하면 됩니다. c++의 경우 isupper, tolower, substr과 같은 문자열(문자)를 다루는 stl을 적절히 사용하면 더 간단하게 구현할 수 있습니다. 코드 #include using namespace std; bool isok(char x) { if (islower(x) || isdigit(x) || x == ..

문제 www.acmicpc.net/problem/20438 20438번: 출석체크 1번째 줄에 학생의 수 N, 졸고 있는 학생의 수 K, 지환이가 출석 코드를 보낼 학생의 수 Q, 주어질 구간의 수 M이 주어진다. (1 ≤ K, Q ≤ N ≤ 5,000, 1 ≤ M ≤ 50,000) 2번째 줄과 3번째 줄에 각각 K명 www.acmicpc.net 풀이 1. 조는 친구들을 우선 체크한 후, 출석 번호를 받은 친구들의 배수마다 출석했다고 체크를 하는데 조는 친구들은 무시하고 넘어가면 됩니다. 2. 이 때 구간질의마다 학생 수를 세면 시간초과가 나기 때문에 미리 누적합 배열을 저장해놓고, [s, e] 구간의 합에 대해psum[e] - psum[s - 1]을 출력하면 해결할 수 있습니다. 코드 #include ..

문제 www.acmicpc.net/problem/20437 20437번: 문자열 게임 2 첫 번째 문자열에서 3번에서 구한 문자열은 aqua, 4번에서 구한 문자열은 raquator이다. 두 번째 문자열에서는 어떤 문자가 5개 포함된 문자열을 찾을 수 없으므로 -1을 출력한다. www.acmicpc.net 풀이 1. W가 소문자 알파벳으로만 이루어졌으므로 문자열 내에서 알파벳들의 위치를 담는 알파벳 벡터를 만들어 각각의 위치들을 담아줍니다. 2. 알파벳 벡터를 순회하며 크기가 K이상인 것들에 대해서 시작 인덱스를 st라 하면 끝은 st + k - 1까지 원소들을 K개씩 검사합니다. 3. 이 때 문제에서 요구하는 정확히 K개 문자를 포함하는 연속 문자열은 결국 w를 구성하는 연속 문자열[st, st + k..