전체 글

문제 풀이 다이나믹 프로그래밍 문제이다. https://kantatatam.tistory.com/155 [백준][C++] 27210: 신을 모시는 사당 문제 풀이 다이나믹 프로그래밍, 누적 합 문제이다. 완전 탐색으로 해결하려고 하면 O(N * N)으로 시간 초과이다. 배열을 두 개를 사용하여 문제를 해결해야 한다. 첫 요소가 왼쪽인 배열. 왼쪽이 kantatatam.tistory.com 위의 문제와 유사하다. 선택한 수의 배열의 총합을 current로 생각한다. 배열을 탐색하면서 current에 현재 요소의 값(nums[i])을 더한다. current가 현재 요소의 값보다 작다면, 기존의 배열을 버리고, 현재 요소를 첫 요소로 하는 새로운 배열을 생성한다. current의 최댓값이 답이다. 코드 #in..

문제 풀이 다이나믹 프로그래밍, 누적 합 문제이다. 완전 탐색으로 해결하려고 하면 O(N * N)으로 시간 초과이다. 배열을 두 개를 사용하여 문제를 해결해야 한다. 첫 요소가 왼쪽인 배열. 왼쪽이 과반수인 배열. (left) 첫 요소가 오른쪽인 배열. 오른쪽이 과반수인 배열. (right) 전체 배열을 탐색하면서 돌상이 왼쪽인 경우에는, left 배열의 깨달음의 양이 1 증가하면서, right 배열의 깨달음의 양이 1 감소한다. 돌상이 오른쪽인 경우에는, left 배열의 깨달음의 양이 1 감소하면서, right 배열의 깨달음의 양이 1 증가한다. 현재 배열의 깨달음의 양이 0미만이라면 해당 배열을 버린다. 현재 배열 2개의 깨달음의 양의 최대값이 답이다. 코드 #include #include using..

51: new 및 delete를 작성할 때 따라야 할 기존의 관례를 잘 알아 두자 operator new를 구현 하려면 다음의 요구사항만큼은 기본으로 지켜야 한다. 반환 값이 제대로 되어있어야 한다. 가용 메모리가 부족할 경우에는 new 처리자 함수를 호출해야 한다. 크기가 없는(0바이트) 메모리 요청에 대한 대비책을 갖춰야 한다. 실수로 "기본(normal)" 형태의 new가 가려지지 않도록 해야 한다. 반환 값 부분은 간단하다. 요청된 메모리를 마련해 줄 수 있으면 그 메모리에 대한 포인터를 반환하는 것으로 끝이다. 메모리를 마련해 줄 수 없을 때는, 항목 49에서 이야기한 규칙을 따라서 bad_alloc 타입의 예외를 던지게 하면 된다. 지금까지의 요구사항을 정리해서, 비멤버 버전의 operator..

문제 풀이 누적 합 문제이다. https://kantatatam.tistory.com/143 [백준][C++] 30508: 고인물이싫어 문제 풀이 그래프 탐색, 누적합 문제이다. 횡단보도의 칸 중에서 물이 빠질 칸을 BFS로 탐색한다. BFS의 시작은 하수구 칸에서 시작한다. 현재 탐색 중인 칸의 상하좌우 칸 중에서, 현재 칸의 높이 kantatatam.tistory.com 2차원 배열에서의 누적 합을 구하는 문제로 위의 30508번 문제와 거의 동일하다. 코드 #include using namespace std; int nums[1001][1001]; int sum[1001][1001]; int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.t..

1. 도형 예제를, GeometryGenerator::CreateSphere 대신 GeometryGeneartor::CreateGeosphere를 사용하도록 수정하고, 세부 수준을 0, 1, 2, 3으로 바꿔보자. 3. 8장의 두개골 메시를 적재해서 렌더링해보자. 8장의 연습문제 'LitColumns' 예제 폴더의 Models/Skull.txt는 정점 목록과 색인 목록이 들어있다. 일단 이 두개골의 정점과 색인을 읽어서 정점 버퍼와 색인 버퍼를 만들어야 한다. 그 후, 기하구조 보조 구조체인 MeshGeometry를 채워서 멤버 데이터인 Geometries에 집어넣는다. void ShapesApp::BuildSkullGeometry() { std::ifstream fin("Models/skull.txt"..

50: new 및 delete를 언제 바꿔야 좋은 소리를 들을지를 파악해 두자 컴파일러의 기본 operator new와 operator delete를 바꾸고 싶은 가장 흔한 이유 세 가지를 보면 다음과 같다. 잘못된 힙 사용을 탐지하기 위해 new한 메모리에 delete를 잊으면 메모리가 누출된다. 두 번 이상 delete하면 미정의 동작이 발생한다. 만일 할당된 메모리 주소의 목록을 operator new가 유지해 두고 operator delete가 그 목록으로부터 주소를 하나씩 제거해 주게 만들어져 있다면, 이런 식의 실수는 쉽게 잡아낼 수 있을 것이다. 데이터 오버런(overrun) 및 언더런(underrun)을 대비하여 operator new를 활용한다면, 요구된 크기보다 약간 더 메모리를 할당한..

문제 풀이 그리디, 누적 합, 많은 조건 분기 문제이다. N의 최대가 10000이므로 O(N * N)으로는 100점이 불가능하다. 꿀을 가장 많이 채집할 수 있는 경우는 밑의 세 가지이다. 벌집이 가운데 어딘가에 있고, 벌이 가장 왼쪽, 오른쪽에 위치하는 경우 벌집이 가장 왼쪽에 있고, 한 벌은 가장 오른쪽, 한 벌은 가운데 어딘가에 위치하는 경우 벌집이 가장 오른쪽에 있고, 한 벌은 가장 왼쪽, 한 벌은 가운데 어딘가에 위치하는 경우 벌집이 가장 왼쪽 혹은 오른쪽에 위치하는 경우, 한 벌이 벌집과 가장 멀리있는 것이 꿀을 채집하는데 가장 유리하다(최선의 선택). 채집한 꿀을 계산할 때, 누적 합이 사용된다. 코드 #include using namespace std; int sum[100001]; int..

49: new 처리자의 동작 원리를 제대로 이해하자 메모리 할당이 제대로 되지 못한 상황에 대한 반응으로 operator new가 예외를 던지기 전에, 이 함수가 사용자 쪽에서 지정할 수 있는 에러 처리 함수를 우선적으로 호출하도록 되어 있는데, 이 에러 처리 함수를 가리켜 new 처리자(new-handler)라고 한다. 표준 라이브러리에는 set_new_handler라는 함수가있다. void outOfMem() { std::cerr

문제 풀이 누적 합 문제이다. O(N * N)이 되면 50점이다. O(N)의 시간복잡도로 해결해야한다. 문자열의 처음부터 시작하여 i번째까지 나온 알파벳마다 배열에 저장해둔다. i번째 문자열이 j일 경우, 이전 j가 등장한 횟수에서 + 1한 값을 배열에 저장한다. 그외에는 이전에 등장한 횟수로 저장한다. 코드 #include using namespace std; int alpha[26][200000]; int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); string S; cin >> S; // 문자열의 처음부터 시작하여 i번째까지 나온 알파벳을 배열에 저장 alpha[S[0] - 'a'][0]++; for (int i = 1..

문제 풀이 수학, 누적 합 문제이다. N이 1000,000이므로 완전 탐색시 O(N * N)으로 시간초과이다. (A - B) % n = ((A % n) - (B % n) + n) % n 배열의 i번째 수까지의 누적 합을 sum이라고 하자. 임의의 j번째에서 k번째 까지(j > N >> M; // 지금까지의 합인 sum // (sum - x) % M == 0인 경우에 답을 만족하므로, // ((sum % M) - (x % M) + M) % M == 0을 만족해야 한다. // 즉, sum % M == x % M인 x의 수가 answer에 추가된다. // sum % == 0인 경우에는 sum자체도 answer에 추가되야 한다. long long answer = 0; long long sum = 0; for (..