전체 글199 백준 10866 문제 이해 코드 cpp 파일 // 전처리 단계(컴파일되기 이전 단계에서 실행됨) #include #include "baekjoon.h"; using namespace std; const int MX = 100005; int dat[MX*2+1]; int head = MX; int tail = MX; // 구현부 void push_front(int val) { dat[head--] = val; } void push_back(int val) { dat[++tail] = val; } // C++도 C의 절차지향적 특성을 가지고 있기 때문에 // 순차적으로 코드를 빌드하는 과정에서 없는 함수를 호출하려고 하면 문제가 생김 // 그래서 선언부를 먼저 정의하고 구현부는 순서 상관없이 두어도 문제없이 실행됨 int .. 2024. 2. 5. 덱(Double Ended Queue) 덱의 정의 양쪽 끝에서 삽입과 삭제가 가능한 자료구조 삽입, 삭제, 제일 앞/뒤의 원소 확인이 모두 O(1) 시간복잡도를 가지고 있다. 제일 앞/뒤가 아닌 원소들의 확인/변경이 불가능하지만 STL Deque에서는 인덱스로 원소에 접근할 수 있다. 구현 방법 스택이나 큐처럼 배열 또는 연결 리스트로 구현할 수 있지만 배열을 이용하는 게 쉽기 때문에 배열로 구현을 했다. 원소를 담을 배열 앞쪽과 뒤쪽을 가리킬 변수 2개 초기값이 0이 아니라 설정한 배열 크기의 중간값으로 잡는다. 왜냐하면 큐에서는 배열의 앞쪽에서는 제거만 발생하고 뒤쪽에서 삽입되는 형태이기 때문에 원소들이 차지하는 공간이 오른쪽으로 이동하면서 확장되지만, 덱에서는 양쪽으로 이동하면서 확장되기 때문에 초기값을 0으로 잡거나 배열의 최대 크기로.. 2024. 2. 4. 큐(Queue) 큐의 정의 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조로 먼저 들어간 원소가 먼저 나오게 되는 FIFO의 구조 연산의 시간복잡도는 스택과 마찬가지로 추가와 제거가 모두 O(1)이고, 제일 앞/뒤의 원소 확인도 O(1)이다. 큐라는 자료구조는 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 불가능하지만, 배열을 가지고 만들 때 해당 기능이 가능하도록 구현을 할 수 있다. STL Queue에서는 중간 지점의 원소들을 확인/변경이 불가능하다. 구현 방법 배열이나 연결 리스트 둘 중 어느것을 이용해도 구현하는데 문제는 없지만 배열을 이용한 방식이 더 쉽기 때문에 배열로 구현해보기 원소를 담은 배열 큐의 앞쪽(head)과 뒤쪽(tail)을 가리킬 변수 2개 배열의 인덱스가 0부터 시작하기 .. 2024. 2. 3. 스택(Stack) 스택이란? 후입선출(LIFO)의 자료구조로 재귀함수가 동작하는 방식과 비슷하다. 프링글스 통과 비슷하게 맨 아래에 있는 감자칩을 먹기 위해서 맨 위에 있는 감자칩부터 순서대로 먹어야 됨 스택은 배열 또는 연결리스트로 구현 할 수 있지만 보통은 배열로 구현을 한다. 스택이 top에서만 삽입과 삭제가 일어나기 때문에 맨 아래쪽에 있는 데이터는 맨 마지막에 삭제된다. 재귀함수도 처음으로 호출 한 함수가 먼저 종료되지 않고 호출 한 함수안의 마지막 재귀함수의 실행이 종료되고 순차적으로 그 다음 재귀함수가 종료되야지 처음으로 호출한 재귀함수가 종료된다. 스택 구현과 STL 사용법 #include #include using namespace std; const int MX = 1000005; int dat[MX];.. 2024. 2. 2. 싱글톤 패턴 적용 싱글톤 패턴이란? 단 하나의 유일한 인스턴스를 만들기 위한 디자인 패턴이며, 메모리 절약을 위해 인스턴스를 매번 새로 만들지 않고 초기에 하나의 인스턴스만 만든 후 재사용하는 방식이다. 해당 인스턴스가 빈번하게 사용되는 경우에 싱글톤 패턴을 적용하면 좋다. 예시를 들자면, Cat 인스턴스에서 어떠한 이벤트가 일어났을 때 GameManger 인스턴스가 처리를 하는데 게임이 시작되는 동안 Cat 인스턴스는 여러 개 생성되는데 그 처리를 담당하는 GameManger 인스턴스도 여러 개 생성된다면 수백 개, 수천 개의 Cat 인스턴스가 생성되는 경우 그에 따라서 GameManger 인스턴스도 많아지기 때문에 리소스를 많이 잡아먹게 된다. 그래서 전역으로 사용되는 인스턴스를 하나 만들고 각각의 Cat 오브젝트에서.. 2024. 2. 2. 백준 1806 1.문제이해 요약 : 길이 N의 수열의 연속된 수들의 부분합에서 그 합이 S 이상이 되면서 가장 짧은 부분합 길이를 출력 ex) N = {5, 10, 7, 4} 이고 S=15 일때, 5 + 10 or 10 + 7 + 4의 부분합을 구할 수 있음 연속된 수들이기 때문에 부분합은 두 개 이상의 연속된 수로 이루어져야 함 2.문제분석 S이상이 되는 부분합을 체크하고 그 부분합의 길이가 가장 짧은 부분합 길이(minLength)라면 해당 길이로 변경 로직 1. st, en 두 개의 커서를 배열의 시작 지점부터 한 칸씩 오른쪽으로 늘리면서 2개 이상의 수의 부분합으로 이루어져 있는가? 2. 부분합이 S 이상인가? 2.1. S이상이라면 부분합의 길이가 minLength 작은가? 2.1.1. minLength 보다 .. 2024. 2. 1. 이전 1 ··· 7 8 9 10 11 12 13 ··· 34 다음
