전체 글 320

[고급 알고리즘] Graph(Shortest Path): Floyd-Warshall

1. Floyd-Warshall모든 정점 쌍 간의 최단 경로를 찾는 알고리즘 입니다. 가중치가 양수 혹은 음수인 그래프에서 사용됩니다. (단, 음의 사이클에는 사용 불가) Dynamic Programming인접행렬을 사용하여 각 정점 쌍 간의 최단 거리를 반복적으로 갱신합니다. 2. 동작 원리모든 정점을 경유지로 설정하고, 최단 경로가 경유지를 거쳐 더 짧아질 수 있는지 확인하며 최단 경로 갱신 초기화모든 정점 쌍에 대해, 직접 연결된 경로의 거리 초기화자기 자신으로 가는 경로 = 0연결되지 않은 경로 = infinit 경유지 검사i->j 로 가는 최단 경로가 i -> k -> j로 가는 경로를 통해 더 짧아질 수 있는지 검사 (정점 k를 경유지로 설정)모든 정점에 대하여 반복 3. 구현int[][] d..

Algorithm 2024.09.20

[고급 알고리즘] Greedy: Activity Selection Problem

1. Activity Selection Problem (활동 선택 문제)한 사람이 참여할 수 있는 최대 활동 수를 구하는 문제입니다.한 사람이 동시에 두 가지 활동을 참여할 수 없습니다. 해결 방법가장 먼저 끝나는 활동부터 선택합니다. 탐욕적 선택 속성현재 선택이 다음 선택의 기준에 영향을 미치지 않습니다.선택할 수 있는 가능 시간을 최대화하여, 남은 활동들을 선택할 수 있는 여지를 최대화합니다. 최적 부분 구조먼저 끝나는 활동을 선택하고, 남은 시간에 대해서도 동일한 방식을 적용할 수 있습니다.

Algorithm 2024.09.20

[알고리즘] Range: Sliding Window

1. Sliding Window선형 자료구조에서 subarray를 찾는 알고리즘 입니다.일정한 크기의 구간을 움직여 찾습니다. 동작 원리윈도우 설정초기 윈도우 구간을 설정함 윈도우 이동한 번에 한 요소씩 이동시킴 (왼쪽 끝 제거 + 오른쪽으로 이동) 조건 확인각 윈도우가 특정 조건을 만족하는지 확인 장점성능슬라이딩 윈도우를 사용하면 O(n) or O(n log n) 브루트 포스일 경우, O(n^2) 메모리 효율성in-place 알고리즘 (새로운 배열 생성 X)  2. 문제subarrayMinimum Size Subarray Sum (문제) (해설)Longest Substring Without Repeating Characters (문제) (해설)

Algorithm 2024.09.19

[Real MySQL] 16-1. 복제

"Real MySQL" 책을 정리한 포스팅 입니다 1. 복제한 서버에서 다른 서버로 동기화되는 것 Source Server원본 데이터를 가진 서버변경이 최초로 이루어짐 (데이터 및 스키마) Replica Server복제된 데이터를 가진 서버소스 서버 동기화:소스 서버로부터 데이터를 전달받아 자신의 리포지토리에 반영 목적scale-out트래픽 대응 목적scale-up보다 훨씬 더 유연한 구조 backup데이터 정합성이 깨질 경우 (개발자 실수 or 공격 등)백업 서버의 데이터로 사용함메인 서버가 터질 경우지리적으로 분산된 백업 서버가 메인 서버의 역할을 대신함 데이터 분석용백업 서버에서 대신 담당하여 최적화데이터 분석은 리소스 소모가 큰 연산메인 서버로 데이터를 분석할 경우 클라이언트 요청 처리에 영향을 ..

Database/Mysql 2024.09.07

[Real MySQL] 8-0. 인덱스: Disk

"Real MySQL" 책을 정리한 포스팅 입니다 HDD (Hard Disk Drive)기계식 (플래터)데이터 보관플래터 위를 헤드가 이동하면서 데이터 읽고 씀 인터페이스SATA(소비자용)SAS(고성능) SSD (Solid State Drive)반도체기계식 플래터에 비해 훨씬 빠릅니다. (기계식으로 플래터를 회전시킬 필요 없음)소음 X 플래시 메모리 (NAND)비휘발성: 전원이 공급되지 않아도 데이터 보관 가능 O

Database/Mysql 2024.09.07

[Redis] 2. Understanding Data Types

cachingqueuingevent processing 1. Stringbyte sequence 저장문자열 매핑에 주로 사용됩니다. (key, value 모두 문자열) Data StructureTextSerialized objectBinary array(image, video, audio) Usagecachecountersbitwise operation 더보기SET bike:1 Deimos # key(namespace:id) - valueGET bike:1 # Deimos 2. JSONSyntax: JSONPath UsageAPI Response (cached) 더보기JSON.SET user:1001 $ '{"name": "John Doe", "email": "john.doe@example.com", ..

Database/Redis 2024.09.05

[NoSQL] NoSQL

1. NoSQL이란?Not Only SQL (SQL 지원)RDBMS보다 덜 제한적인 일관성 모델을 사용하는 데이터 매커니즘 유연한 데이터 모델스키마가 고정되어 있지 않음 대규모 분산 데이터클라우드 컴퓨팅 등장에 맞춰 생긴 기술데이터 공유 및 시스템 운용의 효율성 좋음 2. 장점성능latency: 빠르게 데이터 읽고 쓸 수 있음throughput: 다수의 요청을 효율적으로 처리할 수 있음 (수평적 확장) 단순성설계: 논리적, 물리적 설계 스킵clustering: 분산환경에서 사용하기 용이하도록 지원partitioning (horizontal): 분산환경에서 사용하기 용이하도록 지원 3. 종류key-value데이터: key-value 쌍빠른 데이터 접근 가능Redis, DynamoDB, Riak wide c..

Database 2024.09.05