본문 바로가기

프로그래밍/개발 이야기42

[백준] 11047번 문제풀이 문제 : www.acmicpc.net/problem/11047 기존에는 - 하는 형식으로 알고리즘을 구성했었다. 코드는 이와 같다. #define _CRT_SECURE_NO_WARNINGS #include int main(void) { int n, k; int arr[10]; scanf("%d %d", &n, &k); for (int i = 0; i = 0; i--) { int temp = k - arr[i]; if (temp >= 0) { k -= arr[i]; count++; i++; } } printf("%d", count); return 0; } 근데 왠걸 K 의 입.. 2021. 4. 3.
[자료구조] Priority Queue 우선순위 큐 흔히 볼 수 있는 트리이다. 3 4 6 5 2 1 를 입력하였을 때 1 2 3 4 5 6 이 출력되도록 만들어 보겠다. 우선 Heap으로 만들어본 우선순위 Queue의 시간 복잡도는 O(logN) 정도 될 것이다. 아주 빠르다. #define _CRT_SECURE_NO_WARNINGS #include #define MAX_SIZE 10 #define parentNode(X) (X-1)/2 #define childNodeLeft(X) (X*2)+1 #define childNodeRight(X) (X*2)+2 int heap[MAX_SIZE]; int heapSize = 0; void heapInit(void); int heapIsFull(void); int heapIsEmpty(void); int heap.. 2021. 4. 3.
[자료구조] Queue의 En,Dequeue를 이용해서 출력을 반전시켜보자 이러한 출력구조를 가진게 Queue이다. 1, 2, 3, 4, 5를 Enqueue 하면 1, 2, 3, 4, 5가 그대로 Dequeue 된다. 구현에는 Stack과 마찬가지로 5개 함수로 이루어져 있다. init(), isEmpty(), isFull(), enQueue(), deQueue() Stack과 거의 유사하지만, 몇가지가 다르다. 코드를 보며 생각해보자. Stack은 hyun222.tistory.com/114 여길 참고하면 된다. 함수부분 코드 void init(void) { rear = 0; front = 0; } int isEmpty(void) { return (rear == front); } int isFull(void) { return ((front + 1) % MAX == rear); .. 2021. 4. 3.
[자료구조] Stack의 push, pop을 이용한 출력 이와 같은 출력 구조를 가지는게 Stack이다. FILO 이다. 구현은 5개의 함수면 충분하다. init(), isEmpty(), isFull(), push(), pop() void init(void) { top = 0; } int isEmpty(void) { return (top == 0); } int isFull(void) { return (top == MAX); } int push(int a) { if (isFull()) { printf("Stack이 꽉 찼습니다.\n"); return 0; } STACK[top++] = a; return 1; } int pop(int* a) { if (isEmpty()) { printf("Stack이 비었습니다.\n"); return 0; } *a = STACK[.. 2021. 4. 3.
[백준] 2839번 문제풀이 문제 : www.acmicpc.net/problem/2839 #include int main(void) { int n; scanf("%d", &n); int count = 0; while (1) { if (n == 0) { break; } if (n % 5 == 0) { n -= 5; count++; continue; } if (n % 8 == 0) { n -= 8; count += 2; continue; } if (n % 3 == 0) { n -= 3; count++; continue; } if (n >= 5) { n -= 5; count++; continue; } if (n >= 8) { n -= 8; count += 2; continue; } if (n >= 3) { n -= 3; count++; .. 2021. 4. 1.
[알고리즘] 최대 Subarray 찾기 아래와 같은 배열(집합)이 있다. 1 -3 2 4 -1 5 -3 이 배열의 부분집합중에, 합이 가장 큰 것은 무엇인가? 답은 2, 4, -1, 5 를 더한 10이다. 이것을 어떻게 빨리 구할 수 있을까? --------- 내가 생각한 방법은 이렇다. - 양수로 시작, 양수로 끝. 목록을 만들어보자면 이와 같다. 1, -3, 2, 4 2, 4, -1, 5 4, -1, 5 5 하지만 모두가 음수이거나, 양수이면? 음수일 때 : 최솟값 1개가 정답. 양수일 때 : 모든값을 더한것이 정답. 알고리즘 시간복잡도는 O(N^2)일 것이다. --------- 제시하는 알고리즘은 다음과 같다. Count 변수가 있다. Count 변수는 배열을 더해간다. 만약 Count 변수가 음수가 된다면, 0으로 초기화 한다. 이렇게.. 2021. 3. 26.

티스토리툴바