자료구조6

• 

  [c++] 백준 - 1655 가운데를 말해요(우선순위 큐) 1. 문제 2. 입력 및 출력 3. 문제 해설 priority_queue를 적절히 사용하여 중간값을 찾아내면 되는 문제였다. 우선 중간값을 찾아야한다는 점에서 pq가 두 가지가 필요하다는 것을 알 수 있었다. 우리는 최대힙과 최소힙을 각각 하나씩 선언하여 중간을 찾아내면 된다. 그런데 문제에서 만약 짝수개가 들어갔을 경우에는 더 작은 값을 찾아내라 했으니 정답은 최대 힙에 들어있을 수 있을 것이다. 왜냐하면 pq에서 접근할 수 있고 의미가 있는 값은 pq.top()에 해당하는 부분이다. top()이 항상 답이 되게 하려면 우리는 다음과 같이 pq를 구성해야한다. 만약 1 5 2 10 이라는 수열을 기준으로 봤을 때 정렬을 하면 1 2 5 10이 되고 이 기준에서 중간값은 2에 해당한다. pq.top()이.. c++/알고리즘 2023. 2. 16.

• 

  [c++] 백준 - 달리기 (인덱스드 트리) 1. 문제 2. 입출력 3. 예제 입출력 4. 문제 해설 처음에 이 문제를 읽었을 때는 왜 플래티넘 4인가 했다. 단순히 자신보다 앞에 있는 수 중 자신보다 큰 수의 숫자를 구하면 되는 것이 아닌가?라는 생각이 들었다. 그런데 문제 조건을 확인하니 선수의 수 N은 최대가 500000이고 만약 위의 방법을 적용하면 대략 O(N^2)의 시간복잡도를 갖게 된다. 500000 * 5000000 = 25000000000000 = 20조의 연산 횟수가 늘어나고 만약 break문을 통해 중간중간 가지치기를 해준다해도 시간 제한이 1초라는 것은 대략 1억번의 연산안에 결과가 나와야하는 것인데 O(N^2)알고리즘으로는 불가능하다는 생각이 들었다. 가능한 시간 복잡도는 O(NlogN)정도였다. 결국 알고리즘 분류를 봐버렸.. c++/알고리즘 2023. 2. 3.

• DoubleLinkedList 예전 자료구조 시간에 했던 과제들을 복기하며 다시 자료구조와 알고리즘에 대한 이해를 남겨보기로 했다. 그 중 자료구조에서는 Double Linked List라는 구조가 존재한다. Double Linked List란 양방향으로 연결 되어 있는 리스트로써 각 노드들이 양 방향으로 이어지는 구조를 가진다. 그러면 우리는 이 구조에서 몇 가지의 데이터를 신경써야할까 내가 프로그래밍을 하면서 느낀 점은 프로그래밍은 결국 데이터의 관리, 엔터티의 속성의 관리를 하는 일이다. 노드들이 양방향으로 연결되어 있으니 우리는 우선 노드라는 타입을 만들어야한다. #ifndef DLINKEDLIST_H #define DLINKEDLiST_H #include using namespace std; // 12171800 심정호 ty.. c++ 2022. 3. 13.

• 

  타입스크립트 stack <generic> ver { interface Stack{ // generic 선언은 interface, type, class 의 선언부에 행한다. readonly size: number; push(value : T) : void; pop() : T; } type StackNode = { readonly value : T; readonly next?: StackNode; } class StackImpl implements Stack{ private _size : number = 0; private head? : StackNode; get size() { return this._size; } push(value : T ) { const node : StackNode = {value,next: this.head}; this.head.. 카테고리 없음 2021. 7. 29.

• 

  타입스크립트로 stack 구현하기 { //Linked list 기반 stack interface stack{ readonly size : number; push(value : string) : void; pop() : string; } type node = { nextNode? : node; prevNode? : node; str : string; } class Stack implements stack { private Head? : node; private Tail? : node; private size1 : number = 0; // getter와 이름이 겹치면 안됨 get size() { return this.size1; } push(str : string) { const temp : node = {str}; if(this.size.. front-end/JavaScript, TypeScript 2021. 7. 28.

• 자료구조 stack을 이용한 문제 풀이 1(postfix) 우리는 후위표기식에 대해 알아볼 것이다. 후위 표기식이란 컴퓨터가 알아보기 쉽게 하는 표기 방식으로 우리가 흔히 연산을 표시하는 표시 방법인 중위 표기식과는 사뭇 다르게 생겼다. 예를 들어 중위 표기식에서 3+5 와 같은 식을 후위 표기식으로 표시하게 되면 3,5+와 같이 표기된다. 좀 더 복잡한 중위 표기식 예를 들면 A+B-C*D와 같은 경우에서는 연산 우선 순위가 *가 가장 높으므로 이것부터 처리해준다. A+B-CD* -> AB+-CD*>AB+CD*- 와 같이 변하게 된다. 이것이 후위 표기법이다. 몇 가지의 예시를 더 살펴보겠다. 1. A+B*C -> A+BC* 2. A*B-C -> AB*-C -> AB*C- 이와 같이 컴퓨터는 순서대로 읽으므로 컴퓨터가 읽기 쉽도록 표기법을 수정하는 것이다. ​.. c++ 2021. 6. 18.