알고리즘4 바킹독 알고리즘 0x06강 큐 요약본 1. 큐는 한쪽 끝에서 원소를 넣고, 다른 쪽 끝에서 원소를 제거할 수 있는 자료구조이다. 2. 스택과 마찬가지로, 맨 앞과 맨 뒤가 아닌 원소의 확인/변경이 원칙적으로 불가하다. 3. 큐가 추가되는 곳을 rear 라 하고 큐가 제거되는 곳을 front 라 한다. 4. 배열로 큐를 구현한다고 했을 때, 큐를 구현하려면 1, 원소를 담을 충분히 큰 배열 2, 배열의 원소 중 rear 원소를 가리키는 head 변수, front 원소 + 1의 빈 공간을 가리키는 tail 변수 이렇게 세 가지가 필요하다. 처음에는 head 와 tail 이 같은 곳을 가리킨다. 5. 큐의 크기는 tail - head 로 쉽게 계산 가능하다. 6. 스택과는 달리 큐의 경우 삭제가 발생할 시, head 가 오른쪽으로 밀려나기 때문에.. 2023. 1. 31. 바킹독 알고리즘 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 다음
