문제 https://www.acmicpc.net/problem/27970 27970번: OX O와 X로 이루어진 문자열이 주어진다. 모든 문자를 X로 만들 때까지 다음 연산을 반복할 때, 시행하는 연산의 횟수를 구하시오. 문자열의 가장 왼쪽에 있는 O를 X로 바꾸고, 그보다 왼쪽에 있는 X www.acmicpc.net 풀이 a = 10**9 + 7 s = input() arr = [1]*len(s) for i in range(1, len(s)): arr[i] = (arr[i-1]*2)%a count = 0 for i in range(len(s)): if s[i] == 'O': count = (count + arr[i])%a print(count) 처음에는 for문을 통해 일일이 count하도록 코드를 짰..
문제 https://www.acmicpc.net/problem/28014 28014번: 첨탑 밀어서 부수기 첫째 줄에 첨탑의 개수 $N$이 주어진다. $(1\leq N\leq 5\,000\,000)$ 둘째 줄에는 앞에서부터 차례대로 첨탑의 높이 $H_1, H_2, \cdots, H_n (1\leq H_i\leq 1\,000\,000)$ 이 주어진다. 입력으로 주어지는 모든 수는 정 www.acmicpc.net 풀이 #include using namespace std; int count = 0; int main(){ ios::sync_with_stdio(false); cin.tie(NULL); int n; int n1 = 0; int n2; cin >> n; for(int i = 0; i> n2; if(n..
문제 https://www.acmicpc.net/problem/26258 26258번: 다중 일차 함수 2차원 좌표 평면에 점 $N$개가 주어진다. $i$번째 점의 위치는 $(x_i, y_i)$이고, $1 \leq i \lt N$인 모든 $i$에 대하여 $x_i \lt x_{i+1}$을 만족하며, 점 $i$와 점 $i + 1$을 잇는 일차 함수가 그려진다. 각각 구간 www.acmicpc.net 풀이 #include using namespace std; int cor[100005][2]; int main(){ ios::sync_with_stdio(false); cin.tie(NULL); int N, Q; float x, y, k; cin >> N; for(int i = 0; i> x >> y; cor[i..
문제 https://www.acmicpc.net/problem/21735 21735번: 눈덩이 굴리기 눈송이들이 많은 동네인 숙명여대 앞마당에서 눈사람 만들기 대회를 연다. 앞마당의 길이는 $N$이고 위치 $1$부터 위치 $N$ 까지만 눈이 쌓여있다. 위치 $i$에 눈이 $a_i$만큼 쌓여있다. 대회 규칙은 www.acmicpc.net 풀이 #include using namespace std; int snow[105]; int N, M; int bf(int pos, int count, int size){ if(pos >= N) return size; if(count == M) return size; int result = 0; result = max(bf(pos+1, count+1, size+snow[p..
문제 https://www.acmicpc.net/problem/27963 27963번: 합금 주화 첫 번째 줄에 0보다 크고 100보다 작은 세 정수 $d_1$, $d_2$, $\chi$가 공백으로 구분되어 주어진다. 서로 다른 두 정수 $d_1$, $d_2$는 기념주화를 이루는 두 가지 금속의 밀도이다. 단위는 $\text{g}/\text{cm} www.acmicpc.net 풀이 #include using namespace std; int main(){ int a, b, m; double result; cin >> a >> b >> m; if(a
-알고리즘이란? 주어진 문제를 해결하는 한가지 방법을 명료하게 써놓은 것을 알고리즘이라 한다. - 알고리즘의 시간복잡도에 따른 시간 O(N^3) 알고리즘: 크기 2560 이하인 입력을 1초 안에 풀 수 있다. O(N^2) 알고리즘: 크기 40960 이하인 입력을 1초 안에 풀 수 있다. O(NlgN) 알고리즘: 크기 대략 2천만 이하인 입력을 1초 안에 풀 수 있다. O(N) 알고리즘: 크기 대략 1억 6천만 이하인 입력을 1초 안에 풀 수 있다. - P/NP 문제란? P 문제: 다항 시간 알고리즘이 존재하는 문제들의 집합 NP 문제: 답이 주어졌을 때 이것이 정답인지를 다항시간 내에 확인할 수 있는 문제
