솔

https://www.acmicpc.net/problem/5430  뒤집기와 삭제(R과 D) 명령과 숫자 배열을 입력받은 뒤,명령에 따라 배열을 뒤집거나 삭제하는 문제이다.  이 문제를 보고 배열을 숫자만 입력받는게 아닌데 어떻게 처리해야하지?  라는 생각이 들었다. 생각을 하면서 두 가지 과정을 거치면 해결할 수 있을 것 같았다.1. 배열의 처음과 끝은 무조건 대괄호이므로 이를 먼저 제거한다.2. 문자열에서 쉼표를 찾아 쉼표 이전의 문자열을 숫자로 변환  아래 코드에서 tmp는 입력받은 배열을 저장한 string 이고, d는 int를 저장하는 deque이다.deque를 사용한 이유는 아래서. tmp = tmp.substr(1, tmp.size() - 2); //대괄호를 제거 size..

1.3 The Network Core1.3.1 Packet Switching- 메세지를 목적지로 보내기 위해, source에서는 긴 메세지를 packet이라 불리우는 작은 데이터 조각으로 나눈다. - 메세지가 전달되면서 각 패킷은 communication link 와 packet switch를 통해 이동한다.  주요 패킷 스위치 유형 -> router , link-layer switch - 패킷은 각 링크의 최대 속도로 전송된다. - 패킷의 크기와 링크에 따라 전송 시간이 결정된다. ex) 크기 Lbit, 속도 Rbit/sec -> 전송속도 == L/R sec  Store-and-Forward Transmission대부분의 packet switch는 링크를 입력할 때 store-and-forward tr..

1.1 What Is the Internet?- 인터넷이 무엇이냐는 질문이 들어왔을 때 기본 하드웨어와 소프트웨어 구성요소를 볼트와 너트에 비유할 수 있다.  - 또한, 우리는 각가의 계층에 서비스를 제공하하는 서비스라고도 할 수 있다.  1.1.1 A Nuts-and-Bolts Description-인터넷은 전세계의 수많은 computing device 들을 서로 이어주는 컴퓨터 네트워크이다. -얼마 전까지만 하더라도 이 computing devices라는 것들은 리눅스 작업환경이나 서버 등을 가리켰지만,   현재, 2025년에는 전세계 75%의 사람들이 인터넷을 사용할 것이라는 연구결과가 있을 정도로 많이 발전했다. - 게다가 이제는 원래 인터넷과 관련 없던 것들(안경이나 TV, 시계, 보안시스템 등..

이번에는 c++ 표준 라이브러리인 std::map, std::unordered_map 에 대해 알아보겠습니다. 라이브러리의 이름이 map 이라고 지어진 이유는 mapping 과 관련이 있기 때문입니다.  std::map (Ordered Map)map 은 BST (이진탐색트리) , RedBlackTree(레드블랙트리) 로 구현되어 있어서키의 순서가 자동으로 정렬되고O(log N) 을 기대할 수 있습니다. 또, 트리의 형태를 유지하기 위해 추가적인 메모리를 사용하지만 Unordered_mapd 에 비하면 적고,중복된 값은 허용하지 않습니다. ( 덮어쓰기 ) std::unordered_map (Unordered Map)unordered_map 은 해시테이블로 구현되어 있어서키의 순서가 정렬되지 않고평균적으로 ..

앞에서 AVL Tree와 RedBlackTree에 대해 알아보았는데요. 이번에는 두 트리를 비교해보겠습니다. https://sol248.tistory.com/61 AVL TreeAVL트리는 발명자의 이름인 Geory Adelson-Velsky and Evgeii LanDis을 따서 지어졌습니다. 스스로 균형을 맞추는 이진 탐색 트리여서 self-balancing binary search tree 라고 부르기도 합니다.  이진 트리에서, 데sol248.tistory.com https://sol248.tistory.com/64 RedBlackTree (레드-블랙 트리)레드블랙 트리는 스스로 균형을 잡는 이진트리 라는 점에서  앞에서 살펴본 AVL과 비슷합니다.https://sol248.tistory.com/..

레드블랙 트리는 스스로 균형을 잡는 이진트리 라는 점에서  앞에서 살펴본 AVL과 비슷합니다.https://sol248.tistory.com/61 AVL TreeAVL트리는 발명자의 이름인 Geory Adelson-Velsky and Evgeii LanDis을 따서 지어졌습니다. 스스로 균형을 맞추는 이진 탐색 트리여서 self-balancing binary search tree 라고 부르기도 합니다.  이진 트리에서, 데sol248.tistory.com 또한, 레드블랙 트리는 실제로 키값을 2개 가지진 않지만 2-3트리의 성질도 가지고 있습니다.https://sol248.tistory.com/63 2-3Tree (2-3트리)다음에 알아볼 레드블랙트리를 더 쉽게 이해하기 위해, 2-3트리에 대해 먼저 알..

다음에 알아볼 레드블랙트리를 더 쉽게 이해하기 위해, 2-3트리에 대해 먼저 알아보겠습니다. 2-3트리는 이진트리의 확장 버전입니다. 이진트리에서는, 한 노드가 하나의 키값을 가지고 최대 두개의 자식을 가질 수 있었습니다. 하지만 2-3트리에서는 한 노드가 두개의 키값을 가질 수 있고, 세개의 자식을 가질 수 있습니다. 이진트리에서는 leftChild , rightChild 이렇게 두개의 자식이 있었다면 2-3트리에서는 leftChild , midChild , rightChild 이렇게 세개의 자식을 가질 수 있다고 생각하면 됩니다. 2-3트리는 이진 트리와 비교했을 때 무슨 장점이 있을까요?  먼저,데이터 삽입의 예시를 살펴보겠습니다. 1. 데이터를 삽입할 때 키 값이 2개 있는 노드가 일시적으로 3개..

https://sol248.tistory.com/61 AVL TreeAVL트리는 발명자의 이름인 Geory Adelson-Velsky and Evgeii LanDis을 따서 지어졌습니다. 스스로 균형을 맞추는 이진 탐색 트리여서 self-balancing binary search tree 라고 부르기도 합니다.  이진 트리에서, 데sol248.tistory.com이전에 AVL트리의 특징과 구현하는 방법에 대해 알아보았습니다. 이번에는 AVL트리를 활용하여 간단한 영어사전을 만들어보겠습니다. AVL트리는 알아서 균형을 맞춰주는 트리 형태이기에  삽입, 삭제, 탐색의 시간 복잡도가 최악의 경우에도 O(log N) 이라는 장점이 있었죠. 마침 영어사전은 빠른 삽입, 빠른 삭제, 빠른 탐색이 요구되므로 한번 구..

AVL트리는 발명자의 이름인 Geory Adelson-Velsky and Evgeii LanDis을 따서 지어졌습니다. 스스로 균형을 맞추는 이진 탐색 트리여서 self-balancing binary search tree 라고 부르기도 합니다.  이진 트리에서, 데이터가 마치 연결리스트처럼 한줄로 쭉 나열되는 최악의 경우 트리의 이점을 살리지 못한다는 단점이 있었습니다바로 아래의 그림처럼 말이죠.  이런 일이 발생하지 않기 위해서는 데이터를 추가할 때 한쪽으로 몰리지 않게 조절해주는 기능이 필요합니다. 이것을 가능하게 한 것이 바로 AVL 트리 입니다. 먼저 이진탐색트리의 코드부터 보겠습니다. 이진탐색트리 클래스)연습을 위해 동일한 기능을 하는 함수를 재귀를 사용한 것과 사용하지 않은 것 둘다 구현했습니..

백준 1074번 문제입니다.    행렬에서 z모양으로 탐색하는 문제입니다. 이 문제는 입력받은 행(r)과 열(c)의 크기에 따라 위치를 판단할 수 있습니다. 위 행렬을 사분면 나누듯 4등분을 하며 재귀적으로 문제를 해결할 수 있을 것 같습니다. ( 입력받은 행과 열이 어디에 위치한지 찾고 또 4등분하고를 반복 )  코드)입력받은 행과 열이1.좌상단2.우상단3.좌하단4.우하단중 어디에 있는지 파악하고, 재귀를 이용하여 그 부분으로 다시한번 쪼개는 방식을 사용.(위치에 따라 return 할 떄 재귀함수에 더해지는 값이 달라지는 것 중요 -> 2의 거듭제곱을 이용하여 표현 가능)#include #include int Z(int n, int r, int c) { if (n == 0) return 0; int..