본문 바로가기

분류 전체보기

 (82)
이진 검색 트리(Binary Search Tree, priorty queue, set, map) Balanced BST(균형이 맞춰져 있는 이진 검색 트리)는 c++에서 heap(priorty queue)와 set으로 구현되어 있고, java에서는 tree set, python에서는 set, dict, tree set 등이 있다. 이진 검색 트리(Binary Search Tree, BST) 바이너리 서치가 중앙값보다 작으면 왼쪽 크면 오른쪽으로 이동했으니깐 똑같은 원리로 이루어진 트리 하지만 이진검색트리 만으로는 균형이 잡혀 있지 않기 때문에 최악의 경우 검색, 삽입, 삭제가 O(N)이 걸린다. 그래서 실제로 BST를 사용하지 않는다. 추가, 삭제, 검색이 O(N)이 걸리기 배열을 사용하겠다,, //이진 검색 트리는 매우 중요한 알고리즘이지만 BST를 구현하는 문제는 거의 없다. 고로 균형이 맞춰져..
유니온 파인드[Union Find] 유니온 파인드(Union Find) 그래프 알고리즘의 일종으로서 서로소 집합, 상호 배타적 집합(Disjoint-set)이라고도 한다. 알고리즘 문제 풀이에서는 주로 집합을 나타내며 합집합만 사용할 때 쓰인다. 여러 노드가 존재할 때, 선택한 두 노드를 같은 그래프로 합치거나 서로 같은 그래프에 속하는지 판별하는 알고리즘이다. Parent[x] : x의 부모 노드 Find : x가 속한 집합의 root 노드를 반환하는 연산 Union : x와 y가 포함되어 있는 집합을 합치는 연산 Parent 초기화 vector parent(n); for (int i = 0; i 부모 자식 관계는 중요하지 않음(단지 유니온 연산을 하다가 나온것) -> 하나로 묶여 있다는것이 중요함. -> 가장 중요한것은 루트. 최종 루..
스택 중간난이도 문제 풀이(Stack PS) 스택 가장 큰 특징 : LIFO 마지막에 넣은 게 가장 먼저 나온다 문제를 풀이하면서 가장 중요한 건 스택을 어떤 용도로 사용하고. 어떤 경우에 push를 하고, 어떤 경우에 pop을 해야 할까? 를 생각해야 된다. 문제풀이 9935 문자열 폭팔 : https://www.acmicpc.net/problem/9935 가장 쉽게 생각하는 방법 : 배열에 문자를 저장해서 폭발이 없을 때까지 포문 돌리기 O(N*N), N = 백만이므로 불가능 stack 사용 -> 문자열이 폭파하였을 때, 폭파 가능한 이전 문자열을 O(1)만에 찾을 수 있다. (서로 다른 문자 이므로 가능, 중복이 될 경우 첫 번째 문자인지 마지막 문자인지 구별이 안됨에 따라서 스택 알고리즘 적용이 어렵다.) 폭파 대상을 저장하는 stack 1..
[IT Review] 코로나19 이후 부의 미래에 대한 생각과 관련 해외 기사들 코로나19 이후에 역사상 가장 큰 부의 이동이 예상된다. 항공, 여행과 관광, 호텔, 컨벤션 이벤트, 스포츠, 예식장, 장례식장, 학교와 학원, 쇼핑몰, 백화점, 마트 같은 곳에서 다른 곳으로 이동하고 있다. 개인에게도 부의 이동 기회가 있다. 거대한 부의 이동이 마지막으로 폭발할 곳은 온라인이다. 내가 아는 것을 공유하고 가치를 창출하는 콘텐츠로 부의 일부를 자신에게 이동시켜야 한다. 현재 WEB2.0(모바일)에서 WEB3.0(메타버스)으로 이동하면서 정보의 탈중앙화가 가속되고 있다. 기업이 생산하고 이용자가 소비하는 패턴에서 이용자가 생산하고 소비하는 패턴으로 이동하는 것이다. 이는 콘텐츠의 탈중앙화에 크리에이터 이코노미가 붙어져서 더욱 활발해지고 있다. 현재 이용자들이 콘텐츠를 만들어 내는 것들은 ..
[서평]너무 놀라운 작은 뇌세포 이야기[The Angel and The Assassin] - 도나 잭슨 나카자와 이 책은 우울증을 포함한 마음의 병을 (정신과학, 심리학, 문명사와 사회학이 아닌) 해부학, 생물학, 진화학적 측면 즉, 뉴런, 시냅스, 미세아교세포의 관점에서 연구한 결과들을 풀이한 책이다. 뇌건강에 요인을 주는 다양한 외부&내부적 요인을 여러 가지 설명하며 현대 사회에서 뇌건강에 악영향을 주는 스트레스 요인들(소셜미디어 문화 중독 등)에 관하여 알려주고 있다. 육체의 병과 다르게 마음의 병에 걸린 사람은 다른사람에게 이해받지 못하고 "겨우 그런 것 때문에 우울해?"라는 말을 듣기 십상이다. '마음의 상처를 입은 순간에 시간이 멈춰서 영원히 회복되지 않을 것만 같다'라는 이들의 고통을 우리는 쉽게 상상 할 수 없다. 예전부터 심신이원론에 따라서 '마음과 몸은 별개이다', '뇌는 면역장기가 아니다'라는 ..
브루트 포스[4]:두포인터, 중간에서 만나기 (Brute Force[4]:Two Pointers, Meet in the Middle(MITM)) 브루트 포스(brute force) 이러한 브루트 포스방법 중에서 투포인터, 중간에서 만나기에 관해서 소개를 하려고 한다. 두 포인터(Two Pointers) 배열에서 전체의 경우의 수를 반복문을 통해서 찾는 것이 아니라 두개의 포인터를 조작하여 원하는 결과를 얻는 방법이다. 여기서 두개의 포인터를 이용하여 기존보다 시간복잡도가 줄어드는 구조를 만들 수 있다. 두 포인터 예제 2003 - 수들의 합2 https://www.acmicpc.net/problem/2003 A[i]+...+A[j] = M이 되는 i,j 쌍의 개수를 찾는 문제와 같다. 가장 기본적으로 생각 할 수 있는 방법은 반복문을 만드는 것이다. 반복문으로 i와 j를 선택하고 i부터 j까지의 합을 구한다. (i선택 x j선택 x 합더하기 = ..
[서평]상식 밖의 경제학(Predictably Irrational) - Dan Ariely 난 지금 까지 나를 잘 알고 있다고 생각했고, 이성적이라고 생각했다. 하지만 이 책을 읽고 나서 나는 비이성적인 존재고, 단지 이성적이고 싶다는 욕망만 있다는 걸 알게 되었다. 이 책은 이성적인 표준 경제학과 다른 행동경제학으로서 "사람은 여러 가지 비이성적인 행동을 반복하며 이러한 비이성적인 행동들은 체계적이며 예측 가능하다"라는 많은 사례를 알려준다. 하지만 비이성적으로 행동하는 시점에서 비이성적인 행동을 인지하면 결정을 내리는 데 좀 더 주의를 기울이고, 그 결정을 다른 각도로 생각해 볼 수 있다. 나의 다양한 비이성적인 행동과 결정 : 내가 좋아하는 사람들에게 얻은 정보를 과신뢰 하는 경험이 많다. //이를 반성하고 내 추론을 남에게 맡기지 말고 직접 추론하여 결론을 내자. 완벽주의적인 성격과 강..
이분탐색 문제 풀이[Binary Seach PS] 1. 이분탐색 문제 푸는 방법 2. 이분탐색 문제 풀이 1. 이분탐색 문제 푸는 방법 이분탐색을 이용하여 풀 수 있는 문제는 어떤 유형이고 문제를 해결하기 위해서는 어떻게 이분탐색을 이용할까? -> 정답을 구할 수 없지만, X가 가능한지 아닌지 알아내는 것은 가능한 문제들이 있다. 1. 정답을 구하는 문제(최적해 문제) A에서 B까지 가는 가장 빠른 시간을 구하는 것 2. 가능한지 살펴보는 문제(Yes/No 문제) A에서 B까지 X라는 시간으로 이동할 수 있나? 1.를 풀 수 있으면 2 또한 풀 수 있다. 2를 풀 수 있을때, 1을 풀 수 있을까? 풀 수 있다. X라는 시간에 작은 것부터 순서대로 대입하면 No가 계속 나오다. Yes가 나오는 시점이 해가 된다. =어느 한 기점을 기준으로 yes와 no가..

티스토리툴바