공부
-
해쉬테이블(Hash Table)이란?공부/자료구조 2021. 9. 20. 01:39
해쉬 구조 Hash Table: 키(Key)에 데이터(Value)를 저장하는 데이터 구조 Key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라짐 파이썬 딕셔너리(Dictionary) 타입이 해쉬 테이블의 예: Key를 가지고 바로 데이터(Value)를 꺼냄 보통 배열로 미리 Hash Table 사이즈만큼 생성 후에 사용 (공간과 탐색 시간을 맞바꾸는 기법) 단, 파이썬에서는 해쉬를 별도 구현할 이유가 없음 - 딕셔너리 타입을 사용하면 됨 알아둘 용어 해쉬(Hash): 임의 값을 고정 길이로 변환하는 것 해쉬 테이블(Hash Table): 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조 해싱 함수(Hashing Function): Key에 대해 산술 연산을 이용해 데이터 위치를 찾..
-
링크드리스트(LinkedList)란?공부/자료구조 2021. 9. 20. 00:54
배열과 차이점 : 배열은 미리 특정 순차적인 연결된 데이터 공간을 확보해놓고 데이터를 쓰고 읽지만 링크드리스트는 미리 예약하지않고, 필요할때마다 데이터를 추가 가능하다. 링크드 리스트의 구조: 데이터저장공간 및 다음데이터공간을 가르키는 주소를 가짐(노드) 장점 - 미리 데이터 공간을 할당하지 않아도 됨 단점 - 연결을 위한 별도의 데이터 공간이 필요, 저장공간 효율 x - 인덱스로 바로 접근하는 배열과 달리 탐색에 시간이 오래걸림 - 중간 데이터 삭제, 혹은 삽입시 부가 작업 필요 간단하게 python으로 구현한 add,delete기능을 첨가한 링크드리스트 class Node: def __init__(self, data, next=None): self.data = data self.next = next ..
-
배열(Array)이란?공부/자료구조 2021. 9. 16. 14:20
너무나도 당연하게 사용하는 배열에 대해 아주 간단히 되돌아 보자. 배열 ? -> 데이터를 나열하고, 각 데이터를 인덱스에 대응하도록 구성한 데이터구조 - 같은 종류의 데이터를 효율적으로 관리하기 위해 사용 - 같은 종류의 데이터를 순차적으로 저장 장점 - 빠른 접근 가능 (&*data는 data와 동일한 표현, random access 즉 시작의 주소와 배열의 원소 한칸 한칸 떨어진 만큼 더해주어 접근) 단점 - 추가 / 삭제가 비효율적임 (주변 원소들을 이동시켜주는 작업비용이 큼)
-
자료구조란 ?공부/자료구조 2021. 9. 16. 13:32
하반기 카카오 공채 4솔 불탈락을 경험하고 너무 화가나서 자료구조 쌩기초부터 다시 되돌아 보는 시간을 가진다... - 용어 : 자료구조, 데이터 구조, data structure 등으로 불리운다. - 의미: 대량의 데이터를 효율적으로 관리할 수 있는 데이터의 구조를 의미 - 필요성: 코드상에서 효율적으로 데이터를 처리하기 위해, 데이터 특성에 따라, 체계적으로 데이터를 구조화해야 함. - 구조 : 단순(정수,실수, 문자열...), 선형 (배열, 연결 리스트, 스택, 큐 ...), 비선형 (트리, 그래프 ...) 등으로 나뉨 일상에서 볼수 있는 자료구조는, 항만에 컨테이너가 쌓이고 빠지는 것을 구현할때 Stack구조를 생각 할 수 있고 회사의 조직도에서 트리구조를 생각 해볼 수 있다. 결국, 어떤 데이터라..
-
[hackerrank] Sherlock and Array python공부/알고리즘 2021. 9. 11. 13:00
무난하게 풀었던 것같다. 1. 먼저 arr의 totalSum을 구하고, leftSum, rightSum을 초기화 해주자 2. for문을 돌려서 i > 0일때 leftSum += arr[i-1], rightSum = totalSum - arr[i] - leftSum 즉, 인덱스가 하나씩 늘어날때마다 leftSum과 rightSum을 구해주자. 3. leftSum == rightSum 이면 return YES for문이 다돌면 return NO def balancedSums(arr): # Write your code here totalSum = sum(arr) leftSum = 0 rightSum = 0 for i in range(len(arr)): if i > 0: leftSum += arr[i-1] ri..
-
[hackerrank] Missing Numbers python공부/알고리즘 2021. 9. 11. 00:38
이전 문제와 같이 해시테이블 즉, python dictionary를 이용해보았다. dictionary에서 주로 key in dict 이렇게 key값이 있는지 판별하는 in은 dictionary에서 시간 복잡도가 O(1)이다. (문제 키포인트) 1. 우선 arr, brr의 value들을 key값으로, 갯수를 value로 하는 dictionary를 각각 만들고 2. brr[i] in arrDic으로 빠진 것들을 찾아준다. 3. 빠진것들을 answerList에 append해주고 중복을 제거한뒤 sort해준다. *아쉬운점 answerList에 중복된 수가 발생된다는것, 중복된 원소가 빠졋을때 그만큼 더 연산을 하는것 ... def missingNumbers(arr, brr): # Write your code h..