반응형 알고리즘58 [ps] 알고리즘 문제 풀 때, 메모리 제한? (feat. 구조체 메모리 계산) 코딩 테스트와 같이 알고리즘 문제 풀 때, 메모리 제한이 엄격한 경우가 있다. 이때는 문제 설계 단계에서 메모리가 얼마나 필요할지 계산해서 구현해야 한다. Q) int는 4Byte 입니다. 그렇다면 int[] 배열 크기를 100만 (= 106) 으로 잡으면? A) int arr[1'000'000]; → 4 × 1,000,000 = 4,000,000 = 4MB 이다. 만약에 int 배열 크기가 1억(10^8)으로 잡는다면 → 400 MB 가 된다. 구조체 메모리 계산 하나의 자료형으로 이루어진 구조체 크기도 어렵지 않게 계산할 수 있다. struct Node { int x, y, state; } que[3000 * 3000]; → (int) 4 byte × 3개 × 3000 × 3000 = 10^8 MB .. 2021. 8. 2. 재귀(Recusion) 함수? 재귀 호출(Recusive Call)? 정의 자기 자신을 재참조하는 기법을 의미한다. 단순 반복문을 재귀 형태로 구현할 수 있다. 반대로 재귀 형태를 단순 반복문 형태로도 바꿀 수 있다. (반복문 ↔ 재귀호출) 예시 팩토리얼로 구현해야 한다고 가정해보시자. ex) factorial(3) = 3 × 2 × 1 = 6 을 구하는 과정 반복문 Ver. #include int factorial(int x) { int ret = 1; for (int i = 1; i 2021. 7. 24. 완전탐색 기법이란? 가능한 모든 값을 대입해보는 무식한(?) 방법에 해당된다. 문제 내용 속에서 특정 규칙을 찾아서 모든 Case를 대입해보지 않고도 풀리는 경우도 있지만 충분한 제한 공간과 시간이 주어진다면 특정 수학 공식이나 최적화 없이 문제 내용을 거의 그대로(?) 프로그래밍 언어로 반영해주면 된다. 0 ~ 9 까지 4자리로 구성된 Password가 있다고 가정해보자. 그렇다면 0000 ~ 9999 까지의 Case가 존재하는데 "홀수이다", "짝수이다", "Password를 이루는 숫자는 모두 다르다" 라는 조건이 없다면 간단하면서 가장 확실한 방법은 하나씩 다 입력해보는 것이다. 경우의 수 = 10 × 10 × 10 × 10 = 10,000 으로 1초안에 해결할 수 있다. ▶ 알고리즘 문제에서 시간 복잡도는 어떻게 .. 2021. 7. 24. [Hash] 문자열 Hash 고찰 문자열 Hash 고찰 문자열 Hash (djb2)에서 문자열 → 정수로 변환해서 Hash 구현이 가능해진 것을 확인할 수 있었다. unsigned long djb2(const char* str) { unsigned long hash = 5381; int c; while (c = *str++) { hash = (((hash 2021. 6. 12. 문자열 Hash (djb2) 문자열 Hash (djb2) 해당 게시글 전에 아래 내용을 먼저 읽어보시면 좋습니다. - [해시] Hash란? - [해시] Hash Chaining 기법 구현 Hash 성능에 있어서 Hash Index 충돌을 낮추는 것이 중요하다. Hash 충돌을 처리하는 방법은 크게 2가지로 구분할 수 있다. Chaining 기법 과 Open Address 기법 이다. 위 2 가지는 충돌이 발생하는 경우 처리이지만 Key에 해당하는 Hash Index를 구하는 것도 여러 알고리즘이 존재한다. // djb2 unsigned long djb2(const char* str) { unsigned long hash = 5381; int c; while (c = *str++) { hash = (((hash 2021. 6. 12. [예제] 힙 정렬 구현 Heap Sort ▶ Heap 구조가 궁금한 경우 [그래프] 힙(Heap) 힙(Heap) 자료구조란? Heap - 최대값 또는 최소값을 빠르게 구하기 위한 자료구조 - 완전 이진 트리를 기본으로 한 자료구조 - 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 한다. - 트리가 한쪽으로 기울어진 zoosso.tistory.com ▶ Heap Sort 원리 및 시뮬레이션 힙 정렬 (Heap Sort) 힙 정렬 (Heap Sort) 힙 정렬 (Heap Sort) - O(N logN) - [그래프] 힙(Heap)를 이용한 정렬 입니다. 힙(Heap) 자료구조란? Heap - 최대값 또는 최소값을 빠르게 구하기 위한 자료구조 - 완전 이진 트리를 기본으로 한 자료구조 - zoosso.tistory.com .. 2021. 6. 4. [예제] 퀵 정렬 구현 Problem Solving을 하다보면 주어진 원소를 정렬 시킬 필요가 있습니다. 물론 STL을 이용해서 구현할 수 있지만 해당 노트에서는 구조체 형태로 정렬하는 내용을 다룹니다. ▶ 퀵(Quick) 정렬 상황 (조건) 특정 사람이 {나이age, 경험exp}가 있을 때, 나이가 큰 순(내림차순) / (나이가 동일한 경우) 경험이 큰 순(내림차순) 즉, 여러 기준을 적용해서 정렬하겠습니다. Input 3 20 20 20 30 30 10 Output age = 30, exp = 10 age = 20, exp = 30 age = 20, exp = 20 구현 코드 #include #define MAX_NUM 100 int N; struct Node { int age, exp; void print() { prin.. 2021. 6. 4. 퀵(Quick) 정렬 퀵(Quick) 정렬 - O(N logN) - pivot을 기준으로 하여 큰 값과 작은 값을 찾아 바꿔가며 정렬하는 것입니다. ▶ [예제] 퀵 정렬 구현 [예제] 퀵 정렬 구현 Problem Solving을 하다보면 주어진 원소를 정렬 시킬 필요가 있습니다. 물론 STL을 이용해서 구현할 수 있지만 해당 노트에서는 구조체 형태로 정렬하는 내용을 다룹니다. 상황 (조건) 특정 사람이 { zoosso.tistory.com 시뮬레이션 ① 기준 Pivot을 첫번째 원소로 설정합니다. ② 좌측에서 pivot 값보다 큰 값을 찾습니다. 우측에서 pivot 값보다 작은 값을 찾습니다. arr[left] = 8 / arr[right] = 2 ③ 찾은 두 값의 위치를 바꿔 줍니다. ④ 이러한 작업을 좌측에서 찾은 값이 .. 2021. 6. 4. 삽입 정렬(Insertion Sort) 삽입 정렬(Insertion Sort) - O(N2) 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교 하여, 자신의 위치를 찾아 삽입하여 정렬 정위치에 삽입해야 하므로 기존에 있었던 원소를 뒤로 밀어주어야 합니다. ※ 대부분의 원소가 이미 정렬되어 있는 경우에는 효율적이지만, 그렇지 않은 경우 빈번한 이동 발생 [C 언어] - 오름차순 기준 # include int swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } void insertionSort(int arr[], int n) { for (int i = 0; i 0 && arr[pivot - 1] > arr.. 2021. 6. 2. [ps] 여러 정수 기준에 따른 우선순위 비교 및 정렬 해당 게시글에서는 여러 정수형 데이터로 우선순위가 나눠질 때, 효율적으로 처리할 수 있는 방법을 제시합니다. 몇몇 문제에서는 2가지 이상 기준에 의해 정렬되거나 우선순위가 정해집니다. ▶ [BOJ] 21608 상어 초등학교 (삼성 코딩 테스트 문제) ▶ [BOJ] 21609 상어 중학교 (삼성 코딩 테스트 문제) 만약, 사전순 배열과 같이 문자열 비교가 필요한 경우에는 아래 게시글 참고 ▶ [ps] 문자열 사전 오름차순 비교 및 정렬 [ps] 문자열 사전 오름차순 비교 및 정렬 문제를 풀다보면 ID가 작은 기준으로 하되, 동일한 ID인 경우에는 알파벳 오름차순으로 우선순위를 가지도록 하는 조건이 있습니다. 여러 기준에 의해 우선순위가 결정되는 경우 입니다. 숫자를 zoosso.tistory.com 구조체.. 2021. 5. 30. 이전 1 2 3 4 ··· 6 다음 반응형
