노는 게 제일 좋아

두개의 큐를 쓰면 되지 않을까??? 생각이었지만 예외처리가 꽤나 까다로웠다. https://www.acmicpc.net/problem/7662 여러가지 방법이 있겠지만 나는 쉬운 방법으로 풀었다. MultiSet 자체가 무엇을 위해 만들어졌냐고 하면..? Set이라는 것이 집합이라 중복을 허용하지 않지만.. 이 친구는 key의 중복을 허용해서 유용하게 이 문제에 쓰였다. 중복이 허용되는 Set이라고 보면 된다. 자동정렬 + key,value 형태라고 보면 된다. #맞는 풀이 #include using namespace std; int tc; int main(){ cin>>tc; while(tc--){ int k; cin >> k; //1. ordered된 multi_set으로 중복도 포함된 set을 만들..

나의 좁은 식견에 안타까워하며 배운 상태 저장방법!! 행렬을 문자열로 문자열을 행렬로 변환하는 방법!! 행렬 자체를 저장하는 것이 메모리가 많이드므로 문자열로 저장하는 방법!!! 배울 것이 많은 문제다. https://www.acmicpc.net/problem/1525 #맞은 풀이 #include using namespace std; int dc[4] = {1,-1,0,0}; int dr[4] = {0,0,1,-1}; string start = ""; //상태를 문자열로 저장함 int answer = -1; //answer가 갱신되지 않는 것은 아무리 시도해도 만들 수 없는 것을 의미 int main(){ queue q; //string(상태), int(실행횟수) set check; //상태가 중복되는 ..

흥미로운 문제다. 실제로 최근 1달 이내... 최근 1년 이내.. 최근 5년 이내.. 를 가진 모든 데이터들을 이렇게 다룰 것만 같다. 그만큼 중요하지만 쉬운 문제라고 본다. 큐를 이용한다. https://www.acmicpc.net/problem/21921 #맞는 풀이 #include using namespace std; int N, X; int main(){ cin >> N >> X; queue q; int cnt = 0; int sum = 0; unordered_map number; int M = 0; while(N--){ int visit; cin >> visit; sum += visit; q.push(visit); cnt++; if(cnt>=X){ M = max(M,sum); number[sum..

구글링 + 학교 공부로 작성하였습니다. 피드백 맘껏 양껏 주세요 업데이트(22.06.01) 자료구조 별 접근, 삽입, 삭제, 탐색, 시간 **체크한 것들은 최악의 경우가 존재함( 사용자의 능력에 달림) ex) 해시테이블, BST 배열, 연결리스트 더보기 배열, 연결리스트, List [컴퓨터(Computer Science)/자료구조(Data Structure)] - 배열, 함수의 매개변수,주소,값,자료구조(2) [CS Interview] - C++ 에서의 자료구조 Array vs Linked List; 배열과 연결리스트 [프로그래밍언어(Programming Language)/C || C++] - 연결리스트, Linked List [CPP] [프로그래밍언어(Programming Language)/C || C..

DFS, BFS 알고리즘을 알아야 풀 수 있는 문제다. https://www.acmicpc.net/problem/17298 이것은 그냥 뭐 생각대로 하기 쉽지 않다. 해보려 했는데..인덱스가 저장이 안되어서 정말 힘들었다.그래서 pair를 쓸까 하다가.그냥 스택 2개를 썼다. 인덱스를 이용해야 한다라는 생각을 하면 어렵지만 생각할 수 있는 문제라고 한다.한 번에 생각하기는 확실히 힘든 것 같다. 다른 사람과 풀이를 비교하지 않는 이유는원리는 같아서 그렇다. #include #include #include #include using namespace std; stack num; // 숫자를 넣음 stack stk; // 인덱스를 넣음 int N; int arr[1000001]; void init(){ io..

해시태그라 불리는 # 그렇다면 해시 테이블은 뭔지 알까? 수많은 자료 구조들 중 하나로 속도가 빠른 자료구조로 알려져 있다. 한 번 알아보자 해시 테이블은 기본적으로 Key- Value 시스템을 가지고 있다. key는 value를 찾는 수단이고 우리가 찾는 것은 value이다. 사전을 생각해보면 쉽다. "배추" 의 정의는 배추를 찾아야 그 밑에 설명이 있다. 우리가 필요한 것은 배추라는 단어가 아니라 배추가 뭔지이다. 해시 테이블의 적합하지 않은 데이터들도 있다. 정렬된 데이터가 필요하거나, 멀티 미디어 데이터를 저장할 때 혹은 키의 길이가 길거나 가변적이어서 키에 대한 검색이 필요할 때 데이터의 키가 유일하지 않을 때 등이 있다. 해시 테이블은 O(1)의 시간복잡도를 가진다고 알려져 있다. ?? 딱봐도..

정의는 정점의 집합 V와 가중치를 갖는 간선의 집합 E로 구성된 그래프 G = 가 주어질 때, 모든 정점을 연결하고 연결된 에지의 가중치 합이 최소인 트리 T를 구하시오 다시 쉽게 말하면 최소 비용으로 모두를 잇는 방법이라고 볼 수 있다. 아래 그림을 보자 어떤 알고리즘에 의해 만들어졌을까? **이 아이디어는 Kruskal's Algorithm이라고도 부른다. 매 반복마다 최소 값을 꺼내기 때문에 Greedy라고도 부른다. 1. 그래프의 주어진 모든 간선을 최소힙(Min Heap) H 에 추가한다. 2. H로부터 간선, e을 하나 꺼낸다. 3. 해당 간선의 양 끝점이 T에 있는 경우 e 때문에 cycle이 발생할 수 있으니 e를 버리고 다시 2 단계로 돌아간다. 4. 해당 간선을 T, 트리에 추가시키고 ..

앞서 나온 자료구조보다 해시 테이블은 비교적 빠른 탐색 속도를 가지고 있다. 어떻게 그렇게 될 수 있는지 알아보고 어떤 자료를 표현하기에 적합한지 생각해보자 또한 여기선 lookup 이라는 용어를 알 수 있다. lookup은 조회로 해석되는데 특정 원소가 컨테이너에 있는지 확인하거나 컨테이너 키 값에 해당하는 value를 찾는 작업을 말한다. 단적으로 배열에선.. 어떠한 것이 있는지 알려면 O(N)의 시간이 걸린다. 왜냐하면 모든 것을 살펴봐야 하기 때문이다. 그렇다면 얘는 어떤 방식이길래 그것보다 빠를 수 있을지 생각해보자 앞서 배운 이진 탐색을 생각했다면 똑똑한 사람이다. [문제풀이(Problem Solving)/C++ 문제풀이에 유용한 것들] - 이진탐색, Binary Search 하지만 여기서 알..

[CS Interview] - 비선형 자료구조를 사용하는 이유 우리는 선형구조만으로 모든 것을 표현하지 못한다. 그래서 Tree를 그려내었고 Tree는 하나의 노드에서 다른 노드로 이동하는 경로가 하나만 존재하기 때문에 순환 또는 원형의 종속성을 표현할 수 없다. 때문에 우리는 또 다른 자료구조인 Graph를 구현하고자 한다. 즉, 노드 간의 더 자세한 경로의 표현을 하고싶다면 Tree 보다는 Graph가 더 적합한 자료구조라고 할 수 있다. Graph는 우선 노드에 대한 데이터를 가지고 있을 뿐만 아니라 노드 간의 간선 데이터도 가지고 있어야 한다. 즉, 해당 노드의 값과 해당 노드와 연결된 노드에 대한 정보를 가지고 있어야 한다는 것이다. edge, 간선은 무방향, 일방향 이 존재하고 해당 edge에..

우리가 흔히 보는 위와 같은 그림이 트리구조이다. 왜 Tree냐면 나무를 거꾸로 박아놓은 것처럼 생겼기 때문이다. 그래서 시작이 Root Node라고 부른다. 실제로 물론 한 노드에 여러가지 노드를 가질 수 있지만 우리는 이진 트리, Binary Tree라고 가정하고 진행한다. 각 노드는 자신의 밑에 있는 2개의 노드를 가리킨다. struct Node{ std::string data; node* first; node* second; }; 각 노드들은 자신의 하위 노드를 가리킨다. 즉, 이를 통해서 계층적 구조를 나타낼 수 있다. 트리구조를 처음 만들기 위해서는 Root Node가 필요하다. 해당 노드는 처음에 first와 second가 NULL이다. 내가 예전에 썼던 글이다. 내가 다시 쓰기보다 아래 글..