Meluu_의 코딩 공부 일지

배열의 연속된 구간의 합을 O(Log N)시간만에 할 수 있는 자료구조합 뿐만 아니라 구간 최대 최소, 곱 등도 구할 수 있다. 세그먼트 트리는 보통 3가지로 구성된다init : 세그먼트 트리 초기화query : 원하는 구간의 값을 구함update : 배열에서 요소 a를 변경했을 때 값을 갱신함 트리 크기세그먼트 트리도 결국 이진 트리 기반이기에 가질 수 있는 노드는2^h 개가 된다. h = ceil(log2(n)) , n = 배열의 요소 개수 treeSize = 2^h 높이를 올리는 이유n = 9 일때 log2(9) = 3.xx 로 나온다.그렇다고 높이를 3으로 해버리면2^3 이 되어 트리 크기가 8이 되고 9를 넣을 공간이 없어진다. 그래서 높이를 올림(ceil)해서 4로 잡아야 안전하다. 코드..

일반적으로 배낭문제는정해진 무게 안에 가장 가치 있는 물건을 고르는 것 이다. 이번 포스팅에서는 배낭 문제의 3가지 유형 (0/1, 무한, 개수제한)에 대해 이해해보려한다.사실 배낭문제도 2차원 배열을 활용한 DP 문제다 따라서 제일 먼저 문제를 보고 할 일은 최적 부분 구조 + 부분 반복 문제 확인하는 것이다. 이전 상태 유지 + 개수 제한 일 때는 중복 사용 방지를 위해 2차원 배열을 사용이 유리할 수 있다. 개수제한일 때를 생각해보면 1차원 배열 사용시 중복 사용될 가능성이 있다. 제한이 2개일때 배낭 무게 최대 무게 6아이템 1개에 대하여 무게 2, 가치 10 이라하면dp = {0, 0, 10, 0, 20, 0, 30} 이런식으로 3번 같은 아이템을 사용해 버린다. 때문에 2차원 배열로 같은..

✔️ 리스트(List)데이터를 순서대로 저장한 자료구조 리스트는 배열과 연결리스트를 이용해 구현할 수 있다.  리스트 추상데이터타입insert(list, pos, item) // pos 위치에 요소를 추가insert_last(list, item) // 맨 끝에 요소를 추가insert_first(list, item) // 맨 처음에 요소를 추가delete(list, pos) // pos 위치의 요소를 제거clear(list) // 리스트의 모든 요소를 제거get(list, pos) // pos 위치의 요소를 반환size() // 리스트의 길이를 반환is_empty(list) // 리스트가 비었는지 검사is_full(list) // 리스트가 꽉 찼는지 검사print_list(list) // 리스트의 모든 요..

✔️ 큐(queue)먼저 들어온 데이터가 먼저 나가는 자료구조선입 후출 : FIFO First-In Frist-Out  예시 : 식당에서 먼저 주문한 사람이 먼저 음식을 받는다. 큐에는 선형 큐와 원형 큐가 있다. 선형 큐는 배열처럼 일자 데이터 구조이고 원형 큐는 처음과 끝이 연결되어있는 데이터 구조이다.  ❗ 선형 큐의 문제점    dequeue()로 요소를 꺼내면 맨 앞자리가 비어있기 때문에 이를 채우기위해 뒤의 모든 요소들을 한 칸씩 앞으로 땡겨야    하기에 효율적이지 않다.   프로그램 상에서 어떻게 원형 큐를 구현할까?우리는 아주 좋은 %(나머지 연산)을 알고 있다. (마지막인덱스 + 1) 자리로 인덱싱 접근이 오면 % (큐의 크기) 연산을 해주어서 다시 맨 앞자리에 접근하게 한다. 이를 통..

같은 자료형의 데이터를 쌓아 놓는 자료구조후입 선출 : LIFO Last-In Frist-Out  함수 호출 역시 메모리 스택에 쌓이는 구조이다. func1() // 호출되어 쌓임main() // func1() 호출 스택 추상 데이터 타입create(size) // 최대 크기가 size인 공백 스택을 생성is_full(s) // if (스택의 원소수 == size) return TRUE; 아니라면 return False;is_empty(s) // if(스택의 원소수 == 0) return TRUE; 아니라면 return False;push(s, item) // 스택이 풀 상태이면 에러를 반환, 아니라면 스택 맨 위에 item 추가pop(s) // 스택이 비어있다면 에러 반환, 아니라면 맨 위 원소를 꺼낸..

✔️ 배열같은 자료형의 변수들이 연속된 메모리 공간을 차지하는 자료구조 인덱스와 인덱스에 대응하는 데이터들로 이루어진 자료구조이다.  int arr[5]; // 배열 선언arr[0] = 10; // 0번째 인덱스에 접근하여 값을 바꿈, set 연산int value = arr[0] // 0번째 인덱스에 접근하여 값을 가져옴, get 연산int arr[] = {1, 2, 3, 4}; // 배열 바로 초기화  1차원 배열 :  base(주소값) + n * sizeof(자료형) 2차원 배열 :  base(주소값) + (i * 열의 개수 + j )* sizeof(자료형)       // i : 행,  j : 열 이러한 형식으로 실질적인 배열 인덱스에 접근한다. 응용 : 행렬 (matrix)2차원 배열을 이용하여 ..

순환이란 알고리즘이나 함수가 수행 도중에 자기 자신을 다시 호출하여 문제를 해결하는 기법으로 팩토리얼이 가장 대표적인 예시다.int factorial(int n) { if (n    순환에서 가장 중요한 점은순환을 멈추는 부분과순환을 호출하는 부분이 있어야 한다는 것이다.  순환 호출을 멈추는 부분이 없다면 시스템 오류가 발생할 때까지 무한정 호출하게 된다 .(StackOverflow) 그렇다면 반복 알고리즘 보다 순환 알고리즘이 더 좋은가? 상황에 따라 다른데 문제의 값을 줄일 수 있다면 순환 알고리즘아니라면 반복 알고리즘이 좋을 수 있다.피보나치 수열을 순환으로 실행해보면 연산 중복 현상으로 인해 효율이 떨어지기에 반복 알고리즘이 더 나은 선택이다.    이외에도 두 수의 최대 공양수를 구하는 유클리..

자료구조란?데이터에 대한 효울적인 접근 및 수정을 가능하게 하는 자료의 조직, 관리, 저장 체계 데이터의 모임,데이터 간의 관계, 데이터에 적용할 수 있는 함수나 명령을 포함한 (프로그램에서) 자료들을 정리하여 보관하는 구조 알고리즘의 조건- 입력 : 0개 이상의 입력이 존재- 출력 : 1개 이상의 출력이 존재- 명백성 : 각 명령어의 의미는 모호하지 않고 명확해야함- 유한성 : 한정된 수의 단계 후에는 반드시 종료되어야 함- 유효성 : 각 명령어들은 실행 가능한 연산이여야 함  자료형 기초 자료형 : char, int float, double파생 자료형 : 배열 포인터사용자 정의 자료형 : 구조체, 공용체, 열거형 데이터 집합과 연산의 집합int 자료형 데이터{-INT_MIN, ... , - 2, -1..