https://www.acmicpc.net/problem/315771. 랜섬웨어와 비트코인(G4)120까지 순회를 하는데 8개씩 끊어서 1부터20까지의 숫자를 저장할 수 있어야 함.사이클 돌리는 것을 mod연산으로 구현할 수 있어야 함arr[i%8] = i%20+1;  https://www.acmicpc.net/problem/240252. 돌의 정령 줄세우기특정 숫자에 맞추려고 하기 보단 INF, 0로 무조건 조건을 만족하는 경우를 생각1~N까지의 수를 뒤집고 시작  https://www.acmicpc.net/problem/139553. Key Knockingkey가 3의 배수로만 주어지는 점을 생각(왜 하필 3의 배수일까)→ 3개씩 비트를 붙이면서 가중치가 최대가 되도록 계산  https://www.a..

https://www.acmicpc.net/problem/2405 중위값과 평균값이 세 개 이상이 되도록 하는 숫자 3개를 고르는 문제이다.어떻게 하면 중위값과 평균값이 가장 커질까를 생각해야하는데숫자들을 정렬한 후에 1. 0번째 인덱스의 숫자를 고정시키고 이후 i번째 i+1번째 숫자를 선택하여 차이가 가장 커지는 순간을 구함2. n-1번째 인덱스의 숫자를 고정시키고 이후 i번째 i+1번째 숫자를 선택하여 차이가 가장 커지는 순간을 구함 1번과 2번을 모두 수행한 결과 나온 가장 큰 차이가 답이 된다. #include #include #include #include using namespace std;int main() { int n, avg, ans, tmp; cin >> n; vector v(n); ..

Greedy 알고리즘은 매 단계에서 현재 상황에서 가장 최선이라고 생각되는 선택을 하는 방식으로 문제를 해결하는 알고리즘 기법이다.특정 상황에만 사용되는 최적의 해를 구하는데 사용한다. 정의만 보았을 때는 무슨 말인지 잘 이해가 안 갈수 있다.문제가 주어지면 어떻게 코드를 짜야지 가장 최고의 효율로 문제를 해결할 수 있는지 고민해야하는 문제다.즉, 특정 알고리즘 공식이 있는게 아니라 각 문제 상황마다 다른 최적의 해를 직접 구상해내야 한다.예시를 통해 알아보자거스름돈 문제[문제]거스름돈으로 줄 금액이 주어졌을 때 동전의 개수가 최소가 되도록 동전을 조합하라.단, 사용가능한 동전의 단위는 500원, 100원, 50원, 10원만 가능하다. 해당 문제에 대한 최적의 알고리즘을 구하기 위한 접근1. 현재 상황에..

https://www.acmicpc.net/problem/19846constructive 문제에 익숙하지 않으면 숨이 턱 막히는 문제일 수 있다.constructive는 문제를 한 발짝 뒤에서 바라볼 수 있어야 한다. 이번 문제는 각 구간에 대해 홀수번 나오는 문자가 단 한 개인 예시를 만드는 문제이다.구간도 여러개이고, 어떤 구간이 테스트 케이스로 주어질지 모르는데 그리디처럼 접근하면 코드가 매우 길어지고난이도도 많이 올라간다. Greedy 사고: 주어진 입력을 잘 활용하여 최적의 솔루션을 찾는 것즉, 예시로부터 귀납적으로 생각해서 일반화하는 느낌Constructive 사고: 입력과 같은 특정 구간이 아니라 어떠한 구간이 입력으로 주어지더라도 가능한 경우를 생각하는 것즉, 문제 전체를 아우르는(?) 답..

https://www.acmicpc.net/problem/13018이 문제는 특이한 수열 A를 찾는 문제이다. 특이한 수열의 성질은 다음과 같다.수열 A의 길이는 n1이상 n이하의 정수가 빠짐없이 모두 등장해야 하며, 각 수는 한번만 등장해야함1 ≤ i ≤ n 인 i에 대해 gcd(i, A[i]) > 1 을 만족하는 i가 정확히 k개여야함n, k 가 주어졌을 때, 특이한 수열을 아무거나 하나 구해보자.gcd(i,A[i]) > 1을 만족하는 수는 i == A[i]이면 된다.따라서 i == A[i]를 만족하는 수를 k개 출력하면 되고 나머지 인덱스와 원소의 관계는 서로소되야 한다.i와 A[i]의 차가 1이거나 원소에 1이 있으면 항상 gcd(i,A[i]) = 1(서로소)을 만족한다. 1~N까지의 원소를 활용..

https://www.acmicpc.net/problem/30297 순열P를 irreducible한 순열로 만드는 문제이다.reducible의 정의로는 배열의 앞에서 하나씩 원소를 떼서 부분집합을 만들었을 때 순열을 만족하면 reducible한 순열이다.(단, 자기 자신은 제외) irreducible한 순열이 되기 위해서는...i번째 원소까지의 최대값이 i보다 커질수 있도록 스왑하면서 이동하면 된다.입력으로 주어지는 N의 값의 합이 500000이하인 것이 보장되므로 테스트 케이스 하나당 O(N)으로 해결하면 된다. #include #include #include #define endl "\n"using namespace std;int t, n, m, tmp;int main() { ios_base::syn..