11.06 - TIL

오늘의 코드카타

• 빛의 경로 사이클
  • S, L, R 이라는 각각의 점마다 방향 성질을 더해서 사이클을 찾는 문제
  • 점을 한 번만 방문해서 사이클을 찾는 것이 아니라, 점을 기준으로 4가지 방향을 전부 탐색해야 함
  • L, R 은 서로 반대 방향으로 움직이는 특징이 있기 때문에 이를 이용하면 더 간단하게 로직 작성 가능
  • https://school.programmers.co.kr/learn/courses/30/lessons/86052
• 이중우선순위큐
  • 최댓값과 최솟값을 삭제하는 로직 작성 : multiset + iterator 활용
  • 문제 이름 그대로 우선순위큐를 사용하면 더 복잡해짐
  • https://school.programmers.co.kr/learn/courses/30/lessons/42628
    
    

오늘의 공부

기술 연구

• 모션 워핑
  • 진행하면서 있었던 트러블 슈팅 정리
  • 정리 페이지 : 모션 워핑
    
    

오늘의 CS

메모리 구조에서 스택과 힙의 차이점

스택 영역

• 지역 변수, 함수의 매개 변수 등이 저장되는 영역
• LIFO (Last-In, First-Out) 방식으로 데이터를 관리함
• 스택 메모리 크기는 컴파일 타임에 할당됨
• 컴파일 타임에 할당되는 데이터가 모두 스택에 할당되는 것이 아니고, 실제 메모리 할당은 프로그램 시작 시 OS에 의해 이루어짐.

힙 영역

• 사용자에 의해 동적 메모리 할당이 일어나는 영역
• 데이터 할당이 무작위로 일어나기 때문에, 메모리 단편화가 일어날 수 있음
• 힙 메모리 크기는 런타임 시점에 동적으로 결정됨
  
  

Trie 자료 구조

사용처

• 사전 프로그램에서 사용자가 입력한 접두어에 해당하는 단어 목록을 자동으로 완성해주는 기능
• 욕설 필터링이나 민감 단어 검색 기능
  
  

트라이의 구조 및 특징

• 문자열의 저장, 검색, 접두어 기반의 자동 완성 기능에 최적화된 트리 형태
• 각 노드는 단일 문자를 나타내고, 자식 노드 배열 및 단어 종료 플래그를 가지게 됨
• 삽입, 검색, 삭제의 시간복잡도 : O(N)

장점

• 검색 속도 매우 빠름 : 문자열 길이와 동일한 O(N)의 시간복잡도를 가지기 때문에 매우 빠름
• 효율적인 접두어 처리 : 공통 접두어를 공유하여 메모리 활용도가 높음
• 정렬된 결과 : DFS 순회하면 단어들에 대해 사전순으로 접근 가능

단점

• 많은 메모리 사용 : 각 노드가 알파벳 크기의 배열이나 포인터를 가지고 있어서, 노드가 길어지면 메모리 낭비가 심함
• 문자 집합에 의존 : 문자 집합이 커지면 노드의 크기가 너무 커짐
  
  
• 정리 페이지 : Trie 자료 구조