데이터와 한걸음씩

2023.09.29 - #1. 해시테이블 (hash) / python dictionary #1. 해시테이블 (hash) / python dictionary 데이터역량 키우는 하루하루의 기록 hanawithdata.tistory.com 이전에 list를 딕셔너리로 변환해서 빠르게 조회하는 방법으로 문제를 풀어보았다. 오늘은 해시테이블로 난이도가 좀 더 있는 문제를 풀어보려고 한다. https://leetcode.com/problems/longest-consecutive-sequence Longest Consecutive Sequence - LeetCode Can you solve this real interview question? Longest Consecutive Sequence - Given an u..

스택 & 큐 자료구조란? 데이터를 순차적으로 쌓아나가는 선형 자료구조 스택: 들어온 순서대로 쌓고, 맨 나중에 들어온 데이터 먼저 꺼냄 , LIFO (Last In First Out) 설거지 괄호 짝맞추기 웹사이트 뒤로가기 큐: 들어온 순서대로 쌓고, 먼저 들어온 데이터 먼저 꺼냄 ,FIFO (First In First Out) 맛집 줄서기 프린터 출력 순서 등 순서대로 처리해야하는 업무에 적용 스택과 큐를 사용하는 문제들은 보통 리스트에 값을 차례로 쌓다가 특정 값을 마주칠 때 하나씩 pop() 해주는 문제이다. 대표적인 문제 예시로는 괄호 짝맞추기 문제가 있다. 문제를 풀이 컨셉은 "(" 괄호가 들어오면 스택에 쌓아주다가 ")" 괄호가 들어오면 pop() 해주면서 짝이 맞는지 검사하는것이다. 이렇게 ..

2023.10.05 - #3. 연결리스트 (Linked list) / python으로 구현 #3. 연결리스트 (Linked list) / python으로 구현 데이터역량 키우는 하루하루의 기록 hanawithdata.tistory.com 지난번엔 연결리스트에 대해서 알아보고 단일 연결 리스트를 구현해보았습니다. 단일연결 리스트란 Node가 다음 노드를 가리키는 next만 가지고 있는것입니다. 오늘 구현해볼 이중연결리스트 (double linked list)는 이전 노드를 값이 추가된 노드입니다. 단일 연결리스트는 next만 가지고 있어서 전방탐색만 가능하고 , 이중연결리스트는 앞, 뒤 모두 탐색 가능합니다. 대신 메모리를 더 사용하기 때문에 사용목적에 따라 구현하는것이 좋습니다. 코드 구현하기 자료구조:..

2023.10.01 - #2. 배열 (Array) / python list #2. 배열 (Array) / python list 데이터역량 키우는 하루하루의 기록 hanawithdata.tistory.com array는 이전글 참고해주세요. 이전글에서 List의 종류에는 array list와 linked list가 있다고 분류했습니다. 이 글에서는 Linked List를 알아보고 코드로 구현해보도록 하겠습니다. 연결리스트의 구조 메모리상에 연속적으로 데이터를 저장하는 배열과 달리 연결리스트는 메모리상에 연속적이지 않게 데이터를 저장할 수 있는 자료구조입니다. 노드라는 단위로 구성되었고, 노드는 데이터와 다음 노드를 가리키는 주소로 만들어집니다. 그리고 연결리스트의 가장 첫 노드를 가리키는 head가 존재합..

배열은 데이터를 저장하는 아주 기본적인 자료구조이다. 데이터를 순차적으로 저장하는 List는 크게 Array List 와 Linked List로 나뉘는데 먼저 배열부터 살펴보자. List Array List Array Dynamic Array (Python의 list) Linked List 배열은 다시 또 두가지로 나뉘는데 기본 정적 배열을 보완하여 동적 배열을 구현했다고 보면 된다. 파이썬의 리스트 타입 자료구조는 동적 배열로 구현되어 있다. 배열 (array) 배열의 두가지 특징 고정된 저장공간 순차적인 데이터 저장 배열 메모리 할당 int arr[5] = {1,2,3,4,5} 예를들어 위에 처럼 크기5의 배열을 선언한다면 int (4byte) * 5 = 20 byte의 공간을 메모리에 할당하고 각각..

정의 빠른 탐색을 위해 key-vlaue 쌍을 저장하는 자료구조이며 key는 중복될 수 없고 순서가 없다. 파이썬에서는 dictionary 데이터 타입이 해시테이블을 제공한다. *코드 예시 student = { 1 : "최하나", 2 : "최두리", 3 : "최세찌", 4 : "최네찌" } 해시테이블은 저장, 삭제, 검색 모두 O(1)의 시간복잡도를 가져 매우 빠르다. In 연산자와 사용 특정 key값이 해시테이블에 있는지 조회할 때 in과 사용하면 매우 효율적이다. (리스트는 O(n) 인데, 해시테이블은 O(1) 시간복잡도를 가짐) 만약에 1000명의 학생중에 "최하나" 라는 학생이 있는지가 궁금하다고 할 때 students = ['김xx' , '이xx', ....., '최xx'] 이렇게 리스트로 정의..

알고리즘은 효율적인 패턴을 찾아내어 문제를 해결하는데 도움을 준다. 앞으로 그 알고리즘을 하나하나 배우면서 문제를 풀어나가려고 한다. 첫번째로 재귀호출에 대해서 공부해보았다. 알고리즘 문제를 풀 때, 복잡한 수식을 생각하기전에 단순하게 모든 경우의 수를 계산해보는 방법이 있다. 이를 완전탐색이라고하는데, 이 때 재귀함수를 사용하면 간단하게 해결할 수 있다. 재귀호출이란? 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수 반복문을 재귀호출 이용하도록 바꿔보자! 문제) 1~N까지의 수를 더해주는 함수 ex) numbers=5 -> 1+2+3+4+5 1) 반복문 사용 def is_sum(N): sum_num = 0 for i in..