사용자 도구

사이트 도구


알고리즘:기타

기타

  • 1일차 최적화 & 큐
    • 배열 구간의 합 구하기
    • 연속부분최대곱
    • 용액
    • 회전 초밥(고)
    • 프린터 큐
    • 요세푸스 문제 (정올 문제은행 : 3101)
    • 색종이(고)
  • 2일차 스택&이진탐색
    • 불쾌한 날
    • 히스토그램에서 가장 큰 직사각형
    • 도약
    • 나무 자르기
    • 마법의 성 (정올 실전문제 : 3108)
  • 3일차 링크드리스트
    • 스택 링크드 리스트로 구현하기
    • 큐 링크드 리스트로 구현하기
    • 키로거(Keylogger) (정올 문제은행 : 3123)
    • 주문형 농산물재배 (정올 실전문제 : 3110)
    • 카드섹션 (정올 실전문제 : 3148)
  • 4일차 hash
    • 암소 라인업
    • UNIQUENESS
    • PC방 관리프로그램 (정올 실전문제 : 3119)
    • 설문조사 (정올 실전문제 : 3144)
  • 5일차 segment tree
    • 구간의 최대값 구하기
    • 구간의 합 구하기
    • 마라톤 대회(Gold)
    • CD홀더 (정올 실전문제 : 3107)
//3148 : 카드섹션 (좌석별 관리)
#pragma warning (disable : 4996)
#include <stdio.h>
#define MAXN ((int)1e3)
#define MAXM ((int)1e4 + 1)
int N, M;//좌석 크기, 작업 수
//각 섹션 정보(아이디가 인덱스)
struct SECT {
	int r, c, h, w;
	char color[40 * 40 + 1];
};
struct SECT sect[MAXM];
//좌석별 관리(색, 아이디)
struct NODE {
	char col; int id;
	struct NODE *next;
};
struct NODE A[MAXN][MAXN];//좌석(dummy node)
struct NODE tnode[40 * 40 * MAXM];
int tnodeidx;
struct NODE *myalloc(int id, char col, struct NODE *next) {
	struct NODE *ret = &tnode[tnodeidx++];
	ret->id = id; ret->col = col; ret->next = next;
	return ret;
}
//관리 함수
void Init() {
	tnodeidx = 0;
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			A[r][c].next = NULL;
		}
	}
}
void strcopy(char *dst, char *src) {
	while (*dst++ = *src++);
}
void add(int id) {
	//좌석에 저장
	int r = sect[id].r, c = sect[id].c, h = sect[id].h, w = sect[id].w;
	char *color = sect[id].color;
	int k = 0;
	for (int i = r; i < r + h; i++) {//세로
		for (int j = c; j < c + w; j++) {//가로
			A[i][j].next = myalloc(id, color[k++], A[i][j].next);
		}
	}
}
void insertsection(int id, int r, int c, int h, int w, char *color) {
	//섹션정보 저장
	sect[id].r = r; sect[id].c = c; sect[id].h = h; sect[id].w = w;
	strcopy(sect[id].color, color);
	//좌석에 저장
	add(id);
}
void searchdel(struct NODE *p, int id) {
	while(p->next) {
		if (p->next->id == id) {//지울 노드 찾았음
			p->next = p->next->next;
			break;
		}
		p = p->next;
	}
}
void del(int id) {
	//좌석에서 정보 제거
	int r = sect[id].r, c = sect[id].c, h = sect[id].h, w = sect[id].w;
	for (int i = r; i < r + h; i++) {//세로
		for (int j = c; j < c + w; j++) {//가로
			searchdel(&A[i][j], id);
		}
	}
}
void prt(int sr, int sc, int er, int ec) {
	for (int i = sr; i < er; i++) {
		for (int j = sc; j < ec; j++) {
			if (A[i][j].next == NULL) printf("0");
			else printf("%c", A[i][j].next->col);
		}
	}
	printf("\n");
}
void solve() {
	int cmd, id, r, c, h, w; char color[40 * 40 + 1];
	scanf("%d %d", &N, &M);
	Init();//초기화
	for (int i = 1; i <= M; i++) {
		scanf("%d", &cmd);
		switch (cmd) {
		case 1://섹션 추가
			scanf("%d %d %d %d %d %s", &id, &r, &c, &h, &w, color);
			insertsection(id, r, c, h, w, color);
			break;
		case 2://섹션 제거
			scanf("%d", &id); del(id);
			break;
		case 3://섹션 순서 변경
			scanf("%d", &id); del(id); add(id);
			break;
		case 4://섹션 이동 및 순서 변경
			scanf("%d %d %d", &id, &r, &c); del(id);//기존 정보로 지움
			sect[id].r = r; sect[id].c = c; add(id);//새 정보로 추가
			break;
		default://출력
			scanf("%d %d", &r, &c); prt(r, c, r + 4, c + 4);
		}
	}
}
int main() {
	int T;
	scanf("%d", &T);
	for (int i = 1; i <= T; i++) {
		solve();
	}
	return 0;
}
//3148 : 카드섹션 (섹션별 관리)
#pragma warning (disable : 4996)
#include <stdio.h>
#define MAXN ((int)1e3)
#define MAXM ((int)1e4 + 1)
int N, M;//좌석 크기, 작업 수
//각 섹션 정보(아이디가 인덱스)
struct NODE {
	int id;
	struct NODE *prev, *next;
};
struct NODE *head, *tail;
struct NODE tnode[MAXM + 10];
int tnodeidx;
struct NODE *myalloc(int id, struct NODE * p) {
	struct NODE *ret = &tnode[tnodeidx++];
	ret->id = id;
	if (p == NULL) {
		ret->next = ret->prev = NULL;
	}
	else {
		ret->next = p; ret->prev = p->prev; p->prev->next = ret;
	}
	return ret;
}
struct SECT {
	int r, c, h, w;
	char color[40 * 40 + 1];
	struct NODE * ptr;//배정된 주소(삭제 및 이동)
};
struct SECT sect[MAXM];
void Init() {
	tnodeidx = 0;
	head = myalloc(0, NULL); tail = myalloc(0, NULL);
	head->next = tail; tail->prev = head;
}
void strcopy(char *dst, char *src) {
	while (*dst++ = *src++);
}
void insertsection(int id, int r, int c, int h, int w, char *color) {//섹션 추가
	//섹션정보 저장
	sect[id].r = r; sect[id].c = c; sect[id].h = h; sect[id].w = w;
	strcopy(sect[id].color, color);
	//tail 앞 노드로 추가
	sect[id].ptr = tail->prev = myalloc(id, tail);
}
void deletesection(int id) {//섹션 제거
	sect[id].ptr->prev->next = sect[id].ptr->next;
	sect[id].ptr->next->prev = sect[id].ptr->prev;
	sect[id].ptr = NULL;
}
void movesection(int id) {//마지막 순서로 이동
	//이전 자리에서 제거
	sect[id].ptr->prev->next = sect[id].ptr->next;
	sect[id].ptr->next->prev = sect[id].ptr->prev;
	//tail 앞에 추가
	sect[id].ptr->prev = tail->prev; sect[id].ptr->next = tail;
	tail->prev->next = sect[id].ptr; tail->prev = sect[id].ptr;
}
char str[MAXN][MAXN];
void prt(int sr, int sc, int er, int ec) {
	//1.출력할 좌석만 초기화
	for (int r = sr; r < er; r++) {
		for (int c = sc; c < ec; c++) {
			str[r][c] = '0';
		}
	}
	//2.좌석별 색 정보 찾기(head->next ~ tail전까지)
	for (struct NODE *p = head->next; p != tail; p = p->next) {
		int id = p->id, k = 0;
		int r = sect[id].r, c = sect[id].c, h = sect[id].h, w = sect[id].w;
		char *color = sect[id].color;
		if ((r >= er) || (r + h <= sr)) continue;//현재 섹션 정보는 출력할 영역과 겹치는 부분이 없음
		if ((c >= ec) || (c + w <= sc)) continue;//현재 섹션 정보는 출력할 영역과 겹치는 부분이 없음
		for (int i = r; i < r + h; i++) {
			for (int j = c; j < c + w; j++) {
				str[i][j] = color[k++];
			}
		}
	}
	//3.출력
	for (int r = sr; r < er; r++) {
		for (int c = sc; c < ec; c++) {
			printf("%c", str[r][c]);
		}
	}
	printf("\n");
}
void solve() {
	int cmd, id, r, c, h, w; char color[40 * 40 + 1];
	scanf("%d %d", &N, &M);
	Init();//초기화
	for (int i = 1; i <= M; i++) {
		scanf("%d", &cmd);
		switch (cmd) {
		case 1://섹션 추가
			scanf("%d %d %d %d %d %s", &id, &r, &c, &h, &w, color);
			insertsection(id, r, c, h, w, color);
			break;
		case 2://섹션 제거
			scanf("%d", &id); deletesection(id);
			break;
		case 3://섹션 순서 변경
			scanf("%d", &id); movesection(id);
			break;
		case 4://섹션 이동 및 순서 변경
			scanf("%d %d %d", &id, &r, &c);
			sect[id].r = r; sect[id].c = c; movesection(id);
			break;
		default://출력
			scanf("%d %d", &r, &c); prt(r, c, r + 4, c + 4);
		}
	}
}
int main() {
	int T;
	scanf("%d", &T);
	for (int i = 1; i <= T; i++) {
		solve();
	}
	return 0;
}
//3119 : PC방 관리프로그램 
#ifndef NULL
#define NULL 0
#endif // NULL
#define INF ((int)2e9)
#define MAXN ((int)5e4 + 10)
#define MAXLEN (11 + 1)
int strcompare(char *a, char *b) {//같은 문자열이면 0, 앞에가 크면 양수, 뒤에가 크면 음수
	int i;
	for (i = 0; a[i]; i++) {
		if (a[i] != b[i]) break;
	}
	return a[i] - b[i];
}
void strcopy(char *dst, char *src) {
	while (*dst++ = *src++);
}
int hashfunc(char *a) {
	int hcode = 5381;
	for (int i = 0; a[i]; i++) {
		hcode = (hcode * 33 + a[i]) % MAXN;
	}
	return hcode;
}
static int remainuser;//접속한 유저
static int basetime, curtime;
int Nid;//새로운 아이디 배정용
struct HTBL {
	char org[MAXLEN]; int uid;
	struct HTBL * next;
};
struct HTBL htbl[MAXN];
struct HTBL tnode[MAXN];
int tnodeidx;
struct HTBL * myalloc(char *org, int uid, struct HTBL *next) {
	struct HTBL *ret = &tnode[tnodeidx++];
	strcopy(ret->org, org); ret->uid = uid; ret->next = next;
	return ret;
}
int newid(char *org) {//오름차순으로 추가하기(새로운 아이디 추가)
	int hkey = hashfunc(org);
	struct HTBL * p = &htbl[hkey];
	while (p->next != NULL) {//p->next가 NULL이면 p->next에 추가(새로운 아이디임)
		int cmpret = strcompare(p->next->org, org);
		if (cmpret == 0) return p->next->uid;//기존에 배정한 값 리턴
		if (cmpret > 0) break;//p->next에 추가(새로운 아이디임)
		p = p->next;
	}
	p->next = myalloc(org, ++Nid, p->next);
	return Nid;
}
int SearchId(char *org) {//찾는 함수, 없어도 추가하지 않음
	int hkey = hashfunc(org);
	struct HTBL * p = &htbl[hkey];
	while (p->next != NULL) {
		int cmpret = strcompare(p->next->org, org);
		if (cmpret == 0) return p->next->uid;//기존에 배정한 값 리턴
		if (cmpret > 0) break;
		p = p->next;
	}
	return 0;//없는 아이디임
}
struct CLIENT {
	int login, stime; char pw[20];
};
struct CLIENT client[MAXN];
struct QUE {
	int id, stime;
};
struct QUE que[MAXN];
int wp, rp;
void push(int id, int stime) {
	que[wp].id = id; que[wp].stime = stime; wp++;
}
void pop() { rp++; }
struct QUE front() { return que[rp]; }
int empty() { return wp == rp; }
int reduce(int bt) {
	int cnt = 0;
	while (!empty()) {
		struct QUE tmp = front();
		if (tmp.stime > bt) break;
		pop();
		if ((client[tmp.id].login == 0) || (tmp.stime != client[tmp.id].stime)) continue;
		client[tmp.id].login = 0; cnt++;
	}
	return cnt;
}
/// 사용자의 코드를 초기화 한다.
/// 매 테스트 케이스마다 한번 호출 된다.
void initUser(int baseTick) {
	basetime = baseTick; remainuser = 0; curtime = 0;
	wp = rp = 0;
	Nid = 0; tnodeidx = 0;
	for (int i = 0; i < MAXN; i++) {
		htbl[i].next = NULL;
	}
}
/// PC방에 온 새로운 손님이 회원가입하는 경우 등록하고 기본이용시간을 제공한다.
/// 현재 접속되어 있는 회원수를 반환한다.
/// 기존 회원과 identity가 같은 회원이 입력되지 않으며 최대 50000번 호출 될 수 있다.
int joinGuest(char* identity, char  * password) {
	int id = newid(identity);
	client[id].login = 1; client[id].stime = curtime; strcopy(client[id].pw, password);
	remainuser++;
	push(id, curtime);
	return remainuser;
}
/// id가 identity인 손님이 로그 아웃을 요청한 경우 처리하는 코드이다.
/// 이미 로그 아웃된 id가 입력될 수 있다.
/// 현재 접속되어 있는 회원수를 반환한다.
int logoutGuest(char*identity) {
	int id = SearchId(identity);
	if ((id > 0) && client[id].login) {
		client[id].login = 0; client[id].stime = INF; remainuser--;
	}
	return remainuser;
}
/// 1. 현재 로그인된 회원이고(identity가 등록되어 있고 로그인됨) password가 맞는다면
///    손님의 이용시간을 baseTick으로 초기화하고 현재 접속되어 있는 회원수를 반환한다.
/// 2. 이미 회원가입이 된 회원이고(identity가 등록됨) password가 맞는다면
///    손님의 이용시간을 baseTick으로 초기화하고 현재 접속되어 있는 회원수를 반환한다.
/// 3. 가입된 회원이 아니거나 password가 맞지 않다면 현재 접속되어 있는 회원수를 반환한다.
int contactGuest(char*identity, char*password) {
	int id = SearchId(identity);
	if ((id > 0) && !strcompare(client[id].pw, password)) {
		if (!client[id].login) {
			client[id].login = 1; remainuser++;
		}
		client[id].stime = curtime; push(id, curtime);
	}
	return remainuser;
}
/// 모든 로그인된 손님의 tick을 1 줄인다.
/// 남은 시간이 0인 사용자를 일괄 로그아웃 시키고 이때 로그아웃된 손님의 수를 반환한다.
int reduceTick() {
	++curtime;
	int cnt = reduce(curtime - basetime);
	remainuser -= cnt;
	return cnt;
}
/// 현재 접속되어 있는 회원수를 반환한다.
/// 매 테스트 케이스마다  1번 호출된다.
int remainGuest() {
	return remainuser;
}
//3144 : 설문조사
#ifndef NULL
#define NULL 0
#endif
#define MAXCMD ((int)7e4)
#define MAXSTU ((int)5e4 + 10)
#define MAXCEL ((int)1e4 + 10)
#define MAXLEN (10 + 1)
//유명인물
int strcompare(char *a, char *b) {//같은 문자열이면 0, 앞에가 크면 양수, 뒤에가 크면 음수
	int i;
	for (i = 0; a[i]; i++) {
		if (a[i] != b[i]) break;
	}
	return a[i] - b[i];
}
void strcopy(char *dst, char *src) {
	while (*dst++ = *src++);
}
int hashfunc(char *a) {
	int hcode = 5381;
	for (int i = 0; a[i]; i++) {
		hcode = (hcode * 33 + a[i]) % MAXCEL;
	}
	return hcode;
}
int Nid;
struct HTBL {
	char org[MAXLEN]; int id;
	struct HTBL *next;
};
struct HTBL htbl[MAXCEL];
struct HTBL hnode[MAXCEL];
int hnodeidx;
struct HTBL *hmyalloc(char *org, int id, struct HTBL *next) {
	struct HTBL *ret = &hnode[hnodeidx++];
	strcopy(ret->org, org); ret->id = id; ret->next = next;
	return ret;
}
int newid(char *org) {
	int hkey = hashfunc(org);
	struct HTBL * p = &htbl[hkey];
	while (p->next) {
		int r = strcompare(p->next->org, org);
		if (r == 0) return p->next->id;//등록된 문자열과 동일 문자열이므로 같은 아이디
		if (r > 0) break;
		p = p->next;
	}
	//새로운 문자열임
	p->next = hmyalloc(org, ++Nid, p->next);
	return Nid;
}
int searchid(char *org) {//새로운 문자열은 등록하지 않음(등록된 문자열 중에 찾기만 지원)
	int hkey = hashfunc(org);
	struct HTBL * p = &htbl[hkey];
	while (p->next) {
		int r = strcompare(p->next->org, org);
		if (r == 0) return p->next->id;//등록된 문자열과 동일 문자열이므로 같은 아이디
		if (r > 0) break;
		p = p->next;
	}
	//새로운 문자열임
	return 0;
}
struct CEL {//빠르게 지워야 하므로 double linked list
	int stuid;
	struct CEL *prev, *next;
};
struct CEL cel[MAXCEL];
struct CEL cnode[MAXCMD * 4];
int cnodeidx;
struct CEL *cmyalloc(int stuid, struct CEL *p) {//p뒤에 추가
	struct CEL *ret = &cnode[cnodeidx++];
	ret->stuid = stuid; ret->prev = p; ret->next = p->next; 
	if(p->next) p->next->prev = ret;
	return ret;
}
int blind[MAXCEL];//블라인드 처리를 위한 배열
//학생
struct STU {
	int n;//학생이 좋아하는 인물수
	int celid[4];//학생이 좋아하는 인물의 아이디(hash table로 얻은 숫자 아이디)
	struct CEL * celptr[4];//등록된 주소(빠르게 지우기 위해)
};
struct STU stu[MAXSTU];
int isPossible(int stuid) {
	for (int i = 0; i < stu[stuid].n; i++) {
		if (blind[stu[stuid].celid[i]] == 1) return 0;//블라인드 처리된 인물을 좋아함
	}
	return 1;
}
int isAnd(int stuid, int b) {
	if ((stu[stuid].n < 2) || (isPossible(stuid) == 0)) return 0;
	for (int i = 0; i < stu[stuid].n; i++) {
		if (stu[stuid].celid[i] == b) return 1;//b도 좋아함
	}
	return 0;//b는 좋아하지 않음
}
/// 새로운 설문조사 시작을 위한 초기화
void initUser(){
	Nid = 0; hnodeidx = 0; cnodeidx = 0;
	for (int i = 0; i < MAXCEL; i++) {
		htbl[i].next = NULL;
		cel[i].next = NULL;
		blind[i] = 0;
	}
}
/// 설문조사 결과를 저장
void addSurveyResult(int stdID, int cnt, char celebID[][11]){
	stu[stdID].n = cnt;
	for (int i = 0; i < cnt; i++) {
		int cid = newid(celebID[i]);
		stu[stdID].celid[i] = cid;
		stu[stdID].celptr[i] = cel[cid].next = cmyalloc(stdID, &cel[cid]);
	}
}
/// 설문조사 결과 등록을 취소
void cancelSurveyResult(int stdID){
	for (int i = 0; i < stu[stdID].n; i++) {
		struct CEL * p = stu[stdID].celptr[i];
		p->prev->next = p->next;
		if (p->next) p->next->prev = p->prev;//dummy node tail이 없으므로 뒷 노드는 없을수있음
		stu[stdID].celid[i] = 0;
		stu[stdID].celptr[i] = NULL;
	}
	stu[stdID].n = 0;
}
/// 특정 유명 인물을 선택한 학생들에 대한 모든 선호도 기록을 제외시키기
/// 예를 들어 7번 학생이 A, B, C를 선호하는데 A인물을 blind한다면
/// 7번 학생이 선호하는 B, C에 대한 기록도 제외된다.
void blindCelebID(char celebID[]){
	int cid = searchid(celebID);
	blind[cid] = 1;
}
/// 특정 유명 인물에 대한 모든 선호도 기록이 제외되어 있다면 다시 복원
void recoverCelebID(char celebID[]){
	int cid = searchid(celebID);
	blind[cid] = 0;
}
/// 특정인물을 선호하는 학생수를 리턴한다.
/// 단, blind 처리된 인물을 선정하지 않은 학생이 대상이 된다.
/// mode == 0 : 단일 인물을 선호하는 학생 수
/// mode == 1 : 두 인물 모두를 선호하는 학생 수
/// mode == 2 : 둘 중 하나 이상을 선호하는 학생 수
int uniq;
int used[MAXSTU];
int query(int mode, char celebID[][11]){
	int cnt = 0;
	int a = searchid(celebID[0]);
	if (mode == 0) {
		for (struct CEL * p = cel[a].next; p != NULL; p = p->next) {
			if (isPossible(p->stuid)) cnt++;
		}
	}
	else if (mode == 1) {
		int b = searchid(celebID[1]);
		for (struct CEL * p = cel[a].next; p != NULL; p = p->next) {
			if (isAnd(p->stuid, b)) cnt++;
		}
	}
	else {
		++uniq;
		for (struct CEL * p = cel[a].next; p != NULL; p = p->next) {
			if (isPossible(p->stuid)) cnt++;
			used[p->stuid] = uniq;//a를 좋아하는 학생들 표시
		}
		int b = searchid(celebID[1]);
		for (struct CEL * p = cel[b].next; p != NULL; p = p->next) {
			if (used[p->stuid] == uniq) continue;//a를 좋아하는 학생은 제외
			if (isPossible(p->stuid)) cnt++;
		}
	}
	return cnt;
}
//3107 : CD홀더
#ifndef NULL
#define NULL 0
#endif
#define MAXT (1 << 18)
#define MAXN ((int)1e5)
#define LEFT (0)
#define RIGHT (1)
#define MAXEMPYT (-MAXN)
#define MINEMPTY (MAXN)
#define SEQEMPTY (MAXN)
int lastn;//CD홀더 마지막 번호
int hpos;//헤더위치
int hdir;//헤더방향
int seq;//삽입된 순서용
int cdseq[MAXN + 1];//각 CD가 삽입된 순서
int maxtree[MAXT];//삽입된 cd중 번호가 제일 큰 cd
int mintree[MAXT];//삽입된 cd중 번호가 제일 작은 cd
int seqtree[MAXT];//삽입된 cd중 제일 먼저 삽입된 cd
void InitTree(int n, int s, int e) {
	maxtree[n] = MAXEMPYT; mintree[n] = MINEMPTY; seqtree[n] = SEQEMPTY;
	if (s == e) return;
	int L = n * 2, R = L + 1, m = (s + e) / 2;
	InitTree(L, s, m); InitTree(R, m + 1, e);
}
int MAXIDX(int a, int b) { return (a > b) ? a : b; }
int MINIDX(int a, int b) { return (a < b) ? a : b; }
int MINSEQ(int a, int b) { return (cdseq[a] < cdseq[b]) ? a : b; }
void update(int n, int s, int e, int idx, int mode) {
	if (s == e) {//leaf node
		if (mode) {//추가
			maxtree[n] = mintree[n] = seqtree[n] = idx;//삽입되었으므로 인덱스 저장
			cdseq[idx] = ++seq;//삽입순서 저장
		}
		else {//제거
			maxtree[n] = MAXEMPYT; mintree[n] = MINEMPTY; seqtree[n] = SEQEMPTY;
		}
		return;
	}
	int L = n * 2, R = L + 1, m = (s + e) / 2;
	if (idx > m) update(R, m + 1, e, idx, mode);
	else update(L, s, m, idx, mode);
	maxtree[n] = MAXIDX(maxtree[L], maxtree[R]);
	mintree[n] = MINIDX(mintree[L], mintree[R]);
	seqtree[n] = MINSEQ(seqtree[L], seqtree[R]);
}
int maxquery(int n, int s, int e, int qs, int qe) {
	if ((qe < s) || (e < qs)) return MAXEMPYT;
	if ((qs <= s) && (e <= qe)) return maxtree[n];
	int L = n * 2, R = L + 1, m = (s + e) / 2;
	return MAXIDX(maxquery(L, s, m, qs, qe), maxquery(R, m + 1, e, qs, qe));
}
int minquery(int n, int s, int e, int qs, int qe) {
	if ((qe < s) || (e < qs)) return MINEMPTY;
	if ((qs <= s) && (e <= qe)) return mintree[n];
	int L = n * 2, R = L + 1, m = (s + e) / 2;
	return MINIDX(minquery(L, s, m, qs, qe), minquery(R, m + 1, e, qs, qe));
}
void init(int holder_size, int head) {//번호가 0번 부터임을 주의
	lastn = holder_size - 1; hpos = head; hdir = LEFT; seq = 0;
	cdseq[SEQEMPTY] = MAXN;
	InitTree(1, 0, lastn);//빈 상태 만들기
}
void insert(int holder) {
	update(1, 0, lastn, holder, 1);
}
int first() {
	hpos = seqtree[1];//제일 먼저 삽입된 CD
	update(1, 0, lastn, hpos, 0);//해당 CD 제거
	return hpos;
}
int near() {
	int left = maxquery(1, 0, lastn, 0, hpos);//헤더 위치 왼쪽에서 삽입된 CD중 제일 큰 번호
	int right = minquery(1, 0, lastn, hpos, lastn);//헤더 위치 오른쪽에서 삽입된 CD중 제일 작은 번호
	if ((right == MINEMPTY) || ((hpos - left) <= (right - hpos))) hpos = left;
	else hpos = right;
	update(1, 0, lastn, hpos, 0);//해당 CD 제거
	return hpos;
}
int forward() {
	if (hdir == LEFT) {
		hpos = maxquery(1, 0, lastn, 0, hpos);
		if (hpos == MAXEMPYT) {//왼쪽에 CD없음
			hdir = RIGHT; hpos = mintree[1];//방향 전환
		}
	}
	else {
		hpos = minquery(1, 0, lastn, hpos, lastn);
		if (hpos == MINEMPTY) {//왼쪽에 CD없음
			hdir = LEFT; hpos = maxtree[1];//방향 전환
		}
	}
	update(1, 0, lastn, hpos, 0);//해당 CD 제거
	return hpos;
}
int left() {
	hpos = maxquery(1, 0, lastn, 0, hpos);
	if (hpos == MAXEMPYT) hpos = maxtree[1];
	update(1, 0, lastn, hpos, 0);//해당 CD 제거
	return hpos;
}
int right() {
	hpos = minquery(1, 0, lastn, hpos, lastn);
	if (hpos == MINEMPTY) hpos = mintree[1];
	update(1, 0, lastn, hpos, 0);//해당 CD 제거
	return hpos;
}
알고리즘/기타.txt · 마지막으로 수정됨: 2019/10/25 23:12 저자 trsprs