부분 합이란 ? 배열의 각 위치에 대해서, 배열의 시작부터 현재 위치까지의 원소의 합을 구한 배열 #include #include using namespace std; vector partialSum(const vector& a) { vector ret(a.size()); ret[0] = a[0]; for (int i = 1; i < a.size(); i++) { ret[i] = ret[i - 1] + a[i]; } return ret; } int rangeSum(const vector& psum, int a, int b) { if (a == 0) return psum[b]; return psum[b] - psum[a - 1]; } 앞의 값에서 현재 값을 더하며 부분합 배열을 구하고, 이를 활용해서 구간..
비트마스크(bitmask) 란 ? 이진수 표현을 자료구조로 쓰는 기법이다. 비트 연산자 a & b : AND 연산 a | b : OR 연산 a ^ b : XOR 연산 ~a : NOT 연산 a > b 정수 a를 오른쪽으로 b비트 Shift 비교 연산자 → 비트 연산자의 우선순위 집합의 구현 int noPizza = 0; // 공집합 int fullPizza = (1
HTML 삽입 미리보기할 수 없는 소스 Kafka란 ? 간단하게 설명하자면, 이벤트 생산자(Producer)와 소비자(Consumer)가 큐잉 시스템을 통해서 데이터를 주고 받는 메시지 큐이다. 예를 들어, 마이크로서비스에서는, 각 서비스 간의 데이터 전달이 필요한 상황에서 느슨한 결합을 이루기 위해 큐잉 시스템을 사용하게 된다. 이렇게 여러 송신자가 메시지를 발행하고 여러 수신자가 구독하는 방식을 Pub/Sub구조라고 한다. Producer는 이벤트를 데이터를 구분하기 위한 저장소(Topic)에 저장하게 된다. 하나의 Topic은 여러 개의 Partition으로 나뉘어져 있다. 그리고 이 Topic에 저장된 이벤트들 저장, 전달하는 역할을 Broker가 하게 되는 것이다. Zookeeper란 ? Kaf..
본 게시글은 "프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 (구종만 저)"의 내용을 참고하여 기재하였습니다. 동적 계획법이란 ? 동적 계획법은 분할 정복과 유사하지만, 이미 계산한 값을 중복해서 계산하지 않기 위해 따로 저장하는 메모이제이션 기법을 사용했다는 것이 주요 특징이다. 이 기법은 참조적 투명성을 가지고 있는 함수에 대해서 적용된다. 같은 입력이 들어왔을 때 항상 같은 출력을 반환한다는 것이다. 유의사항 (1) 입력이 정해진 범위를 벗어난 경우 등을 기저 사례로 처리하여 cache에 저장하기 (2) cache의 초기값을 -1과 같은 수로 두고 -1이 아니라면 이미 계산된 값이라 생각한다. (3) 저장된 값을 반환하여 담는 ret변수는 &를 사용해서 “별칭”으로 선언한다. 이는 cache의..
본 게시글은 "프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 (구종만 저)"의 내용을 참고하여 기재하였습니다. 분할 정복 부분 문제의 답으로부터 전체 문제의 답을 도출한다. (1) 문제를 더 작은 문제로 분할하는 과정 (Divide) (2) 부분 문제를 원래 문제로 병합하는 과정(merge) (3) 더이상 답을 분할하지 않고 바로 푸는 문제 (base case) ex) 행렬의 거듭제곱 행렬의 곱셈은 주어진 행렬의 모든 원소를 가로 세로를 곱해줘야하므로 O(n^3) 의 시간 복잡도를 가진다. 이를 분할 정복을 이용해서 풀어보자. class SquareMatrix; SquareMatrix identity(int n); SquareMatrix pow(const SquareMatrix& A, int m) ..
본 게시글은 "프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 (구종만 저)"의 내용을 참고하여 기재하였습니다. [06] 무식하게 풀기 (Brute-Force) 재귀호출 재귀호출의 기저 사례 : 더 이상 쪼개지지 않는 마지막 조각에 도달했을 때 답을 반환하는 조건문을 작성하여야 함. 이 마지막 조각을 기저 사례라고 한다. 4중 for문을 통해 4가지 원소를 고르는 사례에서, 원소들의 총 개수 더 골라야 할 원소들의 개수 지금까지 고른 원소들의 번호 이 세가지를 함수의 인자로 넣어 재귀호출을 수행할 수 있다. 따라서 재귀호출로 완전탐색 문제를 풀 때는 아래의 프로세스를 사용한다. (1) 문제의 분할 (2) 기저 사례의 선택 (3) 구현 (4) 시간복잡도 분석 문제1 : 소풍 #include using ..
A와 B 사이에 겹치는 건물이 있는지 확인하는 과정에서 "두 점 사이의 직선" 공식을 이용해서 A와 B사이에 있는 모든 건물의 높이를 계산하여 푸는 과정을 이용했다. 여기서 (double) 범벅을 한 이 코드에서 j가 자꾸 잘 못 구해지는 버그가 있었다. A와 B건물 사이의 i번째 건물의 높이가 A와 B의 지붕을 연결한 선에 겹치지 않는지 검사하기 위해서 아래 공식을 사용한 것인데, j의 계산이 잘 되지 않았다 . #include #include using namespace std; // 고층 빌딩 /* 15 1 5 3 2 6 3 2 6 4 2 5 7 3 1 5 */ vector height ; // 빌딩 A(x1, y1)이 빌딩 B(x2, y2)를 볼 수 있는 지 확인하는 함수 bool isOverla..
총 일할 수 있는 N일 중에서 연속된 M일을 선택했을 때 그 부분합이 최대가 되는 경우를 계산하는 문제이다. 구간을 정해서 부분합을 구하는 슬라이딩 윈도우 혹은 투포인터 알고리즘을 적용할 수 있고, 여기서는 M이라는 일정한 크기의 윈도우가 정해져있으므로 슬라이딩 윈도우 알고리즘을 사용하여 풀이한다. https://ji-musclecode.tistory.com/37 슬라이딩 윈도우 알고리즘(Sliding Window) (feat. 투 포인트) 1. 슬라이딩 윈도우 알고리즘 (Sliding Window) ( 슬라이딩 윈도우 알고리즘 간단 예제 ) 1, 2, 3, 4, 5, 6, 7 로 이루어진 숫자 배열에서 A[i] + A[i+1] + A[i+2] 형식으로 연속적인 3개의 숫자의 합의 최댓값을 ji-musc..
