배열을 뒤집어서 다른 배열과 대응하는 원소끼리 곱의 합의 특징

8973번: 수학 공책 길이가 n인 두 수열이 존재하는데 두 수열 사이 흐릿함은 두번째 수열을 뒤집어서, 같은 위치에 있는 두 수의 곱의 합이다 예를 들어 3 -4 -3 -3 0 5는 -3 0 5를 뒤집어서 5 0 -3으로 하고 같은 위치에 있는 원소끼리 5*3 + 0*-4 + -3*-3 = 9 + 15 = 24 앞에서부터 b개 뒤에서부터 e개를 지워서 두 수열의 흐릿함을 되도록 크게 만들고자 한다면, 최댓값을 구하고 b,e를 구한다 --------------------------------------------------------------------------------------------------------------- 쉽게 생각할 수 있는건 앞에서부터 b개를 지우고 뒤에서부터 e개를 지웠을때..

• format_list_bulleted 다이나믹 프로그래밍
• · 2025. 4. 3.
• textsms

가장 많은 점을 포함하는 사각형 찾기 놀라운 방법

14658번: 하늘에서 별똥별이 빗발친다 최대 50만*50만의 2차원 평면 위에 k개  최대 10만*10만의 L*L 정사각형으로 가장 많은 점을 포함시키려고 할때, 이 정사각형에 포함되지 않는 점의 개수를 구한다 정사각형의 모서리에 포함되어도 포함된 것으로 인정한다 ---------------------------------------------------------------------------------------------------------------------------------------------- 문제의 조건을 만족하는, 평면 위에 가장 많은 점을 포함하는 정사각형의 배치는 반드시 존재할 수 밖에 없다. 그러한 최적 배치에 들어가있는 모든 별을 포함할 수만 있다면, 정사각형의 배치는 ..

• format_list_bulleted 브루트포스
• · 2025. 3. 30.
• textsms

그래프에서 역방향 간선을 놓아 노드들의 크기 순서를 찾는 테크닉(도달 가능성)

1. 문제 2458번: 키 순서  1번부터 n번까지 번호가 붙여진 학생들의 키 순서가 주어진다. 예를 들어 1번  이 결과로 모든 학생중 키가 가장 작은 학생부터 자신이 몇번째 학생인지 알 수 있는 학생도 있고,  그렇지 못한 학생들도 있다. 이러한 결과가 주어질때 자신의 키가 몇번째 학생인지 정확히 알 수 있는 학생 수를 구한다 ------------------------------------------------------------------------------------------------------------------------------------------------ 상식적으로? 먼저 생각해보면 i번이 몇번째 순서인지 알고 싶다면 i번보다 키가 큰 학생의 수, 키가 작은 학생의 수를 찾..

• format_list_bulleted 그래프 이론 정복기
• · 2025. 3. 29.
• textsms

야바위에서 바로 왼쪽이나 오른쪽으로 한번만 이동시킬 수 있을때 가능한 위치 구하기

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXTC3GH6D-EDFASe SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com  n개의 컵이 일렬로 늘어서있는데, 처음에 1번 컵에 공이 들어있다. 이 때 i번째 시행에서 ai번 컵과 bi번 컵을 서로 바꾼다. 임의의 시점에 정확히 한번, i번에 있는 공을 i-1번 컵이나 i+1번 컵으로 옮긴다. 전부 섞고 나서, 공이 있을 수 있는 모든 위치의 개수는? ----------------------------------------------------------------------..

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

연속하는 구간을 한번 뒤집어야할때 켜져있는 원소들의 합의 최댓값을 구하는 놀라운 방법

25634번: 전구 상태 뒤집기  전구의 밝기들이 배열로 주어지고, 초기에 켜져있는지, 꺼져있는지가 주어진다. 연속하는 구간내의 모든 전구들의 상태를 뒤집으면 켜진 전구는 꺼지고, 꺼진 전구는 켜진다. 이 연산을 정확히 1번 해야할때, 전구 밝기들의 합의 최댓값을 구한다. ---------------------------------------------------------------------------------------------------------------------------------------------------- n이 최대 20만인데, 연속하는 구간의 상태를 뒤집어야한다? 구간 dp로 하자니 O(N^2)일텐데  그리고 연산을 무조건 1번은 해야한다는거까지 굉장히 어렵다 처음 상태에서..

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

한번 쉬면 끝까지 쉬어야할 때 최대한 멀리 달리는 다이나믹 프로그래밍

1757번: 달려달려 n분 동안 달리는데 1분 달리면 지침 지수가 1 올라간다 1분 쉬면 지침 지수가 1 내려간다 지침 지수가 m보다 커지면 달릴 수 없다 한번 쉬면 지침 지수가 0이 될 때까지 쉬어야한다 또한 달리기가 끝난 n분에 지침지수가 0이 되어야한다 i분에 달릴 수 있는 거리가 주어진다. D = [5,3,4,2,10]이면 1분에 달리면 5만큼 뛰고 2분에 달리면 3만큼 뛴다는 소리 이때 가장 멀리 달릴 수 있는 거리는? ------------------------------------------------------------------------------------------------------------------------------------------------- i번째 시간에 지침..

• format_list_bulleted 다이나믹 프로그래밍
• · 2025. 3. 19.
• textsms