[가상 면접 사례로 배우는 대규모 시스템 설계 기초 1권] 5장 - 안정 해시 설계
·
Study/대규모 시스템 설계 기초
수평적 규모 확장의 필요성서버를 늘려 트래픽을 분산하는 수평 확장(Scale-out)을 위해서는, 요청을 서버에 고르게 분배하는 기술이 필수적입니다.안정 해시(Consistent Hashing)는 서버 수가 변해도 데이터 재배치가 최소화되는 기술로 널리 사용됩니다.기존 해시의 문제점: 해시 키 재배치 문제기본 방식serverIndex = hash(key) % N // N은 서버 수서버 수가 4일 때는 key0 → 서버1, key2 → 서버2 등으로 정상 작동하지만 서버가 추가/삭제되면 N 값이 변하고 모든 키의 서버 인덱스가 바뀌게 됨 → 대규모 캐시 미스(cache miss) 발생 ⚠️안정 해시(Consistent Hashing)란?서버 수 변화 시에도 전체 키의 일부만 재배치되도록 설계된 해시 기법핵..
[백준] 11403번 경로 찾기 해설 및 풀이 (Python)
·
Study/코딩 테스트
백준 11403번 경로 찾기https://www.acmicpc.net/problem/11403문제 유형그래프 이론 그래프 탐색 최단 경로 플로이드–워셜 풀이 방법 도출정점 수 N과 N x N 인접 행렬이 주어진다.i에서 j로 길이가 양수인 경로가 존재하는지 구합니다.플로이드-워셜 알고리즘을 사용하여 모든 정점 쌍 (i, j)에 대해 도달 가능한지 판단합니다.만약 i → k 그리고 k → j가 가능하면 i → j도 가능하므로, graph[i][j] = 1로 갱신합니다.모든 노드 쌍에 대해 반복합니다.도달 가능한 경우 1, 불가능한 경우 0을 출력합니다. 시간 복잡도3중 for문 : O(N³)핵심 코드 삽입 및 설명import sysfrom typing import Listdef floyd_warshall..
[프로그래머스] Lv.1 이웃한 칸 해설 및 풀이 (Python)
·
Study/코딩 테스트
프로그래머스 Lv.1 이웃한 칸https://school.programmers.co.kr/learn/courses/30/lessons/250125 문제 유형시뮬레이션구현 문제 풀이 방법 도출 주어진 2차원 보드판에서, 특정 칸 (h, w)를 기준으로 상하좌우 인접 칸 중 같은 색깔로 칠해진 칸의 개수를 구하는 문제입니다. 보드의 크기 n을 구합니다상하좌우 방향을 나타내는 변화량 리스트 dh, dw를 설정합니다.i = 0 ~ 3까지 반복하며, 상하좌우 칸의 위치를 계산합니다.해당 위치가 보드의 범위를 벗어나지 않는다면 기준 색상 (board[h][w])과 해당 위치 색상이 같은지 확인합니다. 같다면 count를 증가시킵니다.최종적으로 count 값을 반환합니다. 시간 복잡도O(1) 핵심 코드 삽입 및 ..
[백준] 1620번 나는야 포켓몬 마스터 이다솜 해설 및 풀이 (Python)
·
Study/코딩 테스트
백준 1620번 나는야 포켓몬 마스터 이다솜https://www.acmicpc.net/problem/1620문제안녕? 내 이름은 이다솜. 나의 꿈은 포켓몬 마스터야.일단 포켓몬 마스터가 되기 위해선 포켓몬을 한 마리 잡아야겠지? 근처 숲으로 가야겠어.(뚜벅 뚜벅)얏! 꼬렛이다. 꼬렛? 귀여운데, 나의 첫 포켓몬으로 딱 어울린데? 내가 잡고 말겠어. 가라! 몬스터볼~(펑!) 헐랭... 왜 안 잡히지?ㅜㅜ 몬스터 볼만 던지면 되는 게 아닌가...ㅜㅠ(터벅터벅)어? 누구지?오박사 : 나는 태초마을의 포켓몬 박사 오민식 박사라네. 다솜아, 포켓몬을 잡을 때는, 일단 상대 포켓몬의 체력을 적당히 바닥으로 만들어놓고 몬스터 볼을 던져야 한단다. 자, 내 포켓몬 이상해꽃으로 한번 잡아보렴. 포켓몬의 기술을 쓰는 것을..
[백준] 5639번 이진 검색 트리 해설 및 풀이 (Python)
·
Study/코딩 테스트
백준 5639번 이진 검색 트리https://www.acmicpc.net/problem/5639문제이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 2..