https://www.acmicpc.net/problem/28078 28078번: 중력 큐 처음에 왼쪽이 큐의 뒤, 오른쪽이 큐의 앞인 가로 방향의 빈 큐가 존재한다. 이 큐에서 공이나 가림막을 하나씩 큐의 뒤에 삽입하거나, 큐의 가장 앞에 있는 공이나 가림막을 꺼낼 수 있으며, 큐 www.acmicpc.net 자료구조 중 큐의 앞, 뒤에 원소를 추가하고 꺼낼 수 있는 자료구조인 deque를 사용하는 것이 핵심인 문제이다. front(), push(), pop()만을 사용하던 기존 queue 자료구조와 다르게 push_front(), push_back(), pop_front(), pop_back(), front(), back()의 함수를 사용할 수 있다. 각각의 쿼리에 대해서 행위를 하였을 때, 공과 가..
https://www.acmicpc.net/problem/28074 28074번: 모비스 주어진 문자열에 포함된 알파벳 대문자들을 이용해 MOBIS를 만들 수 있으면 "YES", 그렇지 않으면 "NO"를 출력한다. www.acmicpc.net 총 N일동안 6가지 선택지 중 하나를 선택하며 얻을 수 있는 기여도의 가짓수를 출력하는 문제이다. 브루트포스 알고리즘을 재귀함수를 이용하여 구현하였으며, 설계는 아래와 같다. 1) 인수 days : 현재 임무를 수행할 날짜 sum : 현재까지 진척도를 모두 더한 기여도 place : 이전 날에 임무를 수행한 장소 2) 종료 조건 : days 가 n일이 될 때, 즉 모든 날을 다 탐색한 경우 방법의 가짓수를 더하도록 하였다. 3) 재귀 호출 첫째 날은 이전 날에 임무..
https://www.acmicpc.net/problem/28074 28074번: 모비스 주어진 문자열에 포함된 알파벳 대문자들을 이용해 MOBIS를 만들 수 있으면 "YES", 그렇지 않으면 "NO"를 출력한다. www.acmicpc.net 문자열에 단어가 포함하였는지 여부를 검사하는 문제이다. algorithm 헤더의 find 함수를 이용해 구현하였다. #include #include using namespace std; char word[5] = { 'M', 'O', 'B', 'I', 'S' }; int main() { string s; cin >> s; for (int i = 0; i < 5; i++) { if (find(s.begin(), s.end(), word[i]) == s.end()) {..
www.acmicpc.net 시간 초과를 조심하자 ! #include #include #include using namespace std; int main() { int n; cin >> n; vector B(n); for (int i = 0; i > B[i]; sort(B.begin(), B.end()); do { long long value= B[0]; bool flag = true; for (int i = 1; i < n; i++) { // 나3곱2의 경우가 아니면 if (!(B[i] == value * 2 || (B[i] == value / 3 && value % 3 == 0))) { flag = false; break; } value = B[i]; } if (flag)..
https://www.acmicpc.net/problem/14889 i와 j가 같은 팀일 때 더해지는 능력치 = S[i][j] + S[j][i]로 계산하며, 두 팀의 능력치의 차이를 최소로 하고자 한다. 이를 구현하는 큰 원리는 아래와 같다. (1) 모든 조합에 대해서 능력치의 차이를 구한다. (2) 능력치의 차이가 최소인 경우, 그 값을 출력한다. 0 1 2 3 4 5 1 0 2 3 4 5 1 2 0 3 4 5 1 2 3 0 4 5 1 2 3 4 0 5 1 2 3 4 5 0 (1,3,6) 팀 = 1 + 2 + 5 + 1 + 3 + 5 = 17 (2,4,5) 팀 = 2 + 3 + 2 + 4 + 4 + 4 = 19 위와 같이, 3개의 팀원이 있다면 (1, 3) (1, 6) (3, 6) 세 개의 조합을 만들..
큐, 스택, 데크 큐는 선입선출 (FIFO)의 속성을 가지고 있다. 스택(Stack) 은 반대로 후입선출(LIFO)의 속성을 가지고 있고, 데크(dequeue) 는 양쪽 끝에서 넣고 뺄 수 있는 자료 구조를 말한다. 이 자료 구조는 동적 배열, 혹은 연결 리스트로 구현할 수 있다 (1) 연결리스트로 구현 시 양쪽 끝에서 상수 시간에 추가와 삭제가 가능하다. (2) 동적 배열을 이용한 구현 시, 배열의 맨 앞에서 원소 삭제 시 O(n)의 시간이 걸린다는 단점이 있다 → head와 tail을 이용해서 이 점을 보완할 수 있다. 즉 배열 전체가 아닌 head부터 tail까지만 자료구조로 사용하겠다는 건데, 버려지는 공간이 많다는 단점이 있다. 이는 환형 버퍼 (circular buffer) 의 개념으로 해결할..
선형 자료구조 배열은 메모리의 연속된 위치에 각 원소들이 저장되어있고, 연결 리스트는 여기저기 흩어져있는 원소들의 특정 위치에서 삽입과 삭제를 상수 시간에 수행하기 위해 이전 원소에서 다음 원소를 가리키는 “포인터”로 구현한다. struct ListNode { int element; ListNode *prev, *next; } C++에서는 연결리스트를 list라는 STL을 사용해서 구현한다. 조세푸스 문제 #include #include using namespace std; void josephus(int n, int k) { list survivors; for (int i = 1; i 2) { kill = survivors.erase(kill); if (kill == survivors.end()) ki..
부분 합이란 ? 배열의 각 위치에 대해서, 배열의 시작부터 현재 위치까지의 원소의 합을 구한 배열 #include #include using namespace std; vector partialSum(const vector& a) { vector ret(a.size()); ret[0] = a[0]; for (int i = 1; i < a.size(); i++) { ret[i] = ret[i - 1] + a[i]; } return ret; } int rangeSum(const vector& psum, int a, int b) { if (a == 0) return psum[b]; return psum[b] - psum[a - 1]; } 앞의 값에서 현재 값을 더하며 부분합 배열을 구하고, 이를 활용해서 구간..
비트마스크(bitmask) 란 ? 이진수 표현을 자료구조로 쓰는 기법이다. 비트 연산자 a & b : AND 연산 a | b : OR 연산 a ^ b : XOR 연산 ~a : NOT 연산 a > b 정수 a를 오른쪽으로 b비트 Shift 비교 연산자 → 비트 연산자의 우선순위 집합의 구현 int noPizza = 0; // 공집합 int fullPizza = (1
