본문 바로가기

전체 글571

알고리즘 문제 해결 전략2 16장 비트마스크(4) 16.4문제:졸업 학기 졸업 필수 학점을 채우려면 전공 과목 N개 중 K개 이상을 수강해야 함. 각 과목의 정보와 앞으로 M학기 동안 개설될 과목의 목록이 주어질 때, 태우가 최소 몇 학기를 다녀야 졸업할 수 있느지 계산하는 프로그램을 작성하시오. 한 과목도 수강하지 않는 학기는 휴학한 것으로 하며, 다닌 학기 수에 포함되지 않음. 예제 입출력 설명 : 첫 학기에 0번 과목, 번 과목을 듣고, 두 번째 학기에 1번 과목을 들은 뒤, 네 번째 학기에 2번 과목을 들으면 됩니다. 세 번째 학기에는 2번 과목이 개설되지 않으므로 다니지 않아도 됨. 두 번째 테스트 케이스에서는 2번과 3번 과목이 서로 선수과목으로 지정되어 있기 때문에 두 과목은 들을 수 없습니다. 0번 과목을 듣기 위해 1번 과목을 미리 들어.. 2021. 6. 21.
알고리즘 문제 해결 전략2 16장 비트마스크(3) 16.3 비트마스크의 응용 예제 지수 시간 동적 계획법 배열 대신 정수로 집합을 표현하면 이것을 곧장 배열의 인덱스로 쓸 수 있따는 점을 이용함. 따라서 메모이제이션의 구현 또한 훨씬 간단해짐 에라토스테네스의 체 k번 원소가 참인지 알기 위해서는 k/8번째 원소의 k%8번째 비트가 켜져 있는지를 확인하면 됨. 실제로 비트마스크를 사용하는 부분은 isPrime(), setComposite() 임. inline bool isPrime(int k) { return sieve[k >> 3] & (1 > 3] &= ~(1 2021. 6. 21.
알고리즘 문제 해결 전략2 16장 비트마스크(2) 16.2 비트마스크를 이용한 집합의 구현 여섯 개의 원소를 갖는 집합 {1,4,5,6,7,9}을 표현하는 정수는 754임을 다음과 같이 알 수 있음. 피자집 예제 한 피자의 정보는 스무 종류의 원소만을 가지는 집합이 되고, 비트마스크를 이용해 표현할 수 있음. 공집합과 꽉 찬 집합 구하기 : 1 2021. 6. 21.
알고리즘 문제 해결 전략2 16장 비트마스크(1) 16.1 도입 현대의 모든 CPU는 이진수를 이용해 모든 자료를 표현함. 내부적으로 이진수를 사용하는 컴퓨터들은 이진법 관련 연산들을 아주 빨리 할 수 있음. 이와 같은 특성을 화용해 정수의 이진수 표현을 자료 구조로 쓰는 기법을 비트마스크라고 부름. 비트마스크의 장점은 - 더 빠른 수행 시간 - 더 간결한 코드 - 더 작은 메모리 사용량 - 연관 배열을 배열로 대체 컴퓨터는 모든 정수형 변수를 이진수로 표현함. 컴퓨터가 표현하는 모든 자료의 근간이 됨. 2^(N-1)에 해당하는 비트를 최상위 비트(most significant bit)라고 부르고, 2^0을 나타내는 비트를 최하위 비트(least significant bit)라고 부름. 비트별 NOT연산은 정수 하나를 입력받아 켜져 있는 비트는 끄고, .. 2021. 6. 21.
Bipartite Match 알고리즘 - 그래프의 최대 이분 매칭은 두 간선이 같은 정점을 공유하지 않는 간선의 최대 집합으 ㄹ말함. #include #define MAX 1000 int countA, countB; int matchA[MAX]; int matchB[MAX]; int adj[MAX][MAX]; int visited[MAX]; int dfs(int a) { int b; if (visited[a]) { return 0; } visited[a] = 1; for (b = 0; b < countB; ++b) { if (adj[a][b] && (matchB[b] == -1 || dfs(matchB[b]))) { matchA[a] = b; matchB[b] = a; return 1; } } return 0; } int bipartiteM.. 2021. 6. 21.
Maximum flow 알고리즘 Network flow란 각각의 간선에 정해진 용량보다 작은 유량이 주어진 방향그래프를 의미함. Maximum flow란 위 수원지에서 수요지까지 공급할 수 있는 최대 유량을 의미함 #include #define MAX_V 10 const int INF = 987654321; int V; typedef struct { int queueArray[MAX_V]; int front; int rear; }Queue; void push(Queue* q, int item) { if ((q->rear + 1) % MAX_V == q->front) { return; } q->queueArray[q->rear] = item; q->rear = (q->rear + 1) % MAX_V; } void pop(Queue* q).. 2021. 6. 21.
topological sorting 알고리즘 - 유향 그래프의 정점이 간선의 방향을 거스르지 않도록 나열한 것을 의미함 #include #include #define MAX_N 25 #define MAX_M 25 #define CONNECTED 1 #define NOT_CONNECTED 0 #define NOT_UPDATED_YET 0 #define NOT_VISITED -1 #define DUPLICATE -2 int map[MAX_N][MAX_N] = { 0, }; int count[MAX_N] = { 0, }; int test_case, n, m; typedef struct { int queue[MAX_N]; int cur_ptr; int last_ptr; } Queue; void queue_reset(Queue* queue) { queue-.. 2021. 6. 21.
minimum spanning tree 알고리즘 - 네트워크(가중치가 간선에 할당된 그래프)에 있는 모든 정점들을 가장 적은 비용으로 연결하는 트리 - 가공된 데이터를 사용하는 것을 배움 #include int V; int graph[100][100]; int minKey(int* key, unsigned char* mstSet) { int min = 2147483647; int min_index; for (int v = 0; v < V; v++) { if (mstSet[v] == 0 && key[v] < min) { min = key[v]; min_index = v; } } return min_index; } void printMST(int parent[]) { int weightSum = 0; for (int i = 1; i < V; i++) { .. 2021. 6. 21.
Plane Sweeping 알고리즘 - 여러 개의 직사각형이 주어졌을 때, 총 넓이를 구하는 알고리즘 - 모든 지도는 직사각형임 트리는 다음과 같은 방식으로 수정함 1. 직사각형의 세로선 데이터를 받아옴 2. 트리의 세로선에 해당하는 구간의 노드를 구함 3. 세로선의 종류에 따라 다음과 같이 작동 시킴 3-1. 세로선이 시작선일 경우, 해당하는 구간의 노드의 cnt값을 1증가시킴 3-2. 세로선이 끝선일 경우, 해당하는 구간의 노드의 cnt값을 1감소시킴 4. 해당하는 구간의 노드를 포함해 다시 루트노드까지 올라가면서 다음과 같이 작동시킴 4-1. 위치한 노드의 cnt값이 0인 경우, 하위 두 자식 노드의 sum값을 더해 위치한 노드의 sum에 저장시킴 4-2. 위치한 노드의 cnt값이 0보다 큰 경우, 해당하는 y축 구간 크기를 sum에.. 2021. 6. 21.

티스토리툴바