728x90 스터디/Algorithm10 [Algorithm] Prefix Sum 구간합 🍒구간합이란? -부분합 : 0~k 까지의 합 -구간합 : a~b 까지의 합 구간합은 말 그대로 시작점 a 부터 끝점 b까지 사이의 모든 값의 합을 의미한다. 🍒구간합 적용 구간합을 구하는 문제인데 구간사이의 수의 개수가 5천만개라면? 이러한 요청이 2천만개라면? 이중반복문을 사용해서 해결하면 분명 시간복잡도가 O(N^2)으로 오래걸리는 문제가 생긴다. int n; //요청 수 scanf("%d", &n); while(n--){ int a, b; scanf("%d %d", &a, &b); int sum = 0; for(int i=a; i 2021. 5. 11. [자료구조] Queue (큐) 📌큐 개념 먼저 들어온 자료가 먼자 나가는 FIFO (First in First Out), 선입선출 구조의 자료구조이다. 📌큐 주요 함수 front (): 맨 앞의 요소 출력 rear() : 맨 뒤의 요소 출력 enqueue() : 큐 뒤에 요소 추가하는 함수 dequeue() : 큐 맨 앞 요소를 빼는 함수 isFull() : 큐가 가득 찼는지 확인하는 함수 isEmpty() : 큐가 비었는지 확인하는 함수 📌큐 사용 사례 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용한다. 우선순위가 같은 작업 예약 (프린터의 인쇄 대기열) 은행 업무 콜센터 고객 대기시간 프로세스 관리 너비 우선 탐색(BFS, Breadth-First Search) 구현 캐시(Cache) 구현 📌구현 코드 #in.. 2021. 3. 8. [자료구조] Stack (스택) 📌스택이란 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO (Last In First Out) 구조의 자료 구조 📌스택 주요 함수 스택은 LIFO 구조로 가장 최근에 추가한 항목이 가장 먼저 제거된다. push() : 스택에 자료를 넣는 함수 pop() : 가장 최근에 추가한 자료를 빼는 함수 isFull() : 스택이 가득 찼는지 확인하는 함수 isEmpty() : 스택이 비었는지 확인하는 함수 📌스택 사용 사례 웹 브라우저 방문 기록 (뒤로가기) 역수 문자열 만들기 수식의 괄호 검사 (ex: 올바른 괄호 문자열 판단 등) 📌구현 코드 class Stack { private: int top, MaxSize; int *stack; public: Stack(int size); bool isFull(), .. 2021. 3. 8. [Algorithm] Binary Search (이분 탐색) 개념 📌이분 탐색(바이너리 서치)이란? 각 노드에 값이 있다. 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다. 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어져 있다. 좌우 하위 트리는 각각이 다시 이진 탐색 트리여야 한다. 📌이분 탐색의 검색 (Search) **조건 : 미리 정렬되어 있어야 한다. 이진탐색트리에서 키 x를 가진 노드를 검색하고자 할때, 트리에 해당 노드가 존재하면 해당 노드를 리턴하고, 존재하지 않으면 NULL을 리턴한다. 검색하고자 하는 값을 루트노드와 먼저 비교하고, 일치할 경우 루트노드를 리턴한다. 불일치하고 검색하고자 하는 값이 루트노드의 값보다 작을 경우 왼쪽 서브트리에서 재귀적으로 검색한다. 불일치하고 검색하고자 .. 2021. 3. 2. [Algorithm] Binary Search (이분 탐색) 코딩 테스트 공부를 하다가 Binary Search와 관련하여 문제풀이 방법이 다른 방법이 있어 정리를 한다. 📌기존에 자주 쓰던 Binary Search 코드 #include int BinarySearch(vector &A, int target) { int N = A.size(); if(N == 0) { return -1; } int l = 0; int r = N-1; while(l target){ r = m - 1; } else{ l = m + 1; } } return -1; } 이 코드에서 문제점이 있다. 바로 int m 을 구하는 과정에서 값이 커질 경우 overflow 문제가 발생한다. int 형의 경우 –2,147,483,648 ~ 2,147,483,647 사이의 값을 가지기 때문에 ( l +.. 2021. 2. 26. 자료형 크기 및 범위 정리 📌32bit (4Byte) 운영체제 기준 2021. 2. 26. [Algorithm] Priority Queue (우선순위 큐) 기본적으로 큰 값이 가장 맨 위에 오도록 queue를 쌓는다. priority_queue의 구조는 priority_queue 이다. 따라서 아래와 같이 코드를 짜면 된다. (C++기준) #include priority_queue pq; priority_queue pq; less : 가장 큰 값이 맨 위에 온다. greater : 가장 작은 값이 맨 위에 온다. 만약 직접 구현한 구조체에 해당하는 비교함수를 쓰고싶다면 아래와 같이 사용하면 된다. #include struct node{ int x, y, cost; node(int x, int y, int cost):x(x), y(y), cost(cost){} }; struct cmp{ bool operator()(node a, node b){ return .. 2021. 2. 17. [Algorithm] Kruskal Algorithm (크루스칼 알고리즘) 💡크루스칼 알고리즘이란? Greedy 알고리즘으로 MST(Minimum Spannig Tree, 최소 신장 트리) 문제 해결할 때 사용하는 알고리즘. 변의 개수를 E, 꼭짓점의 개수를V라고 하면 이 알고리즘은(Elog V)의 시간복잡도를 가진다. 즉, 모든 노드를 최소한의 비용으로 연결만 시키면 되기 때문에 간선의 비용을 오름차순으로 정렬 후 비용이 작은 간선부터 차례로 노드를 연결한다. 📌최소 신장 트리 구성 과정 1. 간선의 비용을 기준으로 정렬 2. 정렬된 순서에 맞게 최소 비용 순으로 그래프 연결 3. 연결 전 사이클이 발생하는지 확인 4. 사이클이 발생하는 경우 그래프에 포함하지 않음. 5. 위 과정을 반복 스패닝 트리 : 1) 모든 노드(정점)을 포함하고, 2) 노드간 연결되어 있으며 사이클을.. 2021. 2. 17. [Algorithm] Segment Tree (세그먼트 트리) 💡Segmet Tree (세그먼트 트리) 란? 세그먼트 트리는 Binary Tree로 리프노드가 배열의 원소이고, 부모 노드는 각 배열 원소의 값의 합입니다. 따라서 배열의 원소값이 계속 변하고, 배열의 부분 합을 구할 때 부분 합을 트리에 계속 저장하여 O(logN)의 속도로 빠르게 부분 합을 구할 수 있습니다. 세그먼트 트리의 구현을 배열을 통해 구현 할 수 있다. 인덱스 i를 기준으로 했을 경우, 각 노드의 위치는 아래와 같습니다. - 부모노드 : i - 왼쪽 자식 노드 : 2*i - 오른쪽 자식 노드 : 2*i + 1 📌세그먼트 트리 구현 함수 void init(int tree[], int arr[], int left, int right, int idx) { if(left == right) { t.. 2021. 2. 11. [Algorithm] Floyd-Warshall Algorithm 알고리즘 문제를 풀다가 최소 비용 문제와 관련하여 플로이드 워셜 알고리즘을 알게되어 정리해 본다. 💡알고리즘 설명 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘이다. 그래프 - 나무위키 이 문서는 대한민국에서 불법인 내용을 다룹니다. 본 문서는 대한민국에서 범죄를 구성하는 행위에 관한 헌법·법률·대통령령·조례를 다루고 있습니다. 일부 예외를 제외하고, 대한민국이 아 namu.wiki 플로이드-워셜 알고리즘은 임의의 노드 s에서 e까지 가는 데 걸리는 최단거리를 구하기 위해, s와 e 사이의 노드인 m에 대해 s에서 m까지 가는 데 걸리는 최단거리와 m에서 e까지 가는 데 걸리는 최단거리를 이용한다. 조금 더 구체.. 2021. 2. 7. 이전 1 다음 728x90
