나쿠리 개발 메모장

개요 https://www.acmicpc.net/problem/10090 10090번: Counting Inversions A permutation of integers from 1 to n is a sequence a1, a2, ..., an, such that each integer from 1 to n is appeared in the sequence exactly once. Two integers in а permutation form an inversion, when the bigger one is before the smaller one. As an example www.acmicpc.net 알아두면 좋을 것 같은 유형 (P5) 본문 요약하면 순열에서 역전된 쌍의 개수를 찾는 문제이다. N이 ..

개요https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄www.acmicpc.net세그먼트 트리 기초 문제 (G1)풀이Range Sum Query를 처리하는 Segment Tree를 구현하면 된다.Ai의 범위가 약 ±2^63 이기 때문에 자료형 주의 ! 코드더보기#include using namespace std; using ll = long long; class segment_tree{ private: vector tr..

매일 상상만 하던 random access + O(logN) 삽입 삭제가 이미 있다니 . . (only g++) #include #include #include using namespace __gnu_pbds; using namespace std; #define ordered_set tree int main(){ ordered_set oSet; // idx 번째 iterator 반환 oSet.find_by_order(idx); // value의 idx를 반환 (value보다 작은 원소 개수를 반환) oSet.order_of_key(value); oSet.insert(v); oSet.erase(v); } 활용 https://www.acmicpc.net/problem/2517 2517번: 달리기 첫째 줄에는..

Data Structure Stack Queue Dequeue Priority Queue Table Hash Tree BST MST(Kruskal/Prim) Uinon-Find(Disjoint-Set) PBDS Segment Tree 에라토스테네스의 체 골드바흐의 추측 Dijkstra BFS / DFS Trie Reclusion Brute Force Backtracking Binary Search Topological Sorting DP knapsack LCS LIS 행렬 곱셈 순서 파일 합치기 Greedy 기타 테크닉 dxy 좌표(값) 압축 bit mask two pointer sliding window prefix sum sweeping

개요 https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net P5 자력솔 ! 본문 힌트 스택을 활용 같은 키가 연속으로 push되는 경우를 고려 풀이 더보기 스택 자료구조를 활용하여 입력을 받음과 동시에 top과 비교하여 처리 (선행 문제 : BOJ 2493번 탑) top이 더 클 경우 : result += (pop한 개수 + 1)개 후 push(키, 1(연속 1회를 의미)) top과 같을 경우 : result += (pop한 ..

개요 https://www.acmicpc.net/problem/22953 22953번: 도도의 음식 준비 첫째 줄에 요리사의 수 $N$ ($1 \le N \le 10$), 만들어야 할 음식의 개수 $K$ ($1 \le K \le 1\,000\,000$), 격려해줄 수 있는 횟수 $C$ ($0 \le C \le 5$)가 주어진다. 둘째 줄에 길이가 $N$인 정수 수열 $A$가 주어 www.acmicpc.net G4 본문 처음에는 정렬 후 빠른 순으로 그리디써서 때려 맞춰봤는데, 오답 - 요리사 수와 격려 기회가 생각보다 작다. -> 브루트포스 모든 경우의 수를 확인하면서 이분 탐색으로 최소 시간을 구했다. 그 중 가장 작은 시간을 출력 더 이상 격려 할 수 없는 경우도 고려해야 함에 주의 코드 #inclu..

개요 https://school.programmers.co.kr/learn/courses/30/lessons/42862# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 체감 난이도 BOJ기준 B1 정도 . . ? 본문 그리디로 풀었다. 여벌의 체육복을 가진 학생이 인접해있으면 누적해서 빌려줄 수 있을 것이라고 생각했는데, 그런것도 없어서 엄청 간단했다. 코드 #include #include using namespace std; int solution(int n, vector lost, vector reserve) { int answer = 0; // 1 ..

개요 https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 오랜만에 풀어봤다. 간단한 투포인터 문제다. Gold V 풀이 입력 값을 vecter나 array에 정렬 후 front 부터 두 value 비교하면 된다. 차이가 M보다 작을 경우 front++ , 아닐 경우 back++ 를 해주면 된다. 코드 #include using namespace std; constexpr int LIMIT = 1e5 + 2; const int I..

개요 https://school.programmers.co.kr/learn/courses/30/lessons/181188 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 개인적인 체감 난이도는 BOJ 기준 S3-S4 언저리 정도 되는 듯 하다. 접근 범위를 정렬 후 그리디 형태로 풀면 될 듯 했다. 이전 미사일의 범위를 넘어갈 경우 카운트를 증가시킨다. 그 후 범위를 넘어간 범위로 재설정 하면 될 것이라고 판단했다. 한 번 틀렸다. 이전 미사일 범위의 끝점(e)보다 현재 끝점(e)가 작은 경우 해당 범위를 이전 미사일 범위로 바꾸어주어야 했다. 그렇지 않을..

개요 https://www.acmicpc.net/problem/26154 26154번: 한양 가왕 $N$개의 줄에 걸쳐, $i$번째 줄에 $i$번째 노래방 기계에 위치해 있는 참가자들의 실력 점수를 오름차순으로 공백을 두고 출력한다. www.acmicpc.net GoldⅡ 애드 혹 + 구현 문제 출제자의 추천으로 풀게 된 문제 ! (M** 보고 있냐) 본문 M이 10억 인 것만 봐도 단순 탐색 시 시간초과가 난다. N을 3으로 잡고 한 번 돌려보았다. 규칙에 따른다면 라운드별로 아래와 같이 진행된다. 라운드 / 방 번호 1 2 3 4 5 6 1 1 3 5 3 5 6 4 6 3 6 5 6 2 2 5 2 6 2 4 2 3 2 5 2 4 3 4 6 4 1 3 1 5 1 4 1 3 1 규칙이 보인다..! 방 개..