Algorithm (4) 썸네일형 리스트형 [Algorithm] Distance in set https://www.acmicpc.net/problem/20190 해당 문제를 해결하는 과정에서 다음과 같은 생각을 했다. std::set은 정렬된 컨테이너로 특정 숫자의 upper bound에 해당하는 인덱스를 알기 어렵구나. set.upper_bound({idx, val}) - set.begin() 이 연산이 지원되지 않았다. 대신, distance 연산이 있었다. distance(set.upper_bound({idx, val}), set.begin()); 으로 활용될 수 있었다. 다만 이는 시간복잡도는 o(n)이다. 그렇기에 상수의 시간복잡도가 필요한 경우, 인덱스 연산이 가능한 vector 의 사용을 고려해야 한다. [Algorithm] CERC 2023 E,B Equal Schedules 두 개의 map 을 이용해서, 각 key 별로 value의 차이를 구하는 문제. getline, istringstream 을 사용해서 input handling 두 가지의 맵을 하나의 for 문에서 순회할 때, map.end 에 닿지 않게끔Ball Passing strictly convex polygon 에서의 pair 간의 거리의 합이 최대가 되게 하려면 모두 교차해야한다. cout 소수점 자릿수 출력strictly convex polygon 에서 순서 부여하기 [Algorithm] 모듈러 연산 알고리즘 문제를 푸는데 많이 나오는 모듈러 연산! 이걸 몰라서 틀리면 억울하니 알아만 두자. (𝑎+𝑏) % 𝑀 = ((𝑎 % 𝑀)+(𝑏 % 𝑀)) % 𝑀 (𝑎−𝑏) % 𝑀 = ((𝑎 % 𝑀)−(𝑏 % 𝑀)+𝑀) % 𝑀 (𝑎×𝑏) % 𝑀 = ((𝑎 % 𝑀)×(𝑏 % 𝑀)) % 𝑀 덧셈, 뺄셈, 곱셈에는 대체로 잘 적용하나 나눗셈은 그렇지 않다. 페르마 소정리를 이용해야 하는데 아래의 블로그에 잘 정리되어 있다. https://ohgym.tistory.com/13 모듈러 나눗셈 Modular 사칙연산만큼 친숙한 모듈러지만 연산은 사칙연산만큼 심플하지는 않다. 정의 자체가 나눗셈을 한 후에 나머지를 가리키는 뜻이니 나눗셈 이상의 매력이 있다. 그럼 한번 사칙연산과 모 ohgym.tistory.com 어쨋든 결.. Frog Jump [26107] 다음 주에 있을 icpc 에 대비해 작년도 문제를 풀어보았다. https://www.acmicpc.net/problem/26107 조건 - 개구리가 아름다운 호수에 살고 있습니다. - 호수에는 x-축 상의 닫힌 구간으로 나타낸 연꽃 잎이 많이 떠 있습니다. - 개구리는 연꽃 잎 위에서 살고 이동하려고 합니다. - x-축 상에서 n개의 닫힌 구간으로 표현된 연꽃 잎이 주어집니다. - 개구리는 초기에 어떤 구간 I0에 위치해 있습니다. - 개구리는 두 구간이 겹치면 그 구간 사이를 이동할 수 있습니다. - 개구리가 오른쪽(왼쪽)으로 이동하는 동안 겹치는 구간을 통과하다가 오른쪽(왼쪽) 끝점에서 더 이상 오른쪽(왼쪽)으로 이동할 수 없는 구간 H에 도달할 수 있습니다. - 이 경우, 개구리는 구간 H의 오른쪽.. 이전 1 다음