□ 강사 정보

knox : swc50.sec
외부메일 : [email protected]

§ Day 01 (Bit operator & Linked List)

□ C++ Syntax

// long long -> ll 로 대체 가능
typedef long long ll;	   

// LM = 1000000 
// e 뒤의 숫자만큼 10이 곱해지고 int 로 캐스팅 하기 ! 
// 2e3 = 2000
int LM = (int)1e6; 	   

// 삼항연산자  
// 조건 ? 참 : 거짓
int max = a > b ? a : b;   

// string 과 int 한 번에 받아 for 문 
char in[100];
int B;
scanf("%s%d", in, &B);

for (int i = 0; in[i]; i++) // while in[i] is True

ctrl + k + c : 선택 영역 주석 처리
ctrl + k + u : 선택 영역 주석 해제

□ Bit-wise Operator

AND (&)
SHIFT( >> / << )
- : 오른쪽으로
- << : 왼쪽으로 !

□ Base Conversion

Horner's method
- for 문 수행할 때 앞서 계산한 값을 이용하여 계산하기 !

□ [A] 진법 변환

A 진법 수 N 을 입력 받아 B 진법 수로 출력하는 프로그램 작성
- N 에 사용되는 값은 0 ~ 9, A ~ Z 이다.
오답노트
- %s 로 입력받은 문자열에 대해 for 문을 사용할 때에는 조건을 in[i] 로만 주어도 된다.
- int 로만 받기에 너무 큰 숫자일 경우 오답이 발생할 수 있다 ! 따라서 long long 을 define 해서 사용하자.

#include <stdio.h>

typedef long long LL;

int A, B;
char in[100], out[100];

// ASCII code : '0' (48) 'A' (65) 'a' (97)
int conv(char ch)
{
	return ch >= 'A' ? ch - 'A' + 10 : ch - '0';
}

char reconv(int in)
{
	return in >= 10 ? 'A' + in - 10 : in + '0';
}

LL base_conv_to_decimal(int A, char in[])
{
	LL ret = 0;

	for (int i = 0; in[i]; i++) // in[i] is True
		ret = (ret * A + conv(in[i]));

	return ret;
}

int base_conv_from_decimal(int B, LL in)
{
	if (in == 0) {
		out[0] = reconv(0);
		return 0;
	}

	int i;
	LL rest = in;

	for (i = 0; rest > 0; i++) {
		int temp = rest % B;
		rest /= B;
		out[i] = reconv(temp);
	}
	return i - 1;
}


int main()
{
	freopen("input.txt", "r", stdin);

	while (1) {

		scanf("%d", &A);
		if (A == 0) break;

		scanf("%s%d", in, &B);

		LL temp = base_conv_to_decimal(A, in);
		int len = base_conv_from_decimal(B, temp);

		for (int i = len; i >= 0; i--)
			printf("%c", out[i]);

		printf("\n");
	}

	return 0;
}

□ Two Pointers

포인터가 같은 방향으로 진행하는 경우
- ex) 연속된 부분 수열합이 6이 되는 개수 (단, 수열 값이 0 이상인 경우)
- 새로운 값이 왔을 때 전 값이 음수이면 버리자.. !
포인터가 다른 방향으로 진행하는 경우
- ex) 수열이 정렬되어 있는 경우, 합이 0과 가장 가까운 쌍

□ Sliding Window

two pointer 와 비슷하고 크기만 고정
매번 마지막 다음 위치를 포함하고 맨 처음 위치를 제거

□ [B] 수열

#ifdef THIS_CODE_IS_RUNNING

#include <stdio.h>
#define MAX int(1e5 + 5)

int N, K, in;
int sum[MAX], max = -5555555;

void input_data()
{
	freopen("input.txt", "r", stdin);
	
	scanf("%d %d", &N, &K);
	
	int temp = 0;
	for (int n = 0; n < N; n++)
	{
		scanf("%d", &in);
		sum[n] = temp + in;
		temp += in;
	}
}

int main()
{
	input_data();

	for (int i = K - 1; i < N; i++)
	{
		int temp = sum[i] - sum[i - K];
		max = (max < temp) ? temp : max;
	}

	printf("%d\n", max);
	return 0;
}

#endif

□ Time complexity

Big-O 표기법 (N의 최고 차수만 고려. 계수 무시)
- 가장 많은 loop 를 필요로 하는 로직이 프로그램의 시간 복잡도
- 대략 O(1억) 정도를 1초로 생각
- ex) O(2n^2 + 3n) ==> O(n^2)

□ Space complexity

1 MB = 1,024 KB = 1,048,576 B
1 MB == 1,000 KB 로 편의상 이렇게 계산하자.
Pro 제한조건 : 256 MB
- 코드 영역 : 실행할 프로그램의 코드. 구조체, CLASS 에서의 함수 등은 코드 영역으로 들어감.
- 데이터 영역 : 전역/정적 변수
- 힙 영역 : 사용자 동적 할당 (런 타임에 크기가 결정됨)
- 스택 영역 : 지역/매개 변수 (컴파일 타임에 크기가 결정)
자료형

모든 pointer 변수는 8 bytes !

아래 코드에서 Node people[100] 이 사용하는 총 메모리 크기는 ?
- 구조체 변수의 함수는 딱 한 번 코드 영역에 들어가기 때문에 함수 제외하고 생각하면 됨.
- 따라서 (100 + 4 + 16 + 80) B * 100 개 = 20,000 B = 대략 20 KB

struct Node {
	char name[100];               // 1 B * 100 = 100 B
	int score;                    // 4 B 
	Node *prev, *next;            // 8 B * 2 = 16 B
	Node *child[10];              // 8 B * 10 = 80 B

	int max(int a, int b) { return a > b ? a : b; }
	int min(int a, int b) { return a < b ? a : b; }
} people[100];

□ [C] 연속 부분합

오답노트
- **N 이 100,000 라고 주어지면 n^2 으로 풀지 말라는 의미 ... ! nlogn 혹은 n 으로 풀자 **
- O(n^2) 으로 계산하게 되면 시간 초과 발생 .. !

#define THIS_CODE_IS_RUNNING
#ifdef THIS_CODE_IS_RUNNING

#include <stdio.h>
#define MAX int(1e5 + 5)
int N, in[MAX], sum, max;

int main()
{
	freopen("input.txt", "r", stdin);
	scanf("%d", &N);

	for (int n = 0; n < N; n++)
	{
		scanf("%d", &in[n]);
		if (sum < 0) sum = in[n]; // 0보다 작아지는 sum 은 더해 줄 필요가 없어짐 ! 
		else sum += in[n];

		max = (max < sum) ? sum : max;
	}

	printf("%d\n", max);
	return 0;
}

#endif

□ [D] 용액

#ifdef THIS_CODE_IS_RUNNING

#include <stdio.h>
#define MAX (int)(1e5 + 5)

int N, num[MAX];
int min = 2e9;
int ansL, ansR;

void input_data()
{
	freopen("input.txt", "r", stdin);
	scanf("%d", &N);

	for (int n = 0; n < N; n++) scanf("%d", num + n);
}

int abs(int x) { return (x < 0) ? -x : x; }

void save_val(int L, int R)
{
	ansL = num[L], ansR = num[R];
}

void my_solution()
{
	int L = 0, R = N - 1;

	while (L < R) 
	{
		int sum = num[L] + num[R];

		if (sum == 0) {
			save_val(L, R);
			break;
		}

		if (min > abs(sum)) {
			min = abs(sum);
			save_val(L, R);
		}

		if (sum > 0) R--;
		else L++;
	}

	printf("%d %d\n", ansL, ansR);
}

int main()
{
	input_data();
	my_solution();

	return 0;
}

#endif

□ Linked List

node 에는 data field + link field
- link field 는 배열로도 가질 수 있음.
생성 방법
- memory pool : 정적 배열을 필요한 만큼 생성하여 순서대로 이용 (구현 편리) . 초기화 시에도 사용된 배열 위치만 0 으로 옮겨주면 됨.
- 동적 할당 : new 혹은 malloc 으로 필요할 때 동적 할당. 사용 후 delete 또는 free 로 반드시 해제 . 메모리 단편화. 테스트마다 초기화 부담. 구현 복잡.
설계 시 고려야 할 사항 : singly ? doubly ? / 2. dummy 0 ? 1 ? 2 ? / 3. insert 혹은 erase 는 head only ? random access ?
- Singly / Head access only (Stack style) / Dummy X . 구현하기 가장 간편. 자주 쓰임. 순서 상관 없이 head 로만. hash chaining 시 주로 쓰임
- Singly / Random access / Dummy 1 . random access 할 때는 꼭 dummy node 를 사용하도록.. ! . 이 방법보다는 아래 (Doubly / Random) 을 쓰는 방식이 더 많음.
- Doubly / Random access / Dummy 1 . 노드 간 자유로운 이동 / 특정 위치의 삽입, 삭제 시 유용

□ [E] 스택

#define THIS_CODE_IS_RUNNING
#ifdef THIS_CODE_IS_RUNNING

#define MAX (100+5)
#include <stdio.h>
int N, bcnt, size;

// struct 는 class 와 비슷한데, default 가 public 인 점이 class 와 다르다 .
// class 의 default : private
struct _node
{
	int val;
	_node *next;
	_node *alloc(int _val, _node* _next) 
	{
		val = _val;
		next = _next;
		return this;
	}
} stack[MAX], *head;
// head 는 pointer 로 선언 

void push_node()
{
	int in;
	scanf("%d", &in);
	head = stack[bcnt++].alloc(in, head);
	size++;
}

void size_stack()
{
	printf("%d\n", size);
}

void pop_node()
{
	if (head == NULL) // NULL 혹은 0 이면 비어져 있는 것
		printf("empty\n");
	
	else
	{
		printf("%d\n", head->val);
		head = head->next;
		size--;
	}
}

void solution()
{
	freopen("input.txt", "r", stdin);
	scanf("%d", &N);

	int val;

	for (int n = 0; n < N; n++)
	{
		char cmd;
		scanf(" %c", &cmd); 
		// 앞에 한 칸을 띄어주면 enter 나 의미 없는 값을 걸러주게 됨. 
		
		if (cmd == 'i')		 push_node();
		else if (cmd == 'c') size_stack();
		else if (cmd == 'o') pop_node();
	}
}

int main()
{
	solution();
	return 0;
}

#endif

□ [F] 큐

head 위치는 항상 dummy 를 가리킴
cursor 가 위치가 바뀌면서 마지막 삽입된 node 를 가리킴
오답노트
- 한 번 linked list 가 empty 가 된 이후에 다시 push 하면 head->next 로 잘 연결되지 않음...

#include <stdio.h>
#define MAX (100 + 5)

int N, bcnt, size;

struct _node {
	int val;
	_node* prev;
	_node* next;
	_node* alloc(int _val, _node* _prev, _node* _next) {
		val = _val, prev = _prev, next = _next;
		if (prev) prev->next = this;
		if (next) next->prev = this;
		return this;
	}
	_node* erase() {
		if (prev) prev->next = this->next;
		if (next) next->prev = this->prev;
		return prev;
	}
} buff[MAX], *head, *cur;

void init() { bcnt = 0; head = cur = buff[bcnt++].alloc(0, 0, 0); }
void push_node() {
	int val;
	scanf("%d", &val);

	cur = buff[bcnt++].alloc(val, cur, cur->next);
	size++;
}
void print_size() { printf("%d\n", size); }
void pop_node() {

	if (head->next == NULL)
		printf("empty\n");
	else {
		printf("%d\n", head->next->val);
		head = head->next;
		size--;
	}
}

int main()
{
	freopen("input.txt", "r", stdin);
	scanf("%d", &N);
	init();

	for (int n = 0; n < N; n++) {
		char cmd;
		scanf(" %c", &cmd);

		if (cmd == 'i')	push_node();
		if (cmd == 'c')	print_size();
		if (cmd == 'o')	pop_node();
	}

	return 0;
}

□ [G] 요세푸스

#include <stdio.h>
#define MAX (int)(1e5 + 5)

int N, K, bcnt;

struct _dnode {
	
	int num;
	_dnode* prev;
	_dnode* next;
	_dnode* alloc(int _num, _dnode* _prev, _dnode* _next) {
		num = _num, prev = _prev, next = _next;
		if (prev) prev->next = this;
		if (next) next->prev = this;
		return this;
	}

	_dnode* erase()	{
		if (prev) prev->next = this->next;
		if (next) next->prev = this->prev;
		return next;
	}
} dbuff[MAX], *head, *dcur;

void my_solution()
{
	dcur->next = dcur->prev = dcur = dbuff[bcnt++].alloc(1, 0, 0);

	for (int n = 2; n <= N; n++)
		dcur = dbuff[bcnt++].alloc(n, dcur, dcur->next);

	for (int n = 0; n < N; n++)
	{
		for (int k = 0; k < K; k++)
			dcur = dcur->next;

		printf("%d ", dcur->num);
		dcur->erase();
	}
	printf("\n");
}

int main()
{
	scanf("%d %d", &N, &K);
	my_solution();

	return 0;
}

□ [H] 키로거

오답노트
- doubly linked list 일 때에는 곡 dummy node 를 1개 이상 만들자 ! . head = cur = buff[bcnt++].alloc(0, 0, 0); . head 의 next 는 항상 첫 시작을 가리키게 된다.
- Test case 가 있는 경우는 반드시 초기화를 해주지 . bcnt = 0 으로 해주고 dummy node 만들어 주면 됨.
- remove 할 때에는 꼭 앞 뒤 상황을 체크해주어야 한다.

#include <stdio.h>
#define MAX (int)(1e6 + 5)

int T, bcnt;
char in[MAX];

struct _node
{
	char ch;
	_node* prev;
	_node* next;

	_node* alloc(char _ch, _node* _prev, _node* _next)
	{
		ch = _ch, prev = _prev, next = _next;
		if (prev) prev->next = this;
		if (next) next->prev = this;
		return this;
	}

	_node* erase()
	{
		if (prev) prev->next = this->next;
		if (next) next->prev = this->prev;
		return prev;
	}
} buff[MAX], *head, *cur;


void init() { bcnt = 0; head = cur = buff[bcnt++].alloc(0, 0, 0); } // init 꼭 해주기 !!! 
void push_node(char ch) { cur = buff[bcnt++].alloc(ch, cur, cur->next); }
void pop_node() { if (cur != head) cur = cur->erase(); } // head 와 동일한 경우에 주의 
void move_left() { if (cur->prev) cur = cur->prev; }
void move_right() { if (cur->next) cur = cur->next; }
void print_node() {
	for (_node *temp = head->next; temp; temp = temp->next)
		printf("%c", temp->ch);
	printf("\n");
}

int main() {
	freopen("input.txt", "r", stdin);
	scanf("%d", &T);

	for (int t = 0; t < T; t++)
	{
		init();
		scanf("%s", in);

		for (int i = 0; in[i]; i++)
		{
			if (in[i] == '-') pop_node();
			else if (in[i] == '<') move_left();
			else if (in[i] == '>') move_right();
			else push_node(in[i]);
		}
		print_node();
	}
	
	return 0;
}

§ Day 02 (Linked List & Hash)

□ [I] 등수 찾기

□ Hash

key 같으면 같은 정보라는 것을 판별할 수 있는 고유 값
search : 원하는 data 의 실제 저장 위치 (index) 찾아나가는 방법
종류 : linear search / direct address table / hash O(1+a)
알파벳 (대소문자) 인 경우 a~~z : 1~~26 + A~~Z : 27~~52 즉 53 진법으로도 사용 가능.
- 두 자리 : aA : 1 * 53 + 27
- 세 자리 : abZ : 1 * 53 ^ 2 + 2 * 53 + 52
- 소문자 4자리 (27^4) 이면 531,441 즉 50만 정도라 hash table 없이 direct table 로도 가능.
- 소문자 5자리 (27^5) 이면 15,000,000 B = 15,000 KB = 15MB 정도라 direct table 로도 가능.
- 6자리 이상으로 가면 이 때부터는 hash 로 ... (단 데이터 수가 적으면 hash 사용 안하고 linear search 도 가능)
hash table 에서 충돌하는 것은 chaining 적용

문제 풀이
- hash key 설정 (data 의 고유 값을 나타낼 수 있는 정보로 설정)
- hash function 설정 (djb2 함수 / k 진법)

collision 처리 방식 설정 (chaining / linear probing - 성능 보장이 안되는 경우 많음.. )
hash table size 설정 . chaining 시 들어오는 data 수의 제곱 수 만큼 해도 충분

예시
- 1 ~ 100 (hash 안해도 됨)
- -100 ~ 100 (hash 안해도 됨)
- 0 ~ 2^32-1 (모듈러 해서 hash table)
- 소문자 4자 (hash 안해도 됨. direct addressing 으로도 가능)
- 대,소문자,숫자 4자 (63진법.. 이므로 이 경우는 hash)
- 숫자배열 (1 ~ 100 의 4개짜리 이면 hash func 으로..)
- 2차원 맵
hash function
- 정수를 해싱할 경우 (division method / multiplication method)
- 문자열을 해싱할 경우 (djb2 함수)

// 나눗셈법 hash 함수
/* 테이블 사이즈를 2 의 제곱수로 정하는 경우 다음과 같은 해시 함수를 사용할 수 있다
아래
SIZE = (1<<25) 는 2 의 제곱수의 한 예이다
*/
Const
int SIZE = (1<<25) ; // 해시 테이블 사이즈 2 25 = 33554432 
// SIZE : 1 0000 0000 0000 0000 0000 0000
const int MOD = SIZE 1; // 33554432 1 = 33554431
// MOD  : 0 1111 1111 1111 1111 1111 1111

int hashTable [SIZE];
unsigned int hashM int n) {
// n % (2 의 제곱수 ) => n & ((2 의 제곱수) -1) 로 비트 연산을 사용할 수 있다
return n & MOD; // return n % SIZE; 와 동일 
}

// djb2 방식 (http://www.cse.yorku.ca/~oz/hash.html) 
/// hash = 5381 * 33 ^ n + str [0] * 33 ^ (n 1) + str [0] * 33 ^ (n-2) + … + str[n-1] * 1
/// 문자열을 5381 을 seed 로 하는 33 진법수로 읽는 것과 같은 의미이다
unsigned long djb2( unsigned char *str) {
   unsigned long hash = 5381 ;; // 소수
   int c;
   while (c = *str++) {
      hash = ((hash << 5) + hash) + c; /* hash = hash * 33 + c ;
      /// hash 는 32bit 정수이므로 문자열이 길어지면 32bit 초과 분은 소멸된다
      /// 따라서 hash = (hash*33 + c) %(long long)4294967296; 과 같은 의미가 된다
   }
   return hash;
   /// return hash % MOD; 와 같이 바꾸어 사용할 수도 잇다.

collision 충돌 관리
- hashing 되는 원소를 모두 하나의 linked list 로 관리.
- 추가적인 linked list 필요

// chaining 을 이용한 충돌 해결 
// 정적 배열과 myAssign 멤버 함수 사용 (해시 값이 충돌하는 경우 키를 스택 형식으로 저장) 
const int MOD = SIZE - 1;
const int BUFFERSIZE = (int) 16e6 + 5;
int bcnt;
struct _node {
   int key, cnt;
   _node* next;
   _node* alloc(int _key, _cnt, _node* _neext) {
      key = _key, cnt = _cnt, next = _next;
      return this;
   }
} buff[BUFFERSIZE], *hash[SIZE];

void probing (int hidx, int key) {
   _node *p = hash[hidx];
   while (p && p->key != key) { p = p->next; }
   // p->key == key 인 경우
   if (p && p->key == key) p->cnt++;
   else // hash[hidx] 의 맨 앞에 새로운 노드 삽입
      hash[hidx] = buff[bcnt++].alloc(key, 1, hash[hidx]);
}

// chaining 을 이용한 충돌 해결 
// 정적 배열과 myAssign 멤버 함수 사용 (해시 값이 충돌하는 경우 키를 오름차순으로 저장) 
const int MOD = SIZE - 1;
const int BUFFERSIZE = (int) 16e6 + 5;
int bcnt;
struct _node {
   int key, cnt;
   _node* next;
   _node* alloc(int _key, _cnt, _node* _neext) {
      key = _key, cnt = _cnt, next = _next;
      return this;
   }
} buff[BUFFERSIZE], *hash[SIZE];

void probing2(int hidx, int key) {
   _node *p = hash[hidx], *q = p; // *q 추가 됨 ! 
   while (p && p->key < key) { q = p, p = p->next; }

   // hash[hidx] == NULL 이거나 hash[hidx]->key > key 인 경우 
   if (p == hash[hidx]) { hash[hidx] = buff[bcnt++].alloc(key, 1, p); }

   else if (p && p->key == key) p->cnt++;

   // q 와 p 사이에 새로운 노드 삽입
   else { q->next = buff[bcnt++].alloc(key, 1, p); }
   
}

□ [K] 합이 0이 되는 쌍

오답노트
- hash 문제 풀이 : key 설정 / function 설정 / collision 처리 - chaining / hash table size 설정
- singly 일 경우의 format : head = buff.alloc(X, head)
- stack style 즉 singly 에서는 dummy 노드 필요 없이 맨 앞에 넣어줌.
- probing 을 반드시 해주자.. 그리고 hcnt 와 hidx 를 헷갈리지 않기 ㅠㅠㅠ
- SIZE 는 어떻게 정해지는지.. 아직 잘 모르겠음.

const int SIZE = 1 << 24;
const int MASK = SIZE - 1;
const int MAX = 4003;
unsigned long long ans;

int N, A[MAX], B[MAX], C[MAX], D[MAX], hcnt;

struct _hash {
	int key; 
	int cnt;
	_hash* next;
	_hash* alloc(int _key, _hash* _next) {
		key = _key, next = _next;
		return this;
	}
} hbuff[MAX * MAX], *hash[SIZE]; // hash size 는 24. buff size 는 입력 수 * 입력 수

int hash_func(int x) { return x & MASK; }
_hash* probing(int key) {
	int hidx = hash_func(key);

	for (_hash* cur = hash[hidx]; cur; cur = cur->next )
		if (cur->key == key) return cur;
	return 0;
}

void insert_hash()
{
	for (int a = 0; a < N; a++) {
		for (int b = 0; b < N; b++) {
			int hidx = hash_func(A[a] + B[b]);

			_hash* cur = probing(A[a] + B[b]);
			if (cur) cur->cnt++;
			else {
				hash[hidx] = hbuff[hcnt++].alloc(A[a] + B[b], hash[hidx]);
				hash[hidx]->cnt++;
			}
		}
	}
}

void check_hash()
{
	for (int c = 0; c < N; c++) {
		for (int d = 0; d < N; d++) {
			int hidx = hash_func(-(C[c] + D[d]));

			_hash* cur = probing(-(C[c] + D[d]));
			if (cur) 
				ans += cur->cnt;
		}
	}
}

int main()
{
	freopen("input.txt", "r", stdin);
	scanf("%d", &N);

	for (int n = 0; n < N; n++)
		scanf("%d %d %d %d", A + n, B + n, C + n, D + n);

	insert_hash();
	check_hash();

	printf("%llu\n", ans);
	return 0;
}

DS Certi (Pro) Linked List , Hash (기본 문제) - jjin-choi/study_note GitHub Wiki

§ Day 01 (Bit operator & Linked List)

□ C++ Syntax

□ Bit-wise Operator

□ Base Conversion

□ [A] 진법 변환

□ Two Pointers

□ Sliding Window

□ [B] 수열

□ Time complexity

□ Space complexity

□ [C] 연속 부분합

□ [D] 용액

□ Linked List

□ [E] 스택

□ [F] 큐

□ [G] 요세푸스

□ [H] 키로거

§ Day 02 (Linked List & Hash)

□ [I] 등수 찾기

□ Hash

□ [K] 합이 0이 되는 쌍

⚠️ GitHub.com Fallback ⚠️

DS Certi (Pro) Linked List , Hash (기본 문제) - jjin-choi/study_note GitHub Wiki

§ Day 01 (Bit operator & Linked List)

□ C++ Syntax

□ Bit-wise Operator

□ Base Conversion

□ [A] 진법 변환

□ Two Pointers

□ Sliding Window

□ [B] 수열

□ Time complexity

□ Space complexity

□ [C] 연속 부분합

□ [D] 용액

□ Linked List

□ [E] 스택

□ [F] 큐

□ [G] 요세푸스

□ [H] 키로거

§ Day 02 (Linked List & Hash)

□ [I] 등수 찾기

□ Hash

□ [K] 합이 0이 되는 쌍

⚠️ **GitHub.com Fallback** ⚠️

⚠️ GitHub.com Fallback ⚠️