konjee's devlog

heap 힙

- 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안됨

- 이진 트리(binary tree)를 기본으로 한 자료구조

- A가 B의 부모노드(parent node)이면, A의 키(key)값과 B의 키값 사이에는 대소관계가 성립

- 키값의 대소관계는 오로지 부모노드와 자식노드 간에만 성립 (형제사이X)

- max heap 최대 힙: 부모노드 키값이 자식노드 키값보다 항상 크거나 같은 힙

- min heap 최소 힙: 부모노드 키값이 자식노드 키값보다 항상 작은 힙

- 주요동작: insert, delete, peek

- 활용 사례: 프로세스 스케줄링, 힙 정렬

priority queue 우선순위 큐

- 큐와 유사하지만 우선순위가 높은 아이템이 먼저 처리됨

- ADT인 priority queue를 구현한 대표적인 data structure가 heap

Map

- key-value pair들을 저장하는 ADT
- 같은 key를 가지는 pair는 최대 한 개만 존재
- Map의 구현체: hash table, tree-based

Hash Table(Hash Map)

- 배열과 해시 함수를 사용하여 map을 구현한 자료구조
- 일반적으로 상수 시간으로 데이터에 접근하기 때문에 빠름
- 해시 함수: 임의의 크기를 가지는 type의 데이터를 고정된 크기를 가지는 type의 데이터로 변환하는 함수, 해시테이블에서 임의의 데이터를 정수로 변환하는 함수
- hash tale resizing: 데이터가 많이 차게 되면 크기를 늘려줘야 함
- default initial capa: 16
- hash table capa: power of 2
- F(key) -> HashCode -> Index  -> Value

Hash Collision(해시 충돌)

- key값은 무한한 것에 비해 hash code는 정수로 한정되어 있기 때문에 충돌이 불가피함
- key는 다른데 hash가 같을 때 (different keys -> same code)
- key도 hash도 다른데 hash%map_capa 결과가 같을 때  (different code -> same index)
- 해결 방법: open addressing(linear probing, CPython), seperate chaining (자바)

연결 리스트 (Linked List)

- 데이터를 링크로 연결해서 관리하는 자료구조
- 자료의 순서는 정해져 있지만 메모리상 연속성이 보장되지는 않음
- 장점: 데이터 공간을 미리 할당할 필요 없음(데이터 길이 가변적이어서 데이처 추가/삭제 용이)
- 단점: 연결구조를 위한 별도 데이터 공간 필요, 연결 정보 찾는 시간 필요(접근 속도 상대적으로 느림), 데이터 추가/삭제 시 앞뒤 데이터의 연결을 재구성하는 작업 필요
- 노드(node): 데이터 저장 단위로 값과 포인터로 구성
- 데이터 추가/삭제: 위치(head/중간/tail)에 따른 연결 작업 필요

List 구현체

- Array list: 배열(array)을 사용하여 list를 구현
- Linked list: 노드를 연결(linked) 시키는 형태로 구현

배열

- 같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있음

- 인접한 메모리 위치에 있는 데이터를 모아놓은 집합

- 인덱스에 해당하는 데이터에 직접 접근(랜덤 접근)할 수 있음

- 중복O, 순서O

- 배열을 선언하면 선언한 자료형과 배열 길이에 따라 메모리가 할당됨

//배열 선언과 초기화
자료형[]배열이름=new 자료형[개수];
자료형 배열이름[]=new 자료형[개수];
int[]studentIDs=new int[10]; //int형 요소가 10개인 배열 선언

큐

- 선입선출(FIFO, First In First Out)

- 스택과 반대되는 개념

- 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용

큐 연산

1. Enqueue: 큐 맨 뒤(rear)에 데이터 추가

- queue.add(), queue.offer()

2. Dequeue: 큐 맨 앞(front) 데이터 삭제

- queue.poll(), queue.remove()

3. peek(): queue의 첫번째 값 참조

스택

- 후입선출(LIFO, Last In First Out)

- 추상적 자료구조(ADT)

- 배열이 수직으로 쌓여있는 것

- 요소의 추가 및 삭제는 맨 위에서만 차례대로 가능

- ex) 웹 뒤로가기, ctr+z 실행취소 등

- push: 자료를 넣는 것 / pop: 넣어둔 자료를 꺼내는 것

스택 연산

- peek(): 스택의 가장 윗 데이터 반환 / 0(1)

- pop(): 스택의 가장 윗 데이터 삭제 / 0(1)

- push(): 스택의 가장 윗 데이터 자리 위에(top = top+1) 메모리 생성, 데이터 x 추가 / 0(1)

- empty(): 스택이 비어있으면 1, 그렇지 않다면 0 반환 / 0(1)

import java.util.Stack;

public class Solution {
    public static void main(String[] args) {
        // 스택 생성
        Stack<Integer> stack = new Stack<>();

        // 스택에 요소 추가
        stack.push(10);
        stack.push(20);
        stack.push(30);
        stack.push(40);

        // 스택 가장 위에 있는 요소 출력
        System.out.println("peek: " + stack.peek());

        // 스택 출력
        System.out.println("stack1: " + stack);

        // 스택 가장 위에 있는 요소 삭제
        System.out.println("pop: " + stack.pop());

        // 스택 가장 위에 있는 요소 삭제 후 스택 재출력
        System.out.println("stack2: " + stack);
    }
}

프론트엔드란?

• 사용자와 상호작용하는 인터페이스로 웹/모바일 서비스의 앞단
• 주요 사용 언어: 자바스크립트 등

백엔드란?

• 사용자가 원하는 정보를 제공할 수 있도록 데이터베이스나 서버를 관리하는 웹/모바일 서비스의 뒷단
• 주요 사용 언어: 자바, 파이썬, C++, C# 등

백엔드 개발자가 되고 싶은 이유

• 서비스의 핵심 기능과 데이터 관리를 책임지는 직무로 새로운 서비스를 만들거나 기능을 추가하는 분야라는 것에 흥미를 느낌