Chapter 2 · 개략적인 규모 추정 모든 프로그래머가 알아야 하는응답 지연값(Latency) Jeff Dean의 Numbers Every Engineer Should Know | 시스템 설계의 직관적 기준 📋 목차 응답 지연값이란? 왜 중요한가 핵심 지연 시간 수치 표 (Jeff Dean) 시각화: 지연 시간 비교 바 차트 시스템 설계에서 얻는 인사이트 메모리 vs 디스크 vs 네트워크 비교 1 응답 지연값이란? 왜 중요한가 시스템을 설계할 때 "이 작업이 얼마나 빠른가?"에 대한 감각이 필요합니다. 메모리 접근은 얼마나 빠른지, 디스크 읽기는 얼마나 느린지, 네트워크 왕복은 어느 정도인지 ..

Chapter 2 · 개략적인 규모 추정 2의 제곱수와 데이터 용량 단위완벽 정리 가상면접 사례로 배우는 대규모 시스템 설계 기초 | Back-of-the-envelope Estimation 📋 목차 왜 2의 제곱수인가? 2의 제곱수 핵심 표 실무 데이터 용량 감각 익히기 면접에서 쓰는 빠른 계산 팁 1 왜 2의 제곱수인가? 컴퓨터는 모든 데이터를 비트(bit) 단위로 처리합니다. 비트는 0 또는 1만 가질 수 있고, 이 때문에 컴퓨터의 모든 용량 단위는 2의 제곱수를 기반으로 합니다. 💡 핵심 개념 시스템 설계 면접에서 "대략 몇 TB의 스토리지가 필요한가?" 같은 질문에 답하..

3계층은 다른 네트워크 대역을 연결하는 역할을한다-LAN 과 LAN 을 이어주는 역할(스위치같은 3계층 장비가 필요하다) 원거리 통신을 위해서는 MAC 주소 뿐만아니라 ip 주소가 필요하다또한 서브넷 마스크, 게이트웨이가 같이 필요하다.3계층 프로토콜 종류ARP 프로토콜IPv4 프로토콜ICMP 프로토콜 IPv4 프로토콜IPv4 주소 구조IPv4는 32비트로 구성되어 있으며, 8비트씩 4부분으로 나누어 10진수로 표현한다. 예를 들어 192.168.0.1 같은 형태이다. 192.168.0.1└─┘ └─┘ └ └ 8 8 8 8 비트 = 총 32비트IPv4 헤더 구조IPv4 패킷의 헤더에는 다음과 같은 정보가 담겨 있다.Version: IP 버전 (IPv4는 4)Header Length: 헤더 길..

근거리 네트워크 통신 - OSI 2계층OSI 2계층에서 하는 일2계층은 같은 네트워크 상에서 송신 장비와 수신 장비에 대한 데이터를 전달하는 역할을 한다. 추가적으로 오류 제어, 흐름 제어를 수행한다.2계층은 같은 네트워크만 가능하기 때문에 다른 네트워크 대역 통신을 위해서는 3계층이 필요하다. 2계층에서 사용하는 주소 - MAC 주소MAC 주소란?MAC 주소(물리 주소)는 16진수로 구성되어 있으며 12자리로 이루어진다. 00:1A:2B:3C:4D:5E└─────┘ └─────┘ OUI 고유번호앞 6자리(OUI): 제조 회사 식별 ID 뒤 6자리: 제조사에서 부여한 고유 식별 번호MAC 주소의 특징MAC 주소는 네트워크 카드(NIC)에 물리적으로 할당된 고유한 주소이다. 전 세계에서 유일한 값..

알고리즘중 값을 배열에 저장하는 로직에서 값의 존재여부를 조회할때 ArrayList 의 contain 를 사용하게 되면 collection 매서드의 동작에서 ArrayList 의 길이 n 만큼 O(n) 만큼 순회하게된다. 이런 케이스는 많은 시간복잡도를 요구한다. HashMap으로 치환이가능한 알고리즘이라면 HashMap의 키에 값을 넣고 키를 가지고있는지 조회하면 HashMap의 containkey 타입으로 확인을 하면 key 값의 메모리 주소를 바로 찾기 때문에 O(1) 단한번의 연산으로 끝낼수있다 import java.util.ArrayList; public class Scartch { public int solution(int[] A) { ArrayListarrayList = new ArrayLi..

기본적으로 괄호문제의 경우 스택을 사용하여 풀이를 진행합니다. 괄호문제에서는 스택은 선언, push, pop 만 알고있어도 쉽게 풀이가 가능합니다. 여기서 스택의 특징인 push 로 들어간 순서에서 가장 마지막으로 들어간 순서 부터 꺼내는 자료구조입니다. 보통괄호 문제는 ( 일때 push 를 하고 , ) 가 나올때 pop 을 해서 Stack.isEmpty()를통해 스택이 비어있게 되면 올바른 괄호가 되는것입니다. (()) 식의 중첩이나 ()() 개별 괄호를 검증할수있습니다. 이런식으로 Stack.isEmpty() 메서드를 통해 stack 이 남아있거나. ex) ()()( , ((())

필자는 위의 유형과 같은 문제를 풀다 해결법이 안나오면 스케치를 해봅니다. 그러다 우연히 발견한것은 N에 대한 정답의 값이 n-1과 n-2 의 합과 같은 패턴 이것은 피보나치 수열입니다. 대부분의 알고리즘 문제에서 피보나치수열은 시간복잡도를 많이 소요하기 때문에 통과하기 어렵습니다. 자세한 설명과 이유는 https://eccsck.tistory.com/51에 있습니다. 역시나, 결과는 시간 초과입니다. 이번에는 배열을 통해 이전값들을 저장하고 다시 불러오는 동적 계획법을 이용해서 풀이해보겠습니다. n의 크기만큼 값을 구하여 각각의 값을 저장하게 됩니다. 그렇게 되면 이전의 값을 구하기 위해 다시 계산하지 않기때문에 시간복잡도를 줄일수있습니다 확실히 시간복잡도가 개선 되어서 통과하게 되었습니다 public..

위와 같은 문제를 접근할때는 그림이나 표를 먼저 그려보며 접근하는 편입니다. 표를 보면 알수있듯이 각 집의 거주인원= 아래층같은호+같은층이전호 라는 패턴을 알수있습니다. 층과 호를 기준으로 알고리즘을 짰을때 사람수(x층y호) = 사람수(x-1층y호)+사람수(x층y-1호)호 라는 식으로 접근이 가능합니다!. 일반적으로 위방식같은 메서드의 알고리즘은 재귀용법으로 접근하게됩니다. 물론 이렇게 접근해도 정답은 나오지만 .... 피보나치 수열 알고리즘을 예시로 위메서드의 특정 값을 구할때 이미 구한 값을 계속 구하게 되는 문제가 있습니다 시간복잡도를 증가 시키기때문에 효율적인 알고리즘이라고 생각하지않습니다.... 그리하여 배열을 메모리를 이용한 동적 계획법으로 코드를 다시 짜보았습니다 사람수[x층][y호] = 사..

신장트리란? spaning tree 라고하며 모든노드가 모두 서로 연결되어있으며, 사이클이 존재하지않는것(트리의속성) 최소신장트리란? minimum Spanning Tree 신장트리의 연결된 간선의 합이 최소인 신장트리 최소신장트리 알고리즘 크루스칼 알고리즘 프림 알고리즘 크루스칼알고리즘 탐욕알고리즘 기반 모든노드를 간선을 기준으로 정렬한후 간선이 낮은것부터 연결한다.