전공/알고리즘(algorithm)

https://www.acmicpc.net/problem/10816 ⊙ 문제 주어진 N개의 수들에서 M개 수들의 개수를 출력하는 문제이다. ⊙ 문제 접근 과정 처음 시도에서 주어진 N개 수들을 하나의 배열에 넣고, 주어진 M개 수들을 하나의 배열에 넣어 lower_bound를 직접 함수로 구현하였는데, 잘못 구현하여 오류가 났다. 런타임 오류(segdefault), 시간초과, 틀림 오류가 났고, 두번째 시도로 인터넷에 찾아봐서 unordered_map 자료구조를 사용하여 O(1) 의 시간 안에 찾을 수 있게 구현했다. 세번째 시도로 upper_bound, lower_bound STL을 이용해 풀었다. 또한 추가로 두 함수를 직접 구현해봤다. ⊙ 문제 풀이 //첫번째 시도 - 틀린 부분이 있습니다. #in..

1.우선순위 큐 큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조이다. 우선순위 큐(Priority Queue)는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다. 우선순위 큐는 일반적으로 힙(Heap)을 이용하여 구현한다. 힙(Heap)은 우선순위 큐를 위해 고안된 완전이진트리 형태의 자료구조이다. 최대 힙 (Max Heap)❝ key(부모노드) ≥ key(자식노드) ❞ 부모 노드의 키 값이 자식 노드보다 크거나 같은 완전이진트리이다. 최소 힙 (Min Heap)❝ key(부모노드) ≥ key(자식노드) ❞ 부모 노드의 키 값이 자식 노드보다 작거나 같은 완전이진트리이다. 2.우선순위 큐 구현방법 ..

https://www.acmicpc.net/problem/5430 ⊙ 문제 테스트케이스 개수 T에 대해 각 테스트케이스마다 수행할 함수 p, 배열에 들어있는 수의 개수 n, [x1,...,xn] 과 같은 형태로 배열에 들어있는 정수가 주어진다. 각 테스트 케이스에 대해서, 정수배열에 대해 함수를 수행한 결과를 출력하고, 빈 배열에 대해서 D를 수행할 경우 error를 출력한다. 이때, 정수배열에 대해 함수를 수행한 결과는 다음 규칙을 따른다. 함수 p는 'D'와 'R' 문자의 혼합 문자열이다. D에 대해서는 정수 배열의 맨 왼쪽 원소를 삭제하고, R에 대해서는 정수 배열을 reverse 시킨다. (예 : 1,2,3,4 -> 4,3,2,1 ) ⊙ 문제 접근 과정 첫 시도 deque를 사용하지 않고, 그냥 ..

덱(Deque)은 double-ended queue의 줄임말로서 큐의 전단(front)와 후단(rear)에서 모두 삽입과 삭제가 가능한 큐를 의미한다 배열을 이용한 원형 덱의 구현 : 배열을 이용한 원형 덱의 동작은 원형 큐에서와 거의 비슷하다. 덱은 좀 특별한 형태의 큐로 볼 수 있으므로 CircularQueue 클래스를 상속해서 CircularDeque 클래스를 만들자. //1CircularDeque.h #include "1CircularQueue.h" class CircularDeque : public CircularQueue { public: CircularDeque() {}; void addRear(int val) { enqueue(val); } int deleteFront() { return ..

https://www.acmicpc.net/problem/1966 priority queue 문제이다 풀이 1(내 풀이) - 우선순위 큐 이용x PriorityQueue STL을 사용하지 않고 직접 구현하였다. 내 생각엔 STL을 사용하여 이보다 간단하게 풀이할 수 있는 방법이 있는 것 같다 디버깅이 중단점에 적중이 되지 않는 문제가 있었는데, 이를 F11 (Step Out) 키를 사용하여 해결하였다 아래 코드에선, priorityQueue 함수를 이용해 M 번째 인덱스의 출력시점의 횟수를 구한다 #include #include #include using namespace std; int priorityQueue(int n, int m) { int answer = 0;//출력 int wonder = m;..

예지 출력은 잘 나왔는데, 계속 '시간초과' 오류가 났다. '시간초과' 오류가 난 코드는 풀이1 이다. 풀이1(내 풀이) 풀이1에서 queue 의 rear와 front 정의, Dequeue() 함수의 정의를 내맘대로 바꾸었다. #include #include #include using namespace std; class Queue { public: int N; int K; int front, rear; int* data; // Removed initialization here public: Queue(int n, int k) { K = k; N = n + 1; front = rear = 0; data = new int[N]; // Initialize data array after setting N } ..

아래 내용들은 'c++로 쉽게 풀어쓴 자료구조 (천인국,최영규)' 책을 읽으며 개인적으로 공부하며 정리한 것입니다. 잘못된 점이 있으면 고치겠습니다. Chapter03 Queue (큐) Queue (큐) : 선입선출(FIFO : first in first out) 의 접근 방법을 유지하는 요소들의 모음 기능 enqueue(e) : 주어진 요소 e를 큐의 맨 위에 추가한다. dequeue() : 큐가 비어있지 않으면 맨 앞 요소를 삭제하고 반환한다 isEmpty() : 큐가 비어있으면 true를 아니면 false를 반환한다 peek() : 큐가 비어있지 않으면 맨 앞에 있는 요소를 삭제하지 않고 반환한다 ifFull() : 큐가 가득 차 있으면 true를 아니면 false를 반환한다 size() : 큐 내..

https://www.acmicpc.net/problem/1918 후위표기식 중위 표기법(infix notation) : 연산자가 피연산자들 사이에 위치 후위 표기법(postfix notation) : 연산자가 피연산자들 뒤에 위치 중위 표현식 -> 후위 표현식 현재 연산자보다 우선순위가 높거나 같은 연산자는 모두 출력한 후(ex. * > + ) 현재 연산자를 스택에 넣는다. ** 괄호를 포함한 중위 표현식 -> 후위 표현식의 경우 왼쪽 괄호 ( 는 우선순위가 가장 낮은 연산자, 왼쪽 괄호 ( 와 오른쪽 괄호 ) 가 만나면 없어짐 풀이1 (내풀이) 세부적으로 케이스를 나눠야하는데 까다로움. (결국 인터넷 참고해서 작성함 https://charles098.tistory.com/10) 피연산자는 순서대로 출..