정영주

문제 출처 : BOJ 1806 - 부분합 www.acmicpc.net/problem/1806 이번 문제도 투포인터를 이용하는 문제이다. 이번 문제는 부분합이 s 이상인 부분합들 중에서 길이가 가장 짧을 때의 길이를 출력하는 문제이다. 최종 코드 #include using namespace std; #define MAX 100001 int main() { int n, s, arr[MAX], l = 0, r = 0, sum = 0, len = 0, min = 0; cin >> n >> s; for (int i = 0; i > arr[i]; while (1) { if (sum >= s) { sum -= arr[l++]; len--; } else if (r == n) break; el..

문제 출처 : BOJ 1644 - 소수의 연속합 www.acmicpc.net/problem/1644 투 포인터를 배운 기념으로 연습 문제를 풀어보았다. 앞서 풀었던 2003 수들의 합 2 문제와 상당히 유사하다. 최종 코드 #include using namespace std; #define MAX 4000001 int prime[MAX]; int main() { int n, l = 2, r = 2, sum = 0, cnt = 0; cin >> n; for (int i = 2; i < n; i++) prime[i] = 0; for (int i = 2; i n) break; else { sum += r; while (prime[++r]) {} } if (sum == n) cnt++; } cout

문제 출처 : BOJ 2003 - 수들의 합2 www.acmicpc.net/problem/2003 처음으로 투 포인터를 사용해 본 문제이다. 이중 for문을 사용하면 시간 복잡도가 엄청 커지는데, 투 포인터를 사용하면 그 문제를 해결할 수가 있다. 최종 코드 #include using namespace std; #define MAX 10000 int main() { int arr[MAX], n, m, cnt = 0, l = 0, r = 0, sum = 0; cin >> n >> m; for (int i = 0; i > arr[i]; while (1) { if (sum >= m) sum -= arr[l++]; else if (r == n) break; else sum += arr..

문제 출처 : BOJ 5397 - 키로거 www.acmicpc.net/problem/5397 list를 이용하는 과제로 풀었다. 앞서 풀었던 1406 에디터 문제와 굉장히 유사한 문제이다. 1406 에디터 문제는 원래 있던 문자열을 입력받는 명령에 따라 수정하는 방식이고, 이 문제는 문자열에 명령이 섞여 있다. 최종 코드 #include #include #include using namespace std; int main() { int t; cin >> t; while (t--) { string str; cin >> str; list L; auto cursor = L.end(); for (auto ch : str) { if (ch == '') { if (cursor != L.end()) cursor++;..

문제 출처 : BOJ 1158 - 요세푸스 문제 www.acmicpc.net/problem/1158 저번에 큐로 풀었던 요세푸스 문제이다. 이번에는 list를 이용하여 풀어보았다. 최종 코드 #include #include using namespace std; int main() { int n, k, cnt = 0; cin >> n >> k; list L; for (int i = 1; i

문제 출처 : BOJ 1405 - 미친 로봇 www.acmicpc.net/problem/1405 과제로 풀게 된 문제인데.. 미친 로봇을 풀다가 내가 미쳐버릴 것 같았다. 최종 코드 #include #include using namespace std; double dir[4]; // 각 방향의 확률 저장 int dx[4] = { 1, -1, 0, 0 }; // 동, 서 int dy[4] = { 0, 0, -1, 1 }; // 남, 북 double robot(int x, int y, int visit[30][30], int count, int n) { if (count == n) return 1; int visit_tmp[30][30]; for (int i = 0; i < 30; i++) { for (in..

문제 출처 : BOJ 1406 - 에디터 www.acmicpc.net/problem/1406 한 줄로 된 간단한 에디터를 구현하는 문제이다. 예전에 자료구조를 처음 배웠을 때 스택을 이용해서 푼 적이 있는데, 이번에는 STL Container 중 하나인 list를 이용해서 풀어보았다. 최종 코드 #include #include using namespace std; int main() { string editor; cin >> editor; list L; for (auto c : editor) L.push_back(c); auto cursor = L.end(); int q; cin >> q; while (q--) { char op; cin >> op; if (op == 'P') { char n; cin >..

문제 출처 : BOJ 10984 - 내 학점을 구해줘 www.acmicpc.net/problem/10984 n개 과목들의 학점과 성적이 주어지면, 총 학점과 평점(GPA)을 구하는 문제이다. 최종 코드 #include #include using namespace std; int main() { int t, n, c, sum; // 학점 c, 총 학점 sum float score, g; // 학점 * 성적 score, 성적 g cin >> t; for (int i = 0; i > n; for (int j = 0; j > c >> g; sum += c; score += c * g; } cout

문제 출처 : BOJ 5565 - 영수증 www.acmicpc.net/problem/5565 책 10권의 총 가격과 9권의 각 가격이 주어졌을 때, 나머지 한 권의 가격을 구하는 비교적 쉬운 문제이다. 최종 코드 #include using namespace std; int main() { int n, cost; cin >> n; for (int i = 0; i > cost; n -= cost; } cout

문제 출처 : BOJ 11650 - 좌표 정렬하기 www.acmicpc.net/problem/11650 평면 위의 점 N개의 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순으로 정렬하는 문제이다. 어제 풀었던 BOJ 10814 나이순 정렬 문제랑 굉장히 비슷하다. https://yeongjujeong1021.tistory.com/17?category=1012907 이 문제도 헤더의 sort() 함수를 이용해서 풀어보았다. 최종 코드 #include #include using namespace std; #define MAX 100000 struct coordinate { int x; int y; } c[MAX]; bool func(coordinate a, coordinate b) {..