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) 세 개의 조합을 만들..
A와 B 사이에 겹치는 건물이 있는지 확인하는 과정에서 "두 점 사이의 직선" 공식을 이용해서 A와 B사이에 있는 모든 건물의 높이를 계산하여 푸는 과정을 이용했다. 여기서 (double) 범벅을 한 이 코드에서 j가 자꾸 잘 못 구해지는 버그가 있었다. A와 B건물 사이의 i번째 건물의 높이가 A와 B의 지붕을 연결한 선에 겹치지 않는지 검사하기 위해서 아래 공식을 사용한 것인데, j의 계산이 잘 되지 않았다 . #include #include using namespace std; // 고층 빌딩 /* 15 1 5 3 2 6 3 2 6 4 2 5 7 3 1 5 */ vector height ; // 빌딩 A(x1, y1)이 빌딩 B(x2, y2)를 볼 수 있는 지 확인하는 함수 bool isOverla..
총 일할 수 있는 N일 중에서 연속된 M일을 선택했을 때 그 부분합이 최대가 되는 경우를 계산하는 문제이다. 구간을 정해서 부분합을 구하는 슬라이딩 윈도우 혹은 투포인터 알고리즘을 적용할 수 있고, 여기서는 M이라는 일정한 크기의 윈도우가 정해져있으므로 슬라이딩 윈도우 알고리즘을 사용하여 풀이한다. https://ji-musclecode.tistory.com/37 슬라이딩 윈도우 알고리즘(Sliding Window) (feat. 투 포인트) 1. 슬라이딩 윈도우 알고리즘 (Sliding Window) ( 슬라이딩 윈도우 알고리즘 간단 예제 ) 1, 2, 3, 4, 5, 6, 7 로 이루어진 숫자 배열에서 A[i] + A[i+1] + A[i+2] 형식으로 연속적인 3개의 숫자의 합의 최댓값을 ji-musc..
해당 리스트의 연속 수열의 합이 특정 값보다 이상이 되는 것 중 가장 짧은 것의 길이를 확인하는 문제이다. https://butter-shower.tistory.com/226 [Algorithm] 투포인터(Two Pointer) 알고리즘 알고리즘 문제를 풀다보면 종종 나오는 투포인터 알고리즘! 막 꼬여가지고 ㅋㅋㅋ 저도 중간에 제대로 못짜고 그러는 경우가 많은데요, 많은 코딩테스트 문제에 등장하는 것은 아니지만 잊을만 butter-shower.tistory.com 투포인터 알고리즘은 병합정렬에서 사용한 Conquer 방식과 유사하게 start와 end 지점에서의 부분합을 계산하는 알고리즘이다. 이 문제에서는 특정값 S의 이상이 되는 값들 중 가장 짧은 것을 구하라고 하였으니, 아래의 방법들로 소스코드를 ..
1003번: 피보나치 함수 (acmicpc.net) 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net #include #define endl '\n' using namespace std; int fibonacci(int n, int &cnt0, int &cnt1) { if (n == 0) { cnt0++; return 0; } else if (n == 1) { cnt1++; return 1; } else { return fibonacci(n - 1, cnt0, cnt1) + fibonacci(n - 2, cnt0, cnt1); } } int main() { ios_base::sync_with_stdio(fa..
