본문 바로가기

Algorithm/Baekjoon38

11660_구간 합 구하기 5 ▶실버1 풀이 누적 합 이용. 0 1 2 3 4 0 0 0 0 0 0 1 0 1 2 3 4 2 0 2 3 4 5 3 0 3 4 5 6 4 0 4 5 6 7 => 배열 표 0 1 2 3 4 0 0 0 0 0 0 1 0 1 3 6 10 2 0 3 8 15 24 3 0 6 15 27 42 4 0 10 24 42 64 => 누적 합 표 ex) (2, 2) ~ (3, 4) 의 구간 합 이는 8 + 15 + 24 + 15 + 27 + 42 와 같은데, 누적합을 이용하면 sum[3][4] - sum[3][1] - sum[1][4] + sum[1][1] 임을 알 수 있다. 이를 통하여 (x1, y1) ~ (x2, y2)의 구간 합의 점화식은 sum[x2][y2] - sum[x2][y1 -1] - sum[x1 - 1][.. 2023. 1. 11.
11055_가장 큰 증가 부분 수열 ▶실버2 풀이 기본적으로 dp[i] = arr[i]인 상태에서 arr[j](이전 값) < arr[i](현재 기준값)을 만족할 때, dp[j] + arr[i] 와 dp[i] 중 큰 값을 선택하여 dp[i]에 대입한다. 위의 예제를 표로 나타내면 1 100 2 50 60 3 5 6 7 8 1 101 1 + 2 = 3 max(1, 3) + 50 = 53 max(1, 3, 53) + 60 = 113 max(1, 3) + 3 = 6 max(1, 3, 6) + 5 = 11 max(1, 3, 6, 11) + 6 = 17 max(1, 3, 6, 11, 17) + 7 = 24 max(1, 3, 6, 11, 17, 24) + 8 = 32 dp값 중 가장 큰 값이 답 코드 #include #include #include u.. 2023. 1. 10.
11057_오르막수 ▶실버1 풀이 처음에는 왜 dp인지 이해가 가지 않음 -> 모든 수를 탐색하며 오르막 수인지 확인하는 작업을 하기엔 시간이 너무 많이 걸리기 때문에 dp로 처리 만약 0_ _이면 한 자리가 추가될 때 0 0 _ _ (1가지) 만 가능 1 _ _이면 0 1 _ _, 1 1 _ _ (2가지) 가능 .... 9 _ _이면 0 9 _ _, 1 9 _ _, ~ , 9 9 _ _ (10가지) 가능 이런 식으로 생각하면 자릿수와 맨 앞 자리의 수가 무엇인지를 따져 `dp[i][j] : 맨 앞 자리 수가 j인 i자리의 수의 개수` 로 놓는다. ex) 3자리 수 오르막 수 구하기 3자리 수의 오르막 수의 개수를 구하기 위해서는 dp[3][0] + dp[3][1] + ... + dp[3][9] 을 구하면 되는데 dp[3].. 2023. 1. 4.
2003_수들의 합 2 ▶실버4 풀이 투 포인터를 이용한 문제. 같은 방향으로 L, R가 나아가는 형태이다. 먼저 L과 R은 모두 인덱스 0번째를 가리킨다. A[L] ~ A[R]의 합인 sum이 m보다 작다면 sum의 값을 늘려야하므로 R을 오른쪽으로 한 칸 이동하고, sum이 m보다 크다면 sum의 값을 줄여야하므로 L을 오른쪽으로 한 칸 이동한다. sum == m인 경우는 R, L 모두 오른쪽으로 한 칸 이동한다. R이 N을 벗어나기 전까지 진행한다. 코드 #include #include #include using namespace std; int A[10001]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int l = 0, r = 0;.. 2023. 1. 2.
21921_블로그 ▶실버3 풀이 누적 합을 이용한다. 예제 1번을 예시로 들면 n = 5, x = 2 1 4 2 5 1 1 5 7 12 13 로 누적 합을 구한다. 이때, x = 2이므로 arr[i] - arr[i - 2]를 한 값들을 벡터에 넣고 내림차순 정렬한 뒤 최댓값이 몇 개 있는지 센다. 벡터에 들어가는 값은 6, 7, 6인데 실제로는 5, 6, 7, 6이어야 한다. 따라서 배열 맨 앞에 0을 넣고 구하는 것이 맞다. 코드 #include #include #include #include using namespace std; int visitor[250001]; vector sum; bool compare(int i, int j) { return j < i; } int main(void) { cin.tie(0); .. 2023. 1. 1.
2583_영역 구하기 ▶실버1 풀이 2차원 bfs문제. 점을 기준으로 탐색하는게 아니라 영역기준이므로 다음과 같은 형태로 정사각형 네 꼭짓점 중 왼쪽 아래를 기준으로 잡는다. x, y 값이 주어지면 for문으로 해당 범위 내의 arr[x][y]의 값을 true로 바꿔준다. 모든 범위가 주어지고 나면 (0, 0)부터 (n - 1, m - 1)까지 돌며 bfs 실행. 코드 #include #include #include #include #include #include #include #include using namespace std; queue q; int r[4] = { 1, -1, 0, 0 }; int c[4] = { 0, 0, 1, -1 }; bool arr[251][251]; int land; vector ans; in.. 2022. 11. 11.

티스토리툴바