Redddy's Devlog

🔈 문제 Implement the RandomizedSet class: RandomizedSet() Initializes the RandomizedSet object. bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise. bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise. int getRandom() Returns a random element from the curr..

개선된 ConcurrentHashMap ConcurrentHashMap 클래스는 동시성 친화적이며 최신 기술을 반영한 HashMap 버전이다. 내부 자료구조의 특정 부분만 잠궈 동시 추가, 갱신 작업을 허용한다. 떄문에 동기화된 Hashtable 버전에 비해 읽기 쓰기 연산 성능이 월등하다. 리듀스와 검색 ConcurrentHashMap은 스트림에서 봤던 녀석들과 비슷한 종류의 세 가지 새로운 연산을 제공한다. forEach: 각 (키, 값) 쌍에 주어진 액션을 실행 reduce: 모든 (키, 값) 쌍을 제공된 리듀스 함수를 이용해 결과로 합침 search: 널이 아닌 값을 반환할 때까지 각 (키, 값) 쌍에 함수를 적용 또 키, 값 그리고 Map.Entry 를 활용해서도 연산을 수행할 수 있는 메서드도..

🔈 문제 BOJ의 인기스타, 방송인 권욱제는 통신 회사에 취업했다. 현재 이 통신 회사는 너무나 큰 통신망을 한 지사에서 관리하느라 큰 비용을 지불하고 있었다. 그래서 회사는 최근 IT의 트렌드 중 하나인 '탈중앙화'에 편승하여, 통신망을 분할하도록 결정했다. 그래서 욱제한테 통신망을 분할 할때 발생하는 비용을 분석하도록 지시했다. 현재 회사 망에는 1번부터 N번까지 총 N개의 통신 탑이 존재하며, 통신탑 간의 연결이 M개 존재한다. 이때 회사에서는 총 Q번 통신탑 간의 연결을 제거함으로써 하나의 통신망을 여러 개의 통신망으로 분리하려고 한다. 통신망이란, 통신탑의 연결을 통해 도달 가능한 통신탑들의 집합이다. 통신탑 간의 연결 관계를 제거할 때 드는 비용은 제거한 후 통신망이 두 개로 나누어진다면 나눠..

서로소 집합 (Disjoint Sets) 서로소 집합은 공통 원소가 없는 두 집합을 의미한다. A = {1, 2} 와 B = {3, 4} 가 있다면 두 집합은 서로소 관계이다. 서로소 집합 자료구조란 서로소 부분들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조다. 서로소인지 판별하려면 union과 find 연산이 필요하다. union연산은 두 집합을 하나의 집합으로 합치는 연산이고 find 연산은 어떤 원소가 주어졌을 때 이 원소가 속한 집합의 대표를 찾는 연산이다. 즉 find 를 통해 주어진 두 집합의 대표를 비교하여 서로 서로소인지 확인이 가능 한 것이다. 때문에 서로소 집합 자료구조는 유니온파인드(Union-Find)라고도 불리운다. 집합 {1, 2, 3, 4, 5, 6}이 있고 여기에 un..

🔈 문제 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다. 매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 2..

🔈 문제 선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다. 함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 첫 번째 수를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다. 함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 수를 버리는 함수이다. 배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오. 📝입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 최대 100이다. 각 테스트..

재귀 함수(Recursive Function)란 자기 자신을 다시 호출하는 함수를 의미한다. 아래와 같은 함수가 재귀 함수이다. def recursive_function(): print("재귀 함수를 호출합니다.") recursive_function() recursive_function() 그러나 이 코드를 실행시킨다면 "재귀 함수를 호출합니다." 라는 문장을 출력하다가 어느 순간 에러를 내며 멈출 것이다. RecursionError: maximum recursion depth exceeded while calling a Python object 이 오류 메세지는 재귀의 최대 깊이를 초과했다는 내용이다. 보통 파이썬 인터프리터는 호출 횟수 제한이 있는데 그 한계를 벗어났기에 다음과 같은 메세지를 출력한 ..

a = [1,2,3,4,5,6,7,8,9,10] a 리스트에서 내가 8이라는 값의 위치를 찾는 방법은 여러가지이다. 그중에서 순차탐색과 이진탐색을 설명하겠다. 순차탐색 (Sequential Search) 순차탐색은 그냥 말그대로 처음부터 이게 8인지 아닌지 확인해가면서 찾는 것이다. 즉 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다. 만약 찾고자하는 데이터가 제일 끝에 있다면, 데이터 개수가 N일 때 최대 N번의 비교 연산을 수행함으로 최악의 경우 시간 복잡도는 O(N) 이다. 이진탐색 (Binary Search) 이진탐색은 절반씩 쪼개가면서 찾는 것이다. 이때 a list가 정렬되어 있어야만 사용가능하다. 1~10 의 데이터 중 8의 위치를 찾으려면 ..

● 스택을 사용한 문제 ● 그리고 - 가 입력됐을때 어떻게 처리할지가 키포인트 우선 입력이 들어오면 바로 리스트에 담지 않고 입력이 ,- 중에 있는지 먼저 체크하였다. 만약

우선순위 큐는 내부적으로 힙(heap)이라는 완전이진트리 Complete binary Tree로 되어 있다. 힙 트리의 루트 노드(root node)에는 데이터들 중에 가장 큰 값 혹은 가장 작은 값을 담게 되는데, 전자는 최대힙(max-heap), 후자는 최소힙(min-heap)이라 한다. 어떤 값을 넣어도 항상 루트에 가장 큰 값 또는 가장 작은 값이 위치하도록 자동으로 갱신한다. 이 과정이 꽤 효율적이라 우선순위 큐의 값 삽입/삭제 시간 복잡도는 O(log N)이다. 무작위 숫자들을 힙에 전부 넣고 하나씩 빼면 정렬된 결과를 얻을 수 있는데, 이게 힙정렬이다. from queue import PriorityQueue pq = PriorityQueue() pq.put(123) pq.put(789) p..