본문 바로가기

분류 전체보기

 (231)
[코드트리] Tree Set SW중심대학 사업단에서 CodeTree와 함께 실시한 코딩테스트 대비 캠프에 참여하여 공부한 내용을 정리하였습니다. * 참고 : python과 c++, java 등 언어별로 설명이 다른 부분 존재! 필자는 c++ 사용. set STL C++에서는 set이라는 STL을 이용할 수 있습니다. set은 TreeSet 자료구조로 되어있으며, 이 TreeSet이 바로 균형 잡힌 이진트리 구조로 데이터들을 관리해주는 자료구조 입니다. 모든 함수의 시간복잡도는 O(logN)입니다. set을 사용하기 위해서는 #include 헤더와, set name; 형태의 선언이 필요합니다. T는 타입으로, set 안에 들어갈 원소의 타입을 적어줘야 합니다. #include #include using namespace std; in..
[코드트리] Hash Set 연습문제 문제 : 데이터 비교 정수로 이루어진 두 수열을 비교하여 같은 원소를 가지고 있는지 판단하는 프로그램을 작성해 보세요. 입력 형식 첫 번째 줄에는 수열 1의 원소의 개수 n이 주어집니다. 두 번째 줄에는 수열 1의 원소들이 공백을 두고 주어집니다. 세 번째 줄에는 수열 2의 원소의 개수 m이 주어집니다. 네 번째 줄에는 수열 2의 원소들이 공백을 두고 주어집니다. 1 ≤ n, m ≤ 100,000 −109 ≤ 주어지는 숫자의 범위 ≤ 109 출력 형식 수열 2의 원소의 순서대로 그 원소가 수열 1에 존재하는 원소이면 1을, 수열 1에 존재하지 않는 원소이면 0을 공백을 사이에 두고 출력합니다. 나의 풀이 #include #include using namespace std; int main() { unor..
[코드트리] Hash Set SW중심대학 사업단에서 CodeTree와 함께 실시한 코딩테스트 대비 캠프에 참여하여 공부한 내용을 정리하였습니다. * 참고 : python과 c++, java 등 언어별로 설명이 다른 부분 존재! 필자는 c++ 사용. unordered_set STL C++에서는 unordered_set이라는 STL을 이용할 수 있습니다. unordered_set은 HashSet 자료구조로 되어있으며, 이 HashSet이 바로 해싱을 기반으로 데이터들을 관리해주는 자료구조 입니다. 모든 함수의 시간복잡도는 O(1)입니다. unordered_set은 set보다 속도가 빠르지만, 값의 존재 여부에만 관심이 있지 그 순서에는 전혀 관심이 없는 자료구조입니다. #include 헤더와, unordered_set name; 형태의..
[코드트리] TreeMap 연습문제 문제 n개의 명령이 주어졌을 때, 각 명령을 수행하는 프로그램을 작성해보세요. 명령의 종류는 크게 4가지 입니다. add k v : (k, v) 쌍을 treemap에 추가합니다. key가 k, value가 v라는 뜻입니다. 이때 만약 동일한 k가 이미 존재한다면, v로 덮어씁니다. remove k : key가 k인 쌍을 찾아 treemap에서 제거합니다. 잘못된 입력은 주어지지 않습니다. find k : key가 k인 쌍이 treemap에 있는지를 판단합니다. 있다면 해당하는 value를 출력하고, 없다면 None을 출력합니다. print_list : treemap에 있는 쌍들을 key 기준으로 오름차순 정렬하여 각 value 값들만 공백을 사이에 두고 순서대로 출력합니다. 만약 treemap이 비어있다..
[코드트리] Tree Map SW중심대학 사업단에서 CodeTree와 함께 실시한 코딩테스트 대비 캠프에 참여하여 공부한 내용을 정리하였습니다. * 참고 : python과 c++, java 등 언어별로 설명이 다른 부분 존재! 필자는 c++ 사용. map STL C++에서는 map이라는 STL을 이용할 수 있습니다. map은 TreeMap 자료구조로 되어있으며, TreeMap의 경우 균형 잡힌 이진트리 구조로 데이터들을 관리해주는 자료구조 입니다. TreeMap은 각 노드에 (key, value) 쌍 형태로 들어가 있어, key를 기준으로 노드의 위치가 결정되고 각 key에 대한 value값을 저장하는 형태입니다. 따라서 TreeMap에서 모든 함수의 시간복잡도가 전부 O(logN)입니다. #include 헤더와, map name;..
[코드트리] HashMap 연습문제 Hash Map 사용 예시, 해시맵, code tree, cpp, 자료구조, 문제, 예제 문제 n개의 명령이 주어졌을 때, 각 명령을 수행하는 프로그램을 작성해보세요. 명령의 종류는 크게 3가지 입니다. add k v : (k, v) 쌍을 hashmap에 추가합니다. key가 k, value가 v라는 뜻입니다. 이때 만약 동일한 k가 이미 존재한다면, v로 덮어씁니다. remove k : key가 k인 쌍을 찾아 hashmap에서 제거합니다. 잘못된 입력은 주어지지 않습니다. find k : key가 k인 쌍이 hashmap에 있는지를 판단합니다. 있다면 해당하는 value를 출력하고, 없다면 None을 출력합니다. 입력 형식 첫 번째 줄에는 n이 주어집니다. 두 번째 줄 부터는 n개의 줄에 걸쳐 각 명..
[코드트리] Hash Map SW중심대학 사업단에서 CodeTree와 함께 실시한 코딩테스트 대비 캠프에 참여하여 공부한 내용을 정리하였습니다. * 참고 : python과 c++, java 등 언어별로 설명이 다른 부분이 존재합니다! 필자는 c++을 사용하고 있습니다. unordered_map STL C++에서는 unordered_map이라는 STL을 이용할 수 있습니다. unordered_map은 HashMap 자료구조로 되어있으며, HashMap의 경우 해싱을 기반으로 데이터들을 관리해주는 자료구조 입니다. HashMap은 (key, value) 쌍 형태로 들어가 있어, key와 그에 따른 value 값을 동시에 저장하는 형태입니다. 따라서 HashMap의 삽입, 삭제, 탐색 등 모든 함수의 시간복잡도가 전부 O(1)입니다. u..
[코드트리] 공간복잡도 SW중심대학 사업단에서 CodeTree와 함께 실시한 코딩테스트 대비 캠프에 참여하여 공부한 내용을 정리하였습니다. 프로그램의 소요시간 뿐만 아니라, 컴퓨터의 메모리가 한정되어 있으므로 공간복잡도도 중요합니다. 공간복잡도도 시간복잡도와 동일하게 점근적 표기법을 사용합니다. function example(n) set arr = [n][n] for i = 0 ... i < n for j = 0 ... j < n arr[i][j] = 1 공간복잡도 = '이 코드가 메모리를 얼마나 차지하고 있을까?' 위 코드에서 set arr = [n][n] 이외의 다른 코드는 메모리를 차지하고 있지 않기 때문에, 공간복잡도는 O(N^2) 입니다. 그렇다면 공간복잡도는 왜 필요할까요? 문제에서 메모리 제한이 80MB라는 식으로..
728x90

티스토리툴바