인접한 두 수를 분해하여 적절하게 바꿔서 정렬하는 방법

33708번: 인수분해 정렬 두 수 A[i]와 A[i+1]을 a*b = A[i]*A[i+1], a+b != A[i]+A[i+1]을 만족하는 a,b로 바꿀 때  원하는 만큼 이 연산을 시행해서 주어진 수열 A를 비내림차순으로 바꿀 수 있는가? ------------------------------------------------------------------------------------------------------------------------------------------- a = 1, b = A[i]*A[i+1]이라고 하면, A[i],A[i+1]을 반드시 1,A[i]*A[i+1] 반대로 a = A[i]*A[i+1], b = 1이라고 하면 A[i],A[i+1]을 반드시 A[i]*A[i+1],..

  • format_list_bulleted 애드 혹 알고리즘
  • · 2025. 4. 10.
  • textsms

서로 순열이 되는 경우를 찾는 트릭(정렬해서 비교하기)

1501번: 영어 읽기 영어 단어의 첫글자와 끝글자가 서로 같고 그 사이의 글자가 순서가 뒤섞인채로 구성이 같으면 같은 단어로 취급한다 abcde는 acbde, abdce,... 등과 같다 단어 사전과 문장들이 주어질때 각 문장을 해석하는 방법의 수를 구한다 ------------------------------------------------------------------------------------------------------------------------------------------- 영어 단어가 bakers, brakes, breaks,...등이 주어질때 먼저 bakers를 보면 bakers, bkaers, bekras, berkas, bearks,... 등이 서로 같은 단어들이다...

  • format_list_bulleted 애드 혹 알고리즘
  • · 2025. 3. 5.
  • textsms

4개 원소를 골라서 짝지어서 쌍을 만들어 크기 비교하는 놀라운 방법

20366번: 같이 눈사람 만들래? n개의 눈덩이가 있는데, 2개의 눈덩이를 합쳐서 1개의 눈사람을 만들 수 있다 n개중 4개의 눈덩이를 골라 2개의 눈사람을 만들려고 한다 이때 눈덩이 크기의 합이 눈사람의 크기라고 할때, 두 눈사람의 크기 차이가 최소가 되도록 하려고 한다 최솟값을 구하면? -------------------------------------------------------------------------------------------------------------------------------------------------------- n이 최대 600인데 이중 4개를 고르면 600C4로 못해도 600*599*598*597 정도에 근사하는 정도? 아무튼 10^8을 가뿐하게 넘는다..

  • format_list_bulleted 정렬 알고리즘
  • · 2025. 3. 4.
  • textsms

배열의 모든 수의 관계가 약수 배수 관계가 되도록 만드는 다이나믹 프로그래밍

19576번: 약수 주어진 배열의 어떤 수를 양의 정수로 바꿔서 임의의 두 수 x,y를 골랐을 때 x가 y로 나누어 떨어지거나, y가 x로 나누어 떨어지도록 만들고 싶다. 이때 양의 정수로 바꾸는 행위를 최소로 하고자 할 때 최소 몇번 바꿔야하는가? --------------------------------------------------------------------------------------------------------------------------------------------------------------- 어떤 수로 바꾸는가?에 대한 문제는 되지 않는다  1은 모든 수의 약수이기 때문에 그냥 1로 바꾸면 되기 때문이다. 그렇다면 몇번 바꿔야하는지는 어떻게 알아내는가? 주어진 배열..

  • format_list_bulleted 다이나믹 프로그래밍
  • · 2025. 2. 24.
  • textsms

m개의 원소를 조건에 맞게 n개의 원소에 배치하는 방법

C - Kaiten Sushi  C - Kaiten SushiAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp  i번째 사람의 미각 점수는 A[i]로 주어지고, j번째 초밥은 맛 점수가 B[j]로 주어진다. j = 1,2,..,m번 초밥이 1번부터 n번 사람에게 순서대로 주어지는데 A[i]  각각의 초밥이 어떤 사람에게 먹어지는지 결정한다. n,m  예를 들어 A = [3,8,2], B = [5,2,1]인데 B[0] = 5가 1번 사람에게 주어질때, A[0]  B[1] = 2가 1번 사람에게 주어지는데, A[0] > B[1]..

  • format_list_bulleted 애드 혹 알고리즘
  • · 2024. 12. 2.
  • textsms

재배열 부등식(rearrangement inequality)을 이용한 내적의 최대 최소

1. 재배열 부등식(rearrangement inequality) 실수 x11,2,..,n의임의의순열\sigma_{1}, \sigma_{2}, ... , \sigma_{n}으로부터x1yn+x2yn−1+...+xny12.증명S1 = x_{1}y_{1} + x_{2}y_{2} + .... + x_{a}y_{a} + .... + x_{b}y_{b} + ... + x_{n}y_{n}에서y_{a}  S2=x1y1+x2y2+...+xayb+...+xbya+...+xnyn 둘을 뺴면 $S1 - S2 = x_{a}(y_{a} - y_{b}) + x_{..

  • format_list_bulleted 그리디 알고리즘
  • · 2024. 11. 22.
  • textsms