hibye1217의 ALOHA & SHARC 탐방기 hibye1217의 ALOHA & SHARC 탐방기

중급반 3주차 풀이 - 이진 탐색, 파라메트릭 서치, 두 포인터 A. [11053] 가장 긴 증가하는 부분 수열 (Silver II) 더보기 \( DP_{i} := \) \( i \)번째 원소로 끝나는 LIS 로 정의하면, \( DP_{i} = \max_{A_{j} \lt A_{i}} DP_{j} + 1 \)로 점화식을 세울 수 있습니다. 초기.. hibye1217-aloha.tistory.com 중급반 3주차의 1~13번 문제입니다. (...)

1. [8958] OX퀴즈 (Bronze II) 더보기 문자열을 한 글자씩 읽으면서 O가 나올 때마다 점수에 1씩 더하고, X가 나올 때마다 점수를 0으로 초기화시켜주면 됩니다. 최종 점수는 각 글자에서 얻는 점수의 합이 됩니다. void Main(){ int t; cin >> t; while (t--){ string s; cin >> s; int ans = 0, com = 0; for (char ch : s){ if (ch == 'O'){ com += 1; } else{ com = 0; } ans += com; } cout q; while (q--){ string x, s; cin >> x >> s; if (s == "enter"){ st.insert(x); } else{ st.erase(x); } }..

1. [10845] 큐 (Silver IV) 더보기 STL 큐에 있는 6가지 연산들을 그대로 써주면 됩니다. 비어있을 때 -1을 출력하는 부분들만 잘 예외처리하면 됩니다. + STL queue에 back이 있다는 건 저도 풀이를 쓰면서 알았습니다. queue que; void Main(){ int q; cin >> q; while (q--){ string typ; cin >> typ; if (typ == "push"){ int x; cin >> x; que.push(x); } if (typ == "pop"){ if (que.empty()){ cout

1. [2748] 피보나치 수 2 (Bronze I) 더보기 4주차에서 이미 풀어본 문제이지만, 다시 풀어보면서 시간복잡도를 분석해봅시다. 피보나치 수는 \( F_{N} = \begin{cases} 0 & \text{if } N = 0 \\ 1 & \text{if } N = 1 \\ F_{N-1} + F_{N-2} & \text{otherwise} \end{cases} \)입니다. 위 방식을 나이브한 재귀로 구현할 때의 시간복잡도는 어떻게 될까요? 결론만 말하자면, 나이브한 재귀로는 \( O(F_{N}) \)의 시간이 걸립니다. \( F_{1} = 1 \)의 케이스까지 내려가야 답에 1이 더해지므로, 저 과정이 \( F_{N} \)번 반복되어야 우리가 원하는 답인 \( F_{N} \)이 나오겠죠. 그리고..

A. [10870] 피보나치 수 5 (Bronze II) 더보기 피보나치 수는 아래와 같이 구할 수 있습니다. \[ F_{x} = \begin{cases} 0 & \text{if } x = 0 \\ 1 & \text{if }x = 1 \\ F_{x-1} + F_{x-2} & \text{otherwise} \end{cases} \] 이를 그대로 재귀함수로 옮겨주면 됩니다. int f(int x){ if (x

A. [2438] 별 찍기 - 1 (Bronze III) 더보기 반복문 예제로 항상 나오는 '별 찍기'에 왔습니다. \( i \)번째 줄에는 별을 \( i \)개 찍어주면 됩니다. void Main(){ int n; scanf("%d", &n); for (int i = 1; i

A. [10952] A+B - 5 (Bronze III) 더보기 A와 B를 입력받은 뒤, A ≠ 0이거나 B ≠ 0인 동안 A+B를 계속 출력해주면 됩니다. int main(){ while (1){ int a, b; scanf("%d %d", &a, &b); if (a != 0 && b != 0) break; printf("%d\n", a+b); } } B. [10872] 팩토리얼 (Bronze III) 더보기 N!의 정의는 1부터 N까지 곱한 값입니다. 그러니 1부터 N까지 곱해주면 됩니다. int main(){ int n, fac = 1; scanf("%d", &n); for (i = 1; i

1. [1000] A+B (Bronze V) 더보기 두 수를 입력받은 뒤, 두 수의 합을 출력해주면 됩니다. int main(){ int a, b; scanf("%d %d", &a, &b); printf("%d", a+b); } 2. [1001] A-B (Bronze V) 더보기 [1000] A+B랑 비슷합니다. 대신 이번에는 A - B를 출력하면 됩니다. int main(){ int a, b; scanf("%d %d", &a, &b); printf("%d", a-b); } 3. [10998] A×B (Bronze V) 더보기 이제는 두 수의 곱을 출력하면 됩니다. int main(){ int a, b; scanf("%d %d", &a, &b); printf("%d", a*b); } 4. [1008] A..