알고리즘 문제/Codeground10 [codeground] 52. 최대 직사각형 codeground - Practice - 연습문제 - 52. 최대 직사각형 문제 : https://www.codeground.org/practice/practiceProblemList 2차원 배열에서 만들 수 있는 모든 직사각형들의 배열 합 중 최대값을 구하는 문제다. 직사각형을 [그림 1] 순서로 탐색하였다. 그런데 실제로는 1,2를 합친 것, 3,4를 합친 것, 5,6을 합친 것 또한 직사각형도 탐색을 해야 하므로 추가적인 알고리즘이 더 필요하다. 이를 위해 변수 2개를 사용한다. tmp는 현재 탐색 중인 직사각형(빨간색)의 배열 합을 의미한다. row는 현재까지 탐색한 열 범위([그림 2]에서 열 범위는 1~2)로 만들 수 있는 직사각형들 중 가장 큰 배열의 합을 의미한다. 즉, [그림 3] 처럼.. 2019. 9. 12. [codeground] 8. 블럭 없애기 codeground - Practice - 연습문제 - 8. 블럭 없애기 문제 : https://www.codeground.org/practice/practiceProblemList 1. i번째 블럭 높이(h) a h b -> 높이가 h인 블럭 없어지는데 걸리는 시간 = h 2. i번째 블럭(h)의 양쪽 블럭이 없어지는데 걸리는 시간 중 최소값 + 1 a h b -> 높이가 h인 블럭 없어지는데 걸리는 시간 = (a, b 중 작은 값) + 1 i번째 블럭이 없어질 때까지 걸리는 시간은 1, 2번 중 최소값이다. int d[n + 2];//d[i] = i번째 블럭이 없어질 때까지 걸리는 시간 즉, d[i] = min(d[i-1] + 1 , d[i+1] + 1, i번 블럭 높이) i 번째 블럭이 모두 없어지.. 2019. 9. 2. [codeground] 36. 재활용 codeground - Practice - SCPC 2회 본선 - 36. 재활용 문제 : https://www.codeground.org/practice/practiceProblemList vector arr; //arr[i] : i집의 x위치 vector sum; //sum[i] : 1~i 집들의 x위치 합 int d[501][501]; //d[s][k] : s~n 까지의 집이 k개의 수집통에 재활용을 넣는 경우 드는 최소 비용 int go(int s, int k) //d[s][k] 채우는 함수 일단 x좌표에 대해 오름차순 정렬해준다. 이제 d배열을 채워보자. 만약 a~e 집이 1개의 재활용 수집통을 사용한다고 했을 때, 가장 적절한 수집통의 위치는 어디가 될까. 가장 적절한 수집통의 위치를 x라고 했.. 2019. 6. 12. [Codeground][74] 버스타기 문제 : https://www.codeground.org/practice/practiceProblemViewNew 5 3 1 4 3 7 9을 예로 들어보자. 일단 오름차순으로 정렬한다.1 3 4 7 9첫번째 수 1과 같은 버스를 탈 수 없는 바둑 기사와 같이 탈 수 있는 바둑기사를 나눠보면 다음과 같다.1 3 4 7 9차이가 작은 수들이 같은 버스를 탈 수 없다. 따라서 1과 같은 버스를 탈 수 없는 바둑 기사들은 각자 누구와도 같은 버스를 탈 수 없다. (정렬했기 때문에 빨간색 범위 내의 능력차이는 항상 3(4-1)보다 작다.)즉, 1 3 4는 각자 다른 버스를 타야하고 따라서 적어도 3개의 버스가 필요하다. 나머지 7과 9는 1번이 탄 버스에 같이 타면 되므로 같이 탈 수 없는 바둑 기사의 수만 고려.. 2018. 11. 16. 이전 1 2 다음
