본문 바로가기
삼성전자 알고리즘/자료구조 알고리즘

15. 꼭 알아야 하는 유형

기명준 2019. 7. 21. 21:28

1. 링크드리스트 동적할당을 정적할당으로 구현

--메인 밖에서 선언
typedef struct _node {
	int x;
	struct _node *next = nullptr;
}NODE;
NODE arr[1000 * 1000 + 10];		//문제에서 나올 수 있는 모든 노드의 수(배열을 할당할 주소값으로 사용)
int cnt = 0;

--메모리 할당
NODE *newNode = &arr[cnt++];
--메모리 해제
cnt = 0;

2. 링크드리스트를 활용하여 만든 해시테이블(설정)

const int MAX = 1 << 20;
typedef struct _node {
	int x;
	struct _node *next = nullptr;
}NODE;
NODE hash_table[MAX + 10];		//나올 수 있는 해시테이블의 수
NODE arr[1000 * 1000 + 10];		//문제에서 나올 수 있는 모든 노드의 수(배열을 할당할 주소값으로 사용)
int cnt = 0;


3. 링크드리스트를 활용하여 만든 해시테이블(삽입)

void make_hash(int key, int x) {
	NODE *cur = &hash_table[key];
	NODE *newNode = &arr[cnt++];
	newNode->x = x;

	//Case 1 : 무작정 맨 앞에 연결 하는 방법
	newNode->next = cur->next;	//맨 앞에 노드 연결
	cur->next = newNode;		//해시연결해주기

	//Case 2 :조건에 따라 노드 연결
	while (cur->next != nullptr) {
		if (true) {
			newNode->next = cur->next;
			cur->next = newNode;		//해시연결해주기
		}
		else {
			cur = cur->next;
		}
	}
}

4. 링크드리스트를 활용하여 만든 해시테이블(삭제)

void delete_hash(int key) {
	if (hash_table[key].next == 0) return;
	NODE *cur = &hash_table[key];
	NODE *delete_node;
	while (cur->next != nullptr) {
		delete_node = cur->next;
		cur->next = cur->next->next;
		delete(delete_node);
	}
}

5. 링크드리스트를 활용하여 만든 해시테이블(검색)

//검색에서 사용할 때 주의
int query() {
	int key = 0;			//키 값 알아서 설정
	NODE *cur = &hash_table[key];
	while (cur->next != 0) {
		cur = cur->next;	//중요 : cur가 처음에 null이기 때문에 이 작업을 해줘야 의미 있음
	}
}

6. 구조체 멀티키 정렬(설정) : A로 정렬. A값이 같을 시 B로 정렬

const int MAX_SIZE = 100;
typedef struct _node {
	int a_con;
	int b_con;
}NODE;
NODE heap[MAX_SIZE];
int heapSize = 0;

7. 구조체 멀티키 정렬(comp 함수)

int comp(int x, int y) { // x : 부모(왼쪽), y : 자식(오른쪽)
	if (heap[x].a_con < heap[y].a_con) return 1;
	else if (heap[x].a_con == heap[y].a_con && heap[x].b_con < heap[y].b_con) return 1;
	else return 0;
}

8. 구조체 멀티키 정렬 (힙정렬) : init

void heapInit(void){heapSize = 0;}

9. 구조체 멀티키 정렬 : PUSH

int heapPush(NODE value)
{
	if (heapSize == MAX_SIZE) { return 0; }
	heapSize++;
	heap[heapSize] = value;

	int current = heapSize;
	int parent = current / 2;
	NODE temp;
	while (parent > 0)
	{
		if (comp(parent, current) == 1) {
			temp = heap[parent];
			heap[parent] = heap[current];
			heap[current] = temp;
			current = parent;
			parent = current / 2;
		}
		else break;
	}
	return 1;
}

10. 구조체 멀티키 정렬 : POP

int heapPop(NODE* value)
{
	if (heapSize <= 0) { return -1; }

	*value = heap[1];
	heap[1] = heap[heapSize];
	heapSize--;
	int current = 0;
	int parent, left, right;
	parent = 1; left = 2 * parent; right = left + 1;
	while (left <= heapSize)
	{
		if (left == heapSize)
		{
			current = left;
		}
		else if (comp(right,left) == 1) {
			current = left;
		}
		else current = right;

		if (comp(parent, current) == 1)
		{
			NODE temp = heap[parent];
			heap[parent] = heap[current];
			heap[current] = temp;
			parent = current; left = 2 * parent; right = left + 1;
		}
		else 	break;
	}
	return 1;
}

11. 구조체 멀티키 정렬 : main

int main(int argc, char* argv[])
{
	int T, N;
	scanf("%d", &T);
	for (int test_case = 1; test_case <= T; test_case++)
	{
		scanf("%d", &N);
		heapInit();
		for (int i = 0; i < N; i++)
		{
			int value;
			scanf("%d", &value);
			heapPush(value);
		}
		printf("#%d ", test_case);
		for (int i = 0; i < N; i++)
		{
			int value;
			heapPop(&value);
			printf("%d ", value);
		}
		printf("\n");
	}
	return 0;
}

12. UpperBound

	int upperBound(int arr[], int s, int e, int key) {
		int m;
		while (s < e) {
			m = (s + e) / 2;
			if (arr[m] <= key) s = m + 1;
			else e = m;
		}
		return e;
	}

13. LowerBound: 참고 : http://bitly.kr/rhV6yq

	int lowerBound(int arr[], int s, int e, int key) {
		int m;
		while(s<e){
			m = (s + e) / 2;
			if (arr[m] < key) s = m + 1;
			else e = m;
		}
		return e;
	}

14. DFS 레이블링 (사전작업)

int map[10][10] = { {0,0,0,0,0,0,0,0,0,0},
					{0,1,0,0,0,0,0,0,0,0},
					{0,1,0,0,0,0,0,1,0,0},
					{0,1,1,1,1,0,0,1,1,0},
					{0,0,0,0,0,0,0,1,0,0}, 
					{0,0,0,0,1,0,0,0,0,0},
					{0,0,0,0,1,0,0,0,0,0},
					{0,0,0,0,1,1,1,1,0,0},
					{0,1,1,0,0,0,0,0,0,0},
					{0,0,0,0,1,1,1,0,0,0}
};
int visited[10][10];
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
int n;	//방 크기

15. DFS 레이블링 (dfs) : label 표시, 방 갯수 세기

int dfs(int r, int c, int label) {
	visited[r][c] = 1;	//방문
	int cnt = 0;		//방 개수
	map[r][c] = label;
	//상하좌우로 이동
	for (int i = 0; i < 4; i++) {
		int nr = r + dr[i], nc = c + dc[i];	//새로운 방향
		if (0 <= nr && nr < n && 0 <= nc && nc < n && visited[nr][nc]==0 && map[nr][nc]==1) {
			//갈 수 있는 조건에 해당하면 이동
			cnt += dfs(nr, nc, label) +1;
		}
	}
	return cnt;
}

16. DFS 레이블링 : 메인

int main() {
	n = 10;
	int label = 1;

	for (int r = 0; r < n; r++) {
		for (int c = 0; c < n; c++) {
			if (map[r][c]==1 && visited[r][c] == 0) {
				cout<<dfs(r, c, label++)+1<<endl;
			}
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			printf("%2d", map[i][j]);
		}
		cout << endl;
	}
}

17. DFS non-recursive 구현

typedef struct _node {
	int r;
	int c;
}NODE;

int map[10][10] = { {0,0,0,0,0,0,0,0,0,0},
					{0,1,0,0,0,0,0,0,0,0},
					{0,1,0,0,0,0,0,1,0,0},
					{0,1,1,1,1,0,0,1,1,0},
					{0,0,0,0,0,0,0,1,0,0},
					{0,0,0,0,1,0,0,0,0,0},
					{0,0,0,0,1,0,0,0,0,0},
					{0,0,0,0,1,1,1,1,0,0},
					{0,1,1,0,0,0,0,0,0,0},
					{0,0,0,0,1,1,1,0,0,0}
};
int visited[10][10];
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
int n;	//방 크기
//
NODE stack[10 * 10 + 10];
int sp = 0;
////dfs non-recursive
void iter_dfs(int r, int c, int label) {
	visited[r][c] = 1;
	int cnt = 0;
	NODE node;
	node.r = r; node.c = c;
	stack[sp++] = node;	//push
	while (sp != 0) {//stack is not empty
	//상하좌우로 이동
	//pop
		node = stack[--sp];
		int temp_r= node.r, temp_c= node.c;
		map[temp_r][temp_c] = label;

		for (int i = 0; i < 4; i++) {
			int nr = temp_r + dr[i], nc = temp_c + dc[i];	//새로운 방향
			if (0 <= nr && nr < n && 0 <= nc && nc < n && visited[nr][nc] == 0 && map[nr][nc] == 1) {				//갈 수 있는 조건에 해당하면 이동
				map[nr][nc] = label;
				visited[nr][nc] = 1;	//방문
				node.r = nr; node.c = nc;
				stack[sp++] = node; //push
			}
		}
	}
}
int main() {
	n = 10;
	int label = 1;

	for (int r = 0; r < n; r++) {
		for (int c = 0; c < n; c++) {
			if (map[r][c] == 1 && visited[r][c] == 0) {
				iter_dfs(r, c, label++);
			}
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			printf("%2d", map[i][j]);
		}
		cout << endl;
	}
}

18. 디렉터리 연결 리스트 노드

struct data {
	char name[13];
	data* parent, * next, * child;
};

19. 트라이 노드

struct Try {
	int num, cnt;
	Try* next[26];
};
struct data {
	int parent;
	Try* child;
}mem[20020];

20. 링크드 리스트 조건에 따른 정렬 A.a조건>B.a조건 if A.a==b.a then A.b>B.b if A.a==B.a and A.b==B.b then A.c>B.c

typedef struct _node {
	int id;
	int a, b, c;
	struct _node* next = NULL;
}NODE;

NODE old_n, new_n, m_alloc[15];
int m_cnt = 0;

21. 링크드 리스트 정렬 : a 구조체를 조건에 따라 정렬된 링크드 리스트로 만들기

테스트를 위해 구조체 배열 a[10]을 선언한 뒤 순서대로 링크드 리스트를 만듬

	NODE a[10];
	NODE* cur = &old_n;
	for (int i = 0; i < 10; i++) {
		a[i].a = i; a[i].b = i; a[i].c = i;
		a[i].id = i + 1;
		while (cur->next != NULL) {
			cur = cur->next;
		}
		cur->next = &a[i];
	}
    cur = &old_n;	//다시 처음부터 돌기 위해 cur 위치 조정

cur를 돌면서 cur2에서 조건에 따라 재정렬

	NODE* cur2;
	while (cur->next != NULL) {
		cur = cur->next;
		NODE* newNode = &m_alloc[m_cnt++];
		newNode->a = cur->a;
		newNode->b = cur->b;
		newNode->c = cur->c;
		newNode->id = cur->id;
		//newNode = cur; // (X)

		cur2 = &new_n;
		while (cur2->next != NULL) {
			//조건에 따른 연결
			if (cur->a > cur2->next->a) {
				break;
			}
			else if (cur->a == cur2->next->a && cur->b > cur2->next->b) {
				break;
			}
			else if (cur->a == cur2->next->a && cur->b == cur2->next->b && cur->c > cur2->next->c) {
				break;
			}
			else {
				cur2 = cur2->next;
			}
		}
		newNode->next = cur2->next;
		cur2->next = newNode;
	}

잘 정렬 됐는지 보기 위해 cur2의 위치는 다시 &new_n 으로 조정 후 출력

	cur2 = &new_n;
	while (cur2->next != NULL) {
		cur2 = cur2->next;
		cout << cur2->id << endl;
	}

22. Open Address 방법: 초기 설정

#define MAX    10
#define HASH_KEY 5 
#define STEP         1 

int Hash_table[MAX] = { -1, -1, -1, -1,  -1, -1, -1, -1, -1, -1 }; //초기값 -1로

23. Open Address : key를 얻고 만약 key값에 이미 할당되어 있다면 다음 값 이용

 

int Get_Hash_Key(int id)
{
	return id % HASH_KEY;
}
int Insert_Data(int  data) {
	int i, key;
	i = 0;
	key = Get_Hash_Key(data);
	//여기에 함수를 완성한다.
	for (i = key; i != key - STEP; i = ((i + 1) % 10)) {
		if (Hash_table[i] == -1) {
			//비어있으면 넣는다.
			Hash_table[i] = data;
			return Hash_table[i];
		}
	}
}

삭제도 마찬가지 :

int Delete_Data(int data) {
	int i, key;
	key = Get_Hash_Key(data);
	//여기에 함수를 완성한다.
	for (i = key; i != key - STEP; i = ((i + 1) % 10)) {
		if (Hash_table[i] == data) {
			//비어있으면 넣는다.
			int tmp = i;
			Hash_table[i] = -1;
			return tmp;
		}

		//if(Hash_table[i]==-1){
		//  return -1;
		//}
	}
	return -1;
}

Chaning 방법: 위 참고

저작자표시 비영리 변경금지

'삼성전자 알고리즘 > 자료구조 알고리즘' 카테고리의 다른 글

BFS / DFS  (0) 2019.06.12
분수 계산  (0) 2019.06.02
12. 배열 Array  (0) 2019.05.17
11. B트리 / B+트리 / B*트리  (0) 2019.05.16
10. 트리  (0) 2019.05.16

'삼성전자 알고리즘/자료구조 알고리즘' Related Articles

티스토리툴바