LUNA's Archive

[Algorithm] Dynamic Programming

동적 프로그래밍이란? 문제의 크기를 변화하면서 정답을 계산하는데, 작은 문제의 결과를 이용해서 큰 문제의 정답을 빠르게 계산하는 알고리즘 문제 풀이 순서 문제가 원하는 정답을 찾기 위해 가장 먼저 완전 탐색(Brute-Force Search) 접근을 시도한다. 근데, 완전 탐색 과정에서 탐색하게 되는 경우가 지나치게 많아서 도저히 안 될 것 같다. 이럴 때, 모든 경우를 빠르게 탐색하는 방법으로 동적 프로그래밍 접근을 시도한다. 동적 프로그래밍 접근 순서 풀고 싶은 가짜 문제 정의 가짜 문제를 풀면 진짜 문제를 풀 수 있는가? 초기값은 어떻게 되는가? 점화식 구해내기 진짜 문제 정답 출력하기 예제 피보나치 수열 가짜 문제 정의 D[i] : i 번째 까지 피보나치 수열의 합. 진짜 문제를 풀 수 있는가? ..

Data Structure & Algorithm 2023. 8. 27. 14:43

[System Design Interview] 9장. 웹 크롤러 설계

웹 크롤러 : 웹에 새로 올라오거나 갱신된 콘텐츠를 찾아내는 것이 주된 목적인 소프트웨어. 웹 크롤럴 사용 방법 검색 엔진 인덱싱 : 웹 페이지를 모아 검색 엔진을 위한 로컬 인덱스를 만든다. 웹 아카이빙 : 나중에 사용할 목적으로 장기보관하기 위해 웹에서 정보를 모으는 절차. 웹 마이닝 : 인터넷에서 유용한 지식을 도출해 낼 수 있게해준다. 웹 모니터링 : 인터넷에서 저작권이나 사욮권이 침패되는 사례를 모니터링할 수 있다. 1단계 문제 이해 및 설계 범위 확정 웹 크롤러 알고리즘 URL 집합이 입력으로 주어지면, 해당 URL들이 가리키는 모든 웹 페이지를 다운로드한다. 다운받은 웹 페이지에서 URL들을 추출한다. 추출된 URL들을 다운로드할 URL 목록에 추가하고 위의 과정을 처음부터 반복한다. 웹 크..

대규모 설계 기초 2023. 8. 9. 21:52

[System Design Interview] 8장 URL 단축기 설계

1단계 문제 이해 및 설계 범위 확정 시스템 설계 면접 문제는 의도적으로 어떤 정해진 결말을 갖지 않도록 만들어 진다. 따라서 면접장에서 시스템을 성공적으로 설계해 내려면 질문을 통해 모호함을 줄이고 요구사항을 알아내야 한다. URL 단축기 시스템 기능 URL 단축 : 주어진 긴 URL을 훨씬 짧게 줄인다. URL 리디렉션 : 축약된 URL로 HTTP 요청이 오면 원래 URL로 안내 높은 가용성과 규모 확장성, 그리고 장애 감내가 요구됨 개략적 추정 쓰기 연산 : 매월 1억 개의 단축 URL 생성 초당 쓰기 연산 : 1억/24/3600 = 1160 읽기 연산 : 읽기 연산과 쓰기 연산 비율은 10:1이라고 하자. 그 경우 읽기 연산은 초당 11,600회 발생한다(1160 * 10 = 11,600) URL..

대규모 설계 기초 2023. 7. 23. 22:57

[System Design Interview] 7장 분산 시스템을 위한 유일 ID 생성기 설계

1단계 문제 이해 및 설계 범위 확정 요구사항 ID는 유일해야 한다. ID는 숫자로만 구성되어야 한다. ID는 64바이트로 표현될 수 있는 값이어야 한다. ID는 발급 날짜에 따라 정렬 가능해야 한다. 초당 10,000개의 ID를 만들 수 있어야 한다. 2단계 개략적 설계안 제시 및 동의 구하기 분산 시스템에서 유일성이 보장되는 ID를 만드는 방법 다중 마스터 복제 UUID 티켓 서버 트위터 스노우플레이크 다중 마스터 복제 다중 마스터 복제 방법은 데이터베이스의 auto_increment 기능을 확용하는 것이다. 다만 다음 ID의 값을 구할 때 1만큼 증가시켜 얻는 것이 아니라, k만큼 증가시킨다. k는 현재 사용중인 데이터베이스 서버의 수다. 단점 여러 데이터 센터에 걸쳐 규모를 늘리기 어렴다. ID의..

대규모 설계 기초 2023. 7. 18. 21:42

[System Design Interview] 5장 안정 해시 설계

안정 해시 사용 이유 수평적 규모 확장성을 달성하기 위해 요청 또는 데이터를 서버에 균등하게 나누는 것이 중요하고, 이를 위해 안정 해시가 사용 된다. 해시 함수란? 해시 함수는 임의의 길이의 입력값을 받아서 고정 크기의 출력값을 생성하는 수학 함수. e.g. SHA-256 해시 키 재배치 문제 N개의 캐시 서버가 존재할 때, 이 서버들에 부하를 균등하게 나누는 보편적 방법은 아래의 해시 함수를 사용하는 것이다. 4대의 서버를 사용할 때 위의 해시 함수의 결과값은 아래 표과 같이 나온다. 아래 그림은 키 값이 서버에 어떻게 분산되는지 보여준다. 이 방법은 서버 풀의 크기가 고정되어 있을 때, 그리고 데이터 분포가 균등할 때는 잘 동작한다. 하지만 서버가 추가되거나 기존 서버가 삭제되면 문제가 생긴다. 예..

대규모 설계 기초 2023. 7. 4. 23:26

[System Design Interview] 3장 시스템 설계 면접 공략법

시스템 설계 면접이란? 두 명의 동료가 모호한 문제를 풀기 위해 협력하여 그 해결책을 찾아내는 과정에 대한 시뮬레이션. 평가 요소 기술적 능력 협업 적합성 압박이 심한 상황도 잘 헤쳐 나갈 자질 모호한 문제를 건설적으로 해결할 능력 좋은 질문을 던질 능력 부정적 신호 설계의 순수성에 직착하여 타협적 결정을 도외시 함 완고함 편협함 효과적 면접을 위한 4단계 접근법 1단계 문제 이해 및 설계 범위 확정 바로 답을 말하지 말고, 속도를 늦춰라. 깊이 생각하고 질문하여 요구사항과 가정들을 분명히 하라. 구체적으로 어떤 기능들을 만들어야 하나? 제품 사용자 수는 얼마나 되나? 회사의 규모는 얼마나 빨리 커지리라 예상하나? 회사가 주로 사용하는 기술 스택은 무엇인가? 설계를 단순화하기 위해 활용할 수 있는 기존 ..

대규모 설계 기초 2023. 6. 12. 21:50

[System Design Interview] 2장 개략적인 규모 추정

개력적인 규모 추정 : 보편적으로 통용되는 성능 수치상에서 사고 실험을 행하여 추정치를 계산하는 행위로서, 어떤 설계가 요구사항에 부합할 것인지 보기 위한 것이다. 2의 제곱수 제대로 된 계싼 결과를 얻으려면 데이터 볼륨의 단위를 2의 제곱수로 표현하려면 아떻게 되는지를 우선 알아야한다. 모든 프로그래머가 알아야 하는 응답지연 값 메모리는 빠르지만 디스크는 아직도 느리다. 디스크 탐색은 가능한 한 피하라. 단순한 압축 알고리즘은 빠르다. 데이터를 인터넷으로 전송하기 전에 가능하면 압축하라. 데이터 센터는 보통 여러 지역에 분산되어 있고, 센터들 간에 데이터를 주고받는 데이틑 시간이 걸린다. 가용성에 관계된 수치들 고가용성 : 시스템이 오랜 시간 동안 지속적으로 중단 없이 운영될 수 있는 능력. SLA(S..

대규모 설계 기초 2023. 6. 11. 20:50

[System Design Interview] 1장 사용자 수에 따른 규모 확장성

단일 서버 사용자 처리 흐름 1. 사용자는 도메인 이름을 이용하여 웹사이트에 접속한다. 2. DNS 조회 결과로 IP 주소가 반환된다. 3. 해당 IP 주소로 HTTP요청이 전달된다. 4. 요청을 받은 웹 서버는 HTML 페이지나 JSON 형태의 응답을 반환한다. 데이터베이스 사용자가 늘면 서버 하나로는 충부낳지 않아서 여러 서버를 두어야 한다. 하나는 웹/모바일 트래픽 용도고, 다른 하나는 데이터베이스 용이다. 이렇게 분리하면 각각을 독립적으로 확장해 나갈 수 있게 된다. 어떤 데이터베이스를 사용할 것인가? 관계형 데이터베이스와 비-관게형 데이터베이스 사이에서 고를 수 있다. 대부분의 경우 관계형 데이터베이스가 최선일 것인데, 40년 이상 시장에서 살아남아 잘 사용되어 온 시스템이기 때문이다. 하지만 ..

대규모 설계 기초 2023. 6. 11. 16:30