본문 바로가기
반응형

[백준]214

[BaekJoon/백준] 10845번 C++ 큐를 직접 구현해보는 문제. 링버퍼 기반의 큐로 구현해주었다. 큐는 링버퍼기반으로 구현해주어야 작업의 시간복잡도가 감소한다. #include #include #include using namespace std; typedef struct { int *que; int front; int rear; int num; int max; } IntQueue; int Initialize(IntQueue *q, int s) { q->que = (int *)calloc(s, sizeof(int)); q->front = q->rear = q->num = 0; q->max = s; return 0; } int push(IntQueue *q, int x) { if(q->max num) return -1; q->num++; q.. 2021. 3. 24.
[BaekJoon/백준] 1074번 C++ 분할정복 분할정복 관련 문제다. 하지만 주의사항이 있다. 분할정복은 맞는데, 분할정복으로 모든 곳을 돌아서 값을 채우고, 그 배열을 이용하려 하면 시간초과가 날 것이다. 최대크기 32568 x 32578은 10억이 넘는다. 시간복잡도 O(n)에서 10억이면 10초정도 예상된다. 따라서 분할했을 때, 해당 섹션을 방문하지 않고도, 계산에 문제가 없도록 섹션의 크기를 계산해내는것이 중요하다. 문제에서 n을 입력 받을 때 변의 길이 = 2^n 역할의 n을 입력받으므로 1. 4^(n - 1)을 구역(섹션) 당 크기로 계산해도 되겠고 2. (현재 변의 길이 / 2)^2 을 구역 당 크기로 계산해도 되겠다. #include #include #include using namespace std; int N, C, i, j; i.. 2021. 3. 23.
[BaekJoon/백준] 1012번 C++ VISITED 배열을 따로 구현하신 분들이 많았는데, 이 문제에서는 딱히 구현해줄 필요 없이 기존 배열을 활용하여 VISITED 기능을 사용할 수 있다. #include #include #include using namespace std; int T; // 테스트 케이스 int arr[50][50]; // 논밭 최대 크기 int N, M; // 가로, 세로 int C; // 배추 수 int x, y; // 배추 위치를 위해 int total; // 전체 지렁이 갯수 // 인근 1 영역을 모두 0으로 만들어주는 함수. (재귀) void road(int x, int y) { if(arr[x][y] == 1) arr[x][y] = 0; else return; if(x - 1 >= 0) road(x - 1, y.. 2021. 3. 21.
[BaekJoon/백준] 10816번 C++ 문제는 두 가지 방법으로 풀었다. 감이 왔다가, 다시 헷갈렸다가... 조금 헤맸다. 결국에 처음 왔던 감 대로 도수분포표 정렬 할 때의 방식을 응용해서 풀었다. 정수 범위가 -10,000,000 ~ +10,000,000 이므로 20,000,000 이라고 보면 되고 int는 4바이트니까 총 80,000,000 byte의 공간이 필요한데, 메모리 제한이 256MB이므로 충분하다고 판단했다. 입출력은 속도가 빠른 C의 입출력을 가져와 썼다. #include #include using namespace std; int arr[20000000]; int main() { int N, M, temp; scanf("%d", &N); for(int i = 0; i < N; i++) { scanf("%d", &temp);.. 2021. 3. 21.
반응형

티스토리툴바