정영주

문제 출처 : BOJ 23327 - 리그전 오브 레전드 https://www.acmicpc.net/problem/23327 23327번: 리그전 오브 레전드 첫 번째 줄에 참가를 원하는 팀의 수 $N$($2 \le N \le 100 \, 000$), 후보 디비전의 개수 $Q$($1 \le Q \le 200 \, 000$)가 주어진다. 두 번째 줄에 정수 $a_1, a_2, \dots, a_N$이 주어진다. $a_i$는 $i$번째로 잘하는 www.acmicpc.net 아주아주 오랜만에 백준 문제를 풀었더니 너무 낯설었다. 이번 방학동안 다시 열심히 불태워봐야겠다. 처음에 이 문제를 봤을 때 2차원 배열로 풀어야 할 것만 같아서 2차원 배열로 풀었는데 (당연하게도) 메모리 초과가 났다. 그렇게 간단한 문제였..

문제 출처 : BOJ 2230 - 수 고르기 www.acmicpc.net/problem/2230 마지막으로 투 포인터를 연습해보는 문제이다. 주어진 수열에서 두 수의 차이가 m 이상인 것 중 최솟값을 구하는 문제이다. 최종 코드 #include #include using namespace std; #define MAX 100001 #define MAX_GAP 2000000000 int arr[MAX]; bool f(int a, int b) { return a > b; } int main() { int n, m, l = 0, r = 0, gap = 0, min = MAX_GAP; cin >> n >> m; for (int i = 0; i > arr[i]; sort(arr, arr..

문제 출처 : 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 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 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) {..

문제 출처 : BOJ 2751 - 수 정렬하기 2 www.acmicpc.net/problem/2751 의 sort() 라는 정렬 함수를 배우게 되어서 정렬 문제를 한번 풀어보았다. 수를 입력 받아서 오름차순으로 정렬하는 문제이다. C언어에서 기본적으로 사용하던 swap() 함수를 이용한 정렬은 시간복잡도가 O(n^2)이어서 시간 초과가 떴었다. 최종 코드 #include #include using namespace std; #define MAX 1000000 int arr[MAX]; int main() { int n; cin >> n; for (int i = 0; i > arr[i]; sort(arr, arr + n); for (int i = 0; i < n; i++) cout

문제 출처 : BOJ 10828 - 스택 www.acmicpc.net/problem/10828 C++ 자체에 스택 기능이 포함되어 있다는 사실을 알게 되어서 스택 관련 예제를 풀어보았다. push x, pop 등 각각의 명령을 수행하고 그 명령에 맞는 출력을 하는 문제이다. 최종 코드 #include #include #include using namespace std; int main() { int n, num; cin >> n; stack s; char str[6]; while (n--) { cin >> str; if (!strcmp(str, "push")) { cin >> num; s.push(num); } else if (!strcmp(str, "pop")) { if (s.size()) { cout