안 쓰던 블로그

자주 쓰는 비트연산 정리 (feat. 펜윅트리) (1

오늘은 세그트리 달린다 https://www.acmicpc.net/blog/view/9 세그먼트 트리 (Segment Tree) 문제 배열 A가 있고, 여기서 다음과 같은 두 연산을 수행해야하는 문제를 생각해봅시다. 구간 l, r (l ≤ r)이 주어졌을 때, A[l] + A[l+1] + ... + A[r-1] + A[r]을 구해서 출력하기 i번째 수를 v로 바꾸기. A[i www.acmicpc.net 최대/최소값 찾기 12015 가장 긴 증가하는 부분 수열2 tree[i] = 수 A[i]를 마지막으로 하는 LIS의 길이로 두면, 1) i보다 앞에 있으면서(j

골딱이의 플레찍기 일기 실버 골드들 복습이랑 플레 문제들 위주로 재밌어보이는 거 풀 것 같음 16975 수열과 쿼리 21 더보기 https://www.acmicpc.net/blog/view/88 펜윅 트리 200% 활용하기 흔히 lazy propagation을 사용하여 푸는 것으로 알려진 이 두 문제는 사실 펜윅 트리만으로 풀 수 있습니다. 구간 덧셈, 포인트 쿼리 다음 연산을 효율적으로 수행하는 자료구조를 만들어 봅시다. 이것으로 16975번 - 수열과 쿼리 21을 풀 수 있습니다. $A_L$, $A_{L+1}$, $\cdots$, $A_R$에 각각 x씩 더한다. $A_k$를 출력한다. $B_1 = A_1$, $B_k = A_k - A_{k-1}$이라고 두면, 각각의 쿼리 www.acmicpc.net ..

https://www.acmicpc.net/blog/view/88 펜윅 트리 200% 활용하기 흔히 lazy propagation을 사용하여 푸는 것으로 알려진 이 두 문제는 사실 펜윅 트리만으로 풀 수 있습니다. 구간 덧셈, 포인트 쿼리 다음 연산을 효율적으로 수행하는 자료구조를 만들어 봅시다. 이것으로 16975번 - 수열과 쿼리 21을 풀 수 있습니다. $A_L$, $A_{L+1}$, $\cdots$, $A_R$에 각각 x씩 더한다. $A_k$를 출력한다. $B_1 = A_1$, $B_k = A_k - A_{k-1}$이라고 두면, 각각의 쿼리 www.acmicpc.net https://blog.naver.com/jh05013/221475142152 BOJ 16975부터 16979까지 16975 수열..

https://programmers.co.kr/learn/courses/18/lessons/1879 알고리즘 문제 해설 - 가장 큰 정사각형 찾기 | 프로그래머스 [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] 9 programmers.co.kr 처음에 문제를 읽고 생각한 풀이는 전체 배열을 돌면서 1을 만나면 dfs를 시작해서 오른쪽, 오른쪽 아래, 아래가 전부 1이면 정사각형이니까 재귀를 다시 돌리는 식으로 (chk배열로 방문 체크랑 범위 체크하면서) 전형적인 dfs문제처럼 풀려고 했는데 그런 방법을 구현하는데 메인함수에 for문이 무슨 5중까지 가고 알 수 없는 에러 터지고 아무리 생각해도 에바라 전부 없애고 다시 접근했다 아래는 망한 코드(미완성) /*int dx[] =..

https://programmers.co.kr/learn/courses/18/lessons/1880 알고리즘 문제 해설 - 땅따먹기 | 프로그래머스 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다. 예를 들면, | 1 | 2 | 3 | 5 | | 5 | 6 | 7 | 8 | | 4 | 3 | 2 | 1 | 로 땅이 주어졌다면 programmers.co.kr ABCD 1234 이렇게 수가 있다고 치면 A에 들어갈 최대 값은 A+2..

단순 구현 어떤 알고리즘을 써서 문제를 풀 때도 구현이라고 하지만 여기서는 말 그대로 '문제를 읽고, 문제 자체를 구현'하는 단순 구현 문제를 의미합니다 단순 구현 문제는 보통 문제에 답이 있는 경우가 많으며, 문제를 읽고 가장 단순하게 생각해서 푸는 문제들도 단순 구현에 속합니다. 이렇게 단순 구현 문제들을 풀어둔다면 나중에 더 어려운 문제를 접하더라도, 문제를 단순하게 푸는 방법을 생각한다->시간이나 메모리를 더 줄일려면 어떻게 해야되지? 어떤 알고리즘을 써야되지? 이런 식으로 생각을 넓혀갈 수 있습니다. 단순 구현 문제는 간단히 풀리는 경우가 많으므로 문제풀이 공부에 회의감이 들거나 자존감이 낮아졌을 때, 재미로 풀면서 다시 공부하고자 하는 의지를 충전 할 수 있습니다. 먼저 문제만 보고 풀어본다-..