본문 바로가기
반응형

알고리즘58

비트마스크 (Bitmask) 비트마스크정수의 이진수 표현(Bit)을 자료 구조로 쓰는 기법현대의 모든 CPU는 이진수를 이용해도 모든 자fy 표현내부적으로 이진수를 사용하는 컴퓨터들은 이진법 관련 연산들을 아주 빨리 할 수 있다. • 더 빠른 수행 시간  비트마스크를 활용하는 것이 원소의 수가 많지 않겠지만, 큰 속도 향상이 없을 수는 있다.  하지만 연산을 여러 번 수행할 때는 굉장히 효율적이다. • 더 작은 공간 복잡도(메모리) • 비트 연산자를 활용한 가독성(간결한 코드)  다양한 집합 연산들을 반복문 없이 사용 ex) 8개의 비트를 사용할 때, 아래와 같이 표현.※ [BOJ] 11723 집합arr[8] = {1, 2, 4, 8, 16, 32, 64, 128} arr[i] = 1 이진수는 십진수 표현도 가능하며 0,1 / tr.. 2025. 1. 9.
[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.
반응형

티스토리툴바