큐, 스택, 데크 큐는 선입선출 (FIFO)의 속성을 가지고 있다. 스택(Stack) 은 반대로 후입선출(LIFO)의 속성을 가지고 있고, 데크(dequeue) 는 양쪽 끝에서 넣고 뺄 수 있는 자료 구조를 말한다. 이 자료 구조는 동적 배열, 혹은 연결 리스트로 구현할 수 있다 (1) 연결리스트로 구현 시 양쪽 끝에서 상수 시간에 추가와 삭제가 가능하다. (2) 동적 배열을 이용한 구현 시, 배열의 맨 앞에서 원소 삭제 시 O(n)의 시간이 걸린다는 단점이 있다 → head와 tail을 이용해서 이 점을 보완할 수 있다. 즉 배열 전체가 아닌 head부터 tail까지만 자료구조로 사용하겠다는 건데, 버려지는 공간이 많다는 단점이 있다. 이는 환형 버퍼 (circular buffer) 의 개념으로 해결할..
선형 자료구조 배열은 메모리의 연속된 위치에 각 원소들이 저장되어있고, 연결 리스트는 여기저기 흩어져있는 원소들의 특정 위치에서 삽입과 삭제를 상수 시간에 수행하기 위해 이전 원소에서 다음 원소를 가리키는 “포인터”로 구현한다. struct ListNode { int element; ListNode *prev, *next; } C++에서는 연결리스트를 list라는 STL을 사용해서 구현한다. 조세푸스 문제 #include #include using namespace std; void josephus(int n, int k) { list survivors; for (int i = 1; i 2) { kill = survivors.erase(kill); if (kill == survivors.end()) ki..
부분 합이란 ? 배열의 각 위치에 대해서, 배열의 시작부터 현재 위치까지의 원소의 합을 구한 배열 #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
본 게시글은 "프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 (구종만 저)"의 내용을 참고하여 기재하였습니다. 동적 계획법이란 ? 동적 계획법은 분할 정복과 유사하지만, 이미 계산한 값을 중복해서 계산하지 않기 위해 따로 저장하는 메모이제이션 기법을 사용했다는 것이 주요 특징이다. 이 기법은 참조적 투명성을 가지고 있는 함수에 대해서 적용된다. 같은 입력이 들어왔을 때 항상 같은 출력을 반환한다는 것이다. 유의사항 (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 ..
