정화 코딩

https://www.acmicpc.net/problem/7453 모든 (a, b, c, d) 쌍에 대해서 4중 반복문(시간 복잡도 = O(n^4))을 돌리면 4000^4 = 256,000,000,000,000번의 연산이 필요하고, 1초에 10^8번의 연산이 가능하다고 가정하면 2,560,000초가 걸린다. 즉, 시간 안에 해결 불가능하다. 그런데 모든 (a, b) 쌍에 대한 합을 ab로 구해두고, 모든 (c, d) 쌍에 대한 합을 cd로 구해둔 뒤, ab + cd = 0이 되는 (ab, cd) 순서쌍을 찾으면 2중 반복문으로 문제를 해결할 수 있다. ab 구하기: 시간 복잡도 = O(n^2)cd 구하기: 시간 복잡도 = O(n^2)ab + cd = 0이 되는 (ab, cd) 순서쌍 찾기: 시간 복잡도..

5회차 - 브루트포스, 이분탐색 수학은 비대면강의입니다https://www.acmicpc.net/problem/19532모든 x와 y에 대해서 조건을 체크해주면 됩니다.#include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int a, b, c, d, e, f; cin >> a >> b >> c >> d >> e >> f; // -999부터 999까지 가능한 x, y 값을 전부 탐색 for (int x = -999; x 마인크래프트https://www.acmicpc.net/problem/18111높이를 계속 바꿔서 고정해놓고 계산하는 방식으로 구..

https://www.acmicpc.net/problem/2467 #include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; vector a(n); for (int i = 0; i > a[i]; int l = 0; int r = n - 1; int dif = 2000000000; int la = 0; int ra = 0; while (l 0) r--; else l++; } cout 간단한 투 포인터 문제. 포인터 하나는 왼쪽 끝을, 하나는 오른쪽 끝을 ..

https://www.acmicpc.net/problem/1166 #include #include typedef long long ll;typedef long double ld;using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, l, w, h; cin >> n >> l >> w >> h; ld li = 0; ld ri = l + 1; for (int i = 0; i 실수 이분 탐색 문제는 처음 풀어봤다. (정답)우선, 오차는 10^(-9)까지 허용한다고 하니 cout li, ri, mi 전부 실수로 정의하되, 이분 탐색 계산할 때는 정수로 계산한..

https://www.acmicpc.net/problem/3541 #include #include using namespace std;int gcd(int x, int y) { if (y == 0) return x; return gcd(y, x % y);}int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; int mina = INT_MAX; while (m--) { int u, d; cin >> u >> d; int gcdt = gcd(u, d); // lcm = u * d / gcd ..

공유기 설치 (백준 2110번) https://www.acmicpc.net/problem/2110문제 해석문제에서 주어진 예제를 그려보면 이렇게 된다. 1, 2, 4, 8, 9 위치에 집이 배치되어 있다. 이런 상황에서 가장 인접한 두 공유기 사이의 최대 거리는 공유기를 1, 4, 8에 설치하는 경우와 1, 4, 9에 설치하는 경우 모두 3이 된다. 이런 답은 어떤 과정으로 나오는 것일까? 우선 이 문제를 코드로 해결하는 게 아닌 인간인 우리가 푼다고 생각해보자. '대충 간격을 4 이상으로 둬볼까? 아 4이상으로 하니까 공유기가 남네... 그러면 좀 더촘촘히 둬도 될 것 같으니까 간격을 더 늘려서.....' 이런식으로 푸는 것이 자연스러워 보인다. 이런 경우에 사용되는 알고리즘이 이분 탐색이다.풀이//C..

가장 긴 증가하는 부분 수열 (백준 11053번) https://www.acmicpc.net/problem/11053 import sysinput = sys.stdin.readlinen = int(input())a = list(map(int, input().split()))dp = [0 for _ in range(n)]maxa = 0for i in range(n): maxt = 0 for j in range(i): if a[i] > a[j]: maxt = max(maxt, dp[j]) dp[i] = maxt + 1 maxa = max(maxa, dp[i])print(maxa)dp[i] : 0부터 i까지 i를 포함하는 가장 길게 증가하는 수열의 길이앞의..

093. Dance Dance Revolution (백준 2342번) https://www.acmicpc.net/problem/2342 import sysinput = sys.stdin.readlinedata = list(map(int, input().split()))n = len(data) - 1l = [0 for _ in range(n + 1)]r = [0 for _ in range(n + 1)]p = [0 for _ in range(n + 1)]for i in range(n): if l[i] == data[i] or r[i] == data[i]: l[i + 1] = l[i] r[i + 1] = r[i] p[i + 1] = p[i] + 1 elif l[..