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

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

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

임의의 직사각형에 포함된 서로 다른 정수의 개수를 찾는 2차원 배열 누적합

14846번: 직사각형과 쿼리 n*n 배열에서 왼쪽 위가 (x1,y1), 오른쪽 아래가 (x2,y2)인 직사각형에 포함되는 서로 다른 정수의 개수를 찾는 쿼리가 많이 주어질 때 이 쿼리에 답한다 ------------------------------------------------------------------------------------------------------- n이 300인데 여기서 핵심은 행렬이 포함하고 있는 정수가 10까지라는 것이다 dp[y][x][i]를 왼쪽 위가 (0,0)이고 오른쪽 아래가 (x,y)인 직사각형에 포함된 정수 i의 개수로 정의한다 x,y가 300까지이고 i가 10까지니까 900000 정도로 메모리 적당 나머지는 여기서 배운 테크닉대로 하면 된다 https://d..

• format_list_bulleted 누적 합 알고리즘
• · 2025. 2. 7.
• textsms

중간에서 만나기 테크닉 - 저장하고 검사하는 것이 아니라 검사를 먼저하고 저장하기

5624번: 좋은 수 (acmicpc.net)  정수 배열에서 현재 위치 i번째 수 앞에 있는 수들 중 세 수의 합이 현재 위치 i번째 수와 같게 되는 경우,  그러한 수의 개수를 구하는 문제 "세 수"는 중복해서 선택해도 좋다 예를 들어 [-1,2,0]이면 0은 -1 -1 + 2 = 0이므로 이 조건에 만족하는 수이다 n이 최대 5000인데, 단순하게 짜면 $O(N^{4})$이라 매우 느리다 대충 이런 느낌 for i in range(n): a = A[i] for j in range(i): for k in range(i): for w in range(i): ..

• format_list_bulleted 중간에서 만나기
• · 2024. 6. 10.
• textsms

배열을 뒤집었을때 생기는 반전 수의 개수 구하기

25339번: 반전 수와 쿼리 (acmicpc.net)  반전 수는 i P[j]인 (i,j)의 개수를 말한다. 배열이 [3,2,1]이면 반전수는 (인덱스 말고) (3,2), (3,1), (2,1)로 3개가 있다. l번, r번을 서로 교환하는 쿼리 [l,r]의 배열을 서로 뒤집는 쿼리가 주어질 때, 매 쿼리마다 수열의 반전 수를 2로 나눈 나머지를 구하는 문제 ---------------------------------------------------------------------------------------------------------------------------------------------------------- 배열 길이와 쿼리 수가 엄청나다보니 단순한 방법으로는 시간초과 이 문제는..

• format_list_bulleted 애드 혹 알고리즘
• · 2024. 5. 23.
• textsms

python 리스트를 이용해 trie 구현하면서 개념 익히기

python에서는 trie가 class로 구현된 경우가 많아 꺼렸는데... 배열로 구현하는 법을 익혀서 기록해보기 https://deepdata.tistory.com/659 문자열 자료구조 Trie 알고리즘 기본기 배우기1. 문자열 단어 저장 'hello', 'hi', 'hey' 등을 저장하고자 할때, 생각할 수 있는 방법중 하나는 dictionary에 저장하는 것이다 d = {'hello':1, 'hi':1, 'hey':1} 단어를 key값으로 저장해두면, 특정 단어를 찾고자deepdata.tistory.com https://blog.encrypted.gg/1059 [실전 알고리즘] 0x1F강 - 트라이안녕하세요, 드디어 마지막 강이라니 가슴이 웅장해집니다. 마지막인만큼 난이도도 끝판왕일 수 있지만 개..

• format_list_bulleted 고급 자료구조
• · 2024. 5. 14.
• textsms