LAZINESS

딱히 정리할 건 없음 괄호가 있는 식에서 괄호가 제대로 짝지어져 있는지 확인하는 법 ) 의 개수가 ( 의 개수를 넘으면 안됨 < 이건 굳이 코드에서 확인 할 필요는 없음 ( 이 괄호를 죄다 스택에 집어넣고 ) 이 괄호가 나오면 하나씩 뽑으면서 짝을 맞춤 식이 모두 끝났을 때 스택도 비어있고 ) 이 괄호도 없으면 맞는 식이고 스택이 비어있지 않거나 ) 이 괄호가 남으면 틀린 식임 !

stl vector에서 제공해주는 기능을 stl deque에서도 대부분 제공 +push_front 앞쪽에서의 추가 제거가 필요하지 않으면 굳이 deque 쓸 필요 없음 배열로 구현하는 덱 #include using namespace std; const int MX = 1000005; int dat[2 * MX + 1]; int head = MX, tail = MX; // 앞으로도 뒤로도 확장 가능해야 하기 때문에 인덱스의 초기값을 중간으로 세팅함 // head 는 맨 앞의 원소를 가리키고 tail은 맨 뒤의 원소 하나 뒤를 가리킴 void push_front(int x) { // 아니 암만 정신 없을 때 풀었어도 그렇지 이게 뭐니 // dat[head--]; dat[--head] = x; } void p..

원소를 담을 배열이랑 HEAD , TAIL head = index / tail = end 큐를 배열로 구현하면 앞쪽에 자꾸 빈 자리가 생김 이를 해결하기 위해 head나 tail이 배열의 끝이면 다시 배열의 처음으로 돌아오도록 하면 됨 = > 원형 큐 코테에서는 어차피 oush 최대 횟수가 정해져 있어서 배열을 엄청 크게 만들어서 원형큐를 사용하지 않을 수 있음 배열로 구현한 큐 #include using namespace std; const int MX = 1000005; int dat[MX]; int head = 0, tail = 0; void push(int x) { dat[tail] = x; tail++; } void pop() { // 이거 아님 tail--; head++; } int front..

restricted structure - 스택 큐 덱 등 특정 위치에서만 원소를 넣거나 뺄 수 있음 원소 추가 제거가 모두 O(1) 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 배열로 구현하는 경우 int data[] & int index 만 있으면 됨 #include using namespace std; const int MX = 1000005; int dat[MX]; int pos = 0; void push(int x) { dat[pos++] = x; } void pop() { pos--; } int top() { return dat[pos-1]; } void test() { push(5); push(4); push(3); cout

연결리스트 원소를 저장 할 때에 다음 원소의 주소를 함께 저장 메모리 상에는 여기저기 흩어져있음 성질 1. k번째 원소를 찾기 위해 O(k)의 시간이 필요 2. 임의의 위치에 원소를 추가/제거가 O(1) 3. Cache Hit Rate가 낮지만 할당이 쉬움 종류 1. 단일 연결리스트 다음 원소의 주소를 들고잇음 2. 이중 연결리스트 다음 원소와 이전 원소의 주소를 모두 들고잇음 3. 원형 연결리스트 끝이 처음과 이어져 있음 원을 이루는 리스트는 이중일수도 있고 단일일수도 있음 stl에 있는 list 는 이중 연결 리스트 배열과 연결리스트는 모두 선형 자료구조 야매 연결리스트 #include using namespace std; const int MX = 1000005; int dat[MX], pre[MX..

배열 메모리 상에 원소를 연속하게 배치한 자료구조 배열의 성질 - O(1)의 시간 복잡도로 k번째 위치를 확인/변경가능 - 추가적으로 소모되는 메모리의 양이 거의 없음 - cache Hit Rate가 높음 - 연속적인 구간을 잡아야 해서 할당에 제약이 걸림 꿀팁 전체를 같은 값으로 초기화 1. memset - 0이나 -1이 아닌 다른 값을 넣으면 오동작 2차원배열에서 오동작 등등 ex ) memset(a, 0, sizeof a); 비추 ! 2. for - 실수 없이 무난 3. fill - 실수 여지 별로 없고 코드도 짧음 algorithm 헤더 ex ) fill(a, a+21, 0); vector 배열과 마찬가지로 메모리상의 연속적인 공간에 존재 크기가 변함 vector 순회 1, range based ..

강의에서 기억해두면 좋을 것들 캡쳐 해옴 ! 출처 : https://blog.encrypted.gg/922 int 최대는 21억 함수의 인자 - int : 값이 복사돼서 넘어감 => 원본에 영향 안 줌 - 배열 : 배열의 이름은 배열의 주소를 담고있기 때문에 변경이 이루어지면 원본에 영향을 줌 - 구조체 : int와 마찬가지로 값이 복사되기 때문에 원본에 영향 안 줌 - stl : 구조체와 비슷하게 함수 인자로 실어보낼 경우 복사본을 보내기때문에 원본에 영향 안 줌 - 포인터 & 레퍼런스 : 원본에 영향을 줌 ! endl 쓰지마

- https://www.acmicpc.net/problem/3986 3986번: 좋은 단어 이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 www.acmicpc.net [ 3986 ] 좋은 단어 이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 깨고 말았다. 안타깝게도 자는 동안 키보드가 잘못 눌려서 보고서의 모든 글자가 A와 B로 바뀌어 버렸다! 그래서 평석이는 보고서 작성을 때려치우고 보고서에서 '..