알고리즘12 바킹독 알고리즘 0x06강 큐 요약본 1. 큐는 한쪽 끝에서 원소를 넣고, 다른 쪽 끝에서 원소를 제거할 수 있는 자료구조이다. 2. 스택과 마찬가지로, 맨 앞과 맨 뒤가 아닌 원소의 확인/변경이 원칙적으로 불가하다. 3. 큐가 추가되는 곳을 rear 라 하고 큐가 제거되는 곳을 front 라 한다. 4. 배열로 큐를 구현한다고 했을 때, 큐를 구현하려면 1, 원소를 담을 충분히 큰 배열 2, 배열의 원소 중 rear 원소를 가리키는 head 변수, front 원소 + 1의 빈 공간을 가리키는 tail 변수 이렇게 세 가지가 필요하다. 처음에는 head 와 tail 이 같은 곳을 가리킨다. 5. 큐의 크기는 tail - head 로 쉽게 계산 가능하다. 6. 스택과는 달리 큐의 경우 삭제가 발생할 시, head 가 오른쪽으로 밀려나기 때문에.. 2023. 1. 31. 바킹독 알고리즘 0x05강 스택 요약본 1. 자료구조에서의 스택 한쪽 끝에서만 원소를 넣거나 뺄 수 있는 자료구조! (프링글스 통) 스택, 큐, 덱 모두 특정 위치에서만 원소를 넣거나 뺄 수 있으므로 Restricted Structure 라고 부름. 중요한 것은, 최상단이 아닌 원소들의 확인이나 변경이 원칙적으로는 불가하다는 것. 그래서 STL 에서도 제공하지 않음. 2. STL 에서 구현한 stack 주의할 점은, 빈 스택에서 pop 이나 top 을 호출하면 런타임 에러를 발생시킨다는 점! #include using namespace std; int main(void) { stack S; S.push(10); // 10 S.push(20); // 10 20 S.push(30); // 10 20 30 cout 2023. 1. 30. 바킹독 알고리즘 0x04강 연결 리스트 요약본 1. 배열에 비해서 cache hit rate 가 낮지만, 할당이 쉽다는 장점이 있다! 2. 배열과 연결 리스트의 차이를 잘 알아두자! 둘 다 선형 자료구조~@ 연결 리스트에서 추가적으로 필요한 공간은, 다음 요소의 주소를 저장하는 공간을 의미한다. 3. 텍스트 에디터가 연결 리스트를 쓰는 대표적인 경우! 4. 실무에서는 쓸 수 없으나 코테에서는 유리한 야매 연결 리스트!! (메모리 누수 때문에 현업에선 절대 사용 불가) (STL list 가 허용되지 않아 직접 구현해야 하는 경우에만 씀.) const int MX = 1000005; int dat[MX], pre[MX], nxt[MX]; // dat[i] 는 i 번지(번째 아님 주의) 원소의 값. pre[i] 는 i 번지 원소의 이전 원소의 인덱스 in.. 2023. 1. 30. 바킹독 알고리즘 0x03강 배열 요약본 1. 배열의 정의 메모리 상에 원소를 연속하게 배치한 자료구조 C++ 에서의 배열은, 한 번 배열의 길이를 선언하면 배열의 길이를 바꾸지 못하지만, 자료구조로써의 배열에서는 배열의 길이를 마음대로 늘리거나 줄일 수 있다. 2. 배열 === 책꽂이라고 생각하자. 책꽂이에 특정 책이 어디에 있는지는 책을 움직이지 않고도 확인 가능하고, 그 책을 다른 책으로 갈아끼우는 것도 1번이면 된다. 또 책을 책꽂이 끝에 추가하는 것도, 그 책만 가져다가 꽂으면 된다 마지막 책 제거도 마찬가지. 그러나 중간에 책을 끼워야 한다면, 책을 하나씩 옮겨야 된다. 책의 위치가 변하는 것이 평균적으로 n/2 이므로 시간 복잡도는 O(n)이 된다. 3. 배열 문제를 풀 때는 fill 함수를 사용 하는 것을 추천. 코드도 짧고 실수.. 2023. 1. 29. 바킹독 알고리즘 0x02강 기초 코드 작성 요령 2 요약본 1. C++ 에서 C 의 포인터 역할을 하는 것 == 참조자 참조자는 포인터에도 * 를 붙일 필요가 업시, 인자에만 & 를 붙여서 넘겨주면 그 뒤에는 그냥 지역 변수처럼 써도 되어서 편한 듯! 2. vector 는 크기가 정해져 있지 않은 가변 배열이며, vector 헤더에 선언되어 있다. 이처럼 개발자가 편하게 사용할 수 있는 다양한 알고리즘과 자료구조가 저장되어 있는 라이브러리를 Standard Template Library 줄여서 STL 이라고 한다. vector 역시 STL 에 구현된 자료구조. Vector 의 경우 배열이긴 하지만, 구조체처럼, 함수 인자로 보낼 경우 원본에 영향을 줄 수 없다. STL을 함수 인자로 넘길 경우 생길 수 있는 또 다른 단점! 복사본을 만들기 때문에, 그에 따른 비.. 2023. 1. 27. 바킹독 알고리즘 0x01강 기초 코드 작성 요령 1 요약본 시간, 공간 복잡도 먼저 시간 복잡도라 함은, 컴퓨터가 연산을 하는데 걸리는 대략적인 시간. 정확한 시간을 구하기 힘들기 때문에, Big O notation 을 이용하여 n 에 비례한다. lg n 에 비례한다. 등 그 식에서 가장 큰 값을 가지는 항에 비례한 시간이 걸린다고 생각. n 의 크기에 따른 허용 시간복잡도. 절대적인 것은 아니나, 이 정도 시간대로 처리하는 것이 유리하다는 느낌은 가지고 있어야 함. 중요! 문제를 풀 때, 무턱대고 풀 게 아니라, 제한 시간내에 풀 수 있는 풀이인가? 를 생각해야 함. 다음으로 공간복잡도라 함은, 연산하는데 필요한 메모리 공간의 크기. 코테에서는 고려할 필요가 거의 없고, 메모리 제한이 512 MB 일 때 int 변수를 약 1.2억개 선언할 수 있다는 것을 알아.. 2023. 1. 26. 이전 1 2 다음
