인접한 원소의 곱의 합이 최대가 되도록 수열을 만드는 방법

16209번: 수열 섞기 수열 a1,a2,...,an이 주어질때 인접한 원소들의 곱 a1a2 + a2a3+... + an-1an이 최대가 되도록 수열을 섞고 싶다 그렇게 섞은 수열 하나만 구한다 ----------------------------------------------------------------------------------------------------------------------------------------------------------- 적어도 양수는 양수끼리, 음수는 음수끼리 곱해야 한다는 것을 생각할 수 있다 또한 절댓값이 큰 것끼리 곱해야 커진다는 것도 생각할 수 있다 양수 그룹에서 큰 값들을 먼저 찾아서 a1 > a2 > .... > an이라고 한다면... a1 a..

  • format_list_bulleted 그리디 알고리즘
  • · 2025. 2. 20.
  • textsms
똑같은 원소를 연속해서 사용하지 않도록 최대한 쓰는 놀라운 그리디 알고리즘

똑같은 원소를 연속해서 사용하지 않도록 최대한 쓰는 놀라운 그리디 알고리즘

25635번: 자유 이용권 i번째 놀이기구 이용권의 횟수가 A[i]로 주어진다 모든 놀이기구를 이용하고 싶은데 연속으로 같은 놀이기구를 사용하지 않는다 최대 몇번 사용가능한가? A = [1,1,3]이면 3번, 2번, 3번, 1번, 3번으로 5번 가능하다 처음에 생각하기에는 무조건 큰 값끼리 모아서 쌍으로 이용하면 된다고 생각을 했는데 A = [1,2,3,4,5]라고 한다면  5번 이용가능한거랑 4번 이용가능한거 모아서 5 4 5 4 5 4 5 4 이렇게 하면 8번 쓰는거고 5가 1번 남고 [1,2,3,0,1]에서  3,5 해서 3번이 2번 남고 [1,2,2,0,0]에서 3번 2번 가져와서 3,2,3,2 해서 [1,0,0,0,0] 해서 1번을 쓰면 된다는 식으로 n = int(input())A = list..

  • format_list_bulleted 그리디 알고리즘
  • · 2025. 1. 21.
  • textsms
합과 bitwise or연산이 같게되는 조건

합과 bitwise or연산이 같게되는 조건

1322번: X와 K  x+y = x | y를 만족하는 k번째로 작은 자연수 y를 구하는 문제 합과 or 연산이 서로 같게되는 조건을 먼저 생각해본다 or연산은 두 bit가 1이면 1이고 두 bit가 0이면 0이고 두 bit가 1,0으로 서로 다르면 1인 연산 두 수를 합하는 것은 어떤 의미인지 생각해본다 x,y를 2진수로 바꿔서 예를 들어 5 = 101이고 12 = 1100인데 이진수끼리 서로 덧셈은 어떻게 하는가? 101=0∗23+1∗22+0∗21+1∗20 1100=1∗23+1∗22+0∗21+0∗20 우측에 2의 거듭제곱으로 바꾼 것끼리 더한다고 생각해보면,  $(0 + 1)*2^{3} + (1+1..

  • format_list_bulleted 비트마스킹
  • · 2025. 1. 9.
  • textsms

(두 위치의 거리 * 두 위치의 원소 중 최솟값)의 최댓값을 투포인터로 찾는 방법

22945번: 팀 빌딩  n명이 한줄로 서있을 때 2명을 골라 그 2명 사이의 사람 수 * min(첫번째 사람의 능력치, 두번째 사람의 능력치)의 최댓값을 찾는 문제 [1,4,2,5]이면 A[1] = 4, A[3] = 5이고 두 사람 사이에는 1명 있고 둘 중 최솟값은 4니까 4가 최댓값이다 투 포인터로 해결할 수 있다해서 연습삼아 풀어볼려했는데 기존에 알던 투 포인터 풀이는 안먹히니 답이 없다 인덱스랑 같이 넣어서 정렬해야하나 일단 정렬이 안되어있고 포인터 움직여도... min값이 커졌다 작아졌다 하는데 근데 0번과 n-1번에 포인터를 두고 서로 간격을 좁혀가면 된다는데 그래도 어떻게 해야하는지 고민되더라고 A[i], A[i+1], A[i+2], A[i+3], ...., A[j] i번과 j번을 가리키고..

  • format_list_bulleted 투 포인터 알고리즘
  • · 2025. 1. 7.
  • 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