CHAAANY ARCHIVE
559개의 기록을 주제별로 둘러보세요.
해야 할 일의 시작·종료 시간이 제각각일 때 서로 겹치지 않게 최대한 많이 고르려 한다. 가장 짧은 일을 먼저 고르면 될까? 가장 일찍 시작하는 일을 먼저 고르면 될까? 둘 다 그럴듯하지만, 뒤에 남길 수 있는 시간을 보지 않으면 좋은 답을 놓칠 수 있다.그리디 알고리즘(greedy algorithm)은 매 단계에서 당장 좋다고 정한 선택을 확정하고, 이전 선택을 되돌리지 않는 방법이다. 빠르게 선택할 수 있다는 장점이 있지만 그때 좋아 보이는 선택이 끝까지 좋은 결과로 이어지는지는 문제마다 확인해야 한다.겹치지 않는 일을 많이 고르려면일마다 시작 시각과 종료 시각이 있다. 앞 일이 끝나는 시각과 다음 일이 시작하는 시각이 같으면 겹치지 않는다고 하자.A: 1시~4시 B: 3시~5시 C: 0시..
주문 데이터를 서버 한 대에 담다가 저장 공간과 요청량이 늘어 두 대로 나누기로 했다. 주문 번호의 짝수와 홀수를 갈라 놓으면 일단 각 서버에 들어가는 주문 수는 비슷할 수 있다. 그런데 한 판매자의 주문 조회가 하루 종일 몰린다면 서버 두 대의 바쁜 정도도 비슷해질까?데이터의 개수를 고르게 나누는 것과 실제 일을 고르게 나누는 것은 다르다. 어디에 저장할지 정하는 규칙, 어떤 요청이 자주 오는지, 서버를 더 늘릴 때 무엇을 옮길지를 함께 봐야 한다.무엇을 기준으로 나눌까파티션(partition)은 데이터를 나눠 저장하고 관리하는 단위다. 어떤 파티션에 넣을지 판단할 때 쓰는 값을 파티션 키(partition key)라고 한다. 주문 번호를 키로 잡으면 주문 한 건을 찾을 때는 위치를 계산하기 쉽다. 반..
역에서 다른 역까지 몇 번 갈아타야 하는지 찾는다고 하자. 출발역과 바로 연결된 역부터 살핀 뒤 그다음 역을 보면 가장 적은 이동 횟수를 찾을 수 있다. 반면 연결된 역을 하나씩 끝까지 따라가면 어딘가에 도달할 수 있는지 살피기는 좋지만, 처음 찾은 길이 가장 짧다고 말할 수는 없다.대상과 대상 사이의 연결을 나타내는 자료구조를 그래프(graph)라고 한다. 역은 정점(vertex), 두 역 사이의 연결은 간선(edge)으로 표현한다. 같은 연결 정보를 두고도 어떤 순서로 방문하느냐에 따라 먼저 얻는 답이 달라진다.‘연결됐다’의 뜻부터 정해야 한다다음 연결을 보자. 여기서는 화살표 방향으로만 이동할 수 있다고 하자.A → BA → CB → DC → DD → EA에서 D로 가는 길은 A→B→D와 A→C→D..
작업자 A가 보고서를 만드는 동안 갑자기 멈췄다. 다른 작업자 B가 일을 이어받아 새 보고서를 저장했다. 그런데 A가 다시 움직이면서 자신이 만든 오래된 보고서를 덮어썼다. A가 실제로 죽은 줄 알고 B를 세웠지만, A는 잠깐 멈췄을 뿐이었다.여러 서버가 일을 나눠 할 때 ‘응답이 없다’는 사실은 ‘그 서버가 앞으로 절대 쓰지 않는다’는 증거가 아니다. 느린 네트워크, 긴 일시 정지, 과부하 때문에 응답이 늦을 수 있다. 새 작업자를 세울 때는 이전 작업자가 뒤늦게 돌아와도 결과를 망치지 않게 해야 한다.응답이 없을 때 알 수 있는 것은 어디까지인가실패 감지기(failure detector)는 다른 작업자의 응답을 관찰해 문제가 있다고 의심하는 구성 요소다. 주기적으로 보내는 생존 신호를 하트비트(hea..
작업 네 건의 우선순위가 5, 2, 8, 4라고 하자. 숫자가 작을수록 급하다면 지금은 2를 먼저 처리해야 한다. 잠시 뒤 우선순위 1인 작업이 새로 들어올 수도 있다. 급한 작업 하나를 꺼낼 때마다 목록 전체를 정렬하는 방법도 있지만, ‘다음에 처리할 한 건’을 빨리 찾는 데 맞춘 구조를 쓸 수 있다.우선순위 큐(priority queue)는 들어온 순서와 관계없이 우선순위가 가장 높은 값을 먼저 꺼내는 자료구조다. 앞에서 본 일반 큐(queue)가 먼저 들어온 것을 먼저 꺼내는 것과 다르다. 우선순위 큐를 구현하는 방법 중 하나가 힙(heap)이다. 힙은 전체 원소를 차례대로 정렬하지 않고, 다음에 꺼낼 값이 맨 앞에 오도록 필요한 관계만 유지한다.맨 앞이 최솟값인 이유최소 힙(min-heap)은 부..
주문 상세 화면의 주소가 /orders/123이라고 하자. 123을 124로 바꿨을 때 다른 사람의 주문이 보인다면 로그인 기능은 있어도 접근을 제대로 막지 못한 것이다. 서버가 ‘누가 요청했는가’만 확인하고 ‘그 사람이 이 주문을 볼 수 있는가’를 확인하지 않았기 때문이다.지난 글에서 로그인 이후의 요청을 세션으로 사용자와 연결하는 과정을 살펴봤다. 세션이 유효하다고 모든 주문을 읽을 권한이 생기는 것은 아니다. 인증(authentication)은 요청자를 확인하는 일이고, 인가(authorization)는 그 요청자가 특정 대상에 특정 동작을 해도 되는지 판단하는 일이다.URL의 번호는 접근 권한이 아니다사용자 A가 주문 123의 상세 화면을 요청한다고 하자. 서버는 세션으로 A를 확인하고, 저장소에..
폴더 안의 파일을 모두 찾는다고 하자. 지금 폴더의 파일을 확인한 뒤 하위 폴더를 열어 같은 일을 반복하면 된다. 그런데 하위 폴더의 처리가 끝났을 때, 프로그램은 원래 폴더의 어디로 돌아와 다음 폴더를 볼까?재귀(recursion)는 함수가 같은 형태의 더 작은 문제를 풀기 위해 자기 자신을 다시 호출하는 방식이다. 재귀 호출은 시작한 일을 잊고 처음부터 다시 하는 게 아니다. 아직 끝나지 않은 호출마다 돌아올 위치와 지역 상태가 남는다.폴더를 내려갈 때 무엇을 기억하나예를 들어 사진/2025/여행이라는 폴더를 차례로 방문한다고 하자. 사진의 파일을 읽다가 2025를 열고, 그 안에서 여행을 연다. 여행의 처리가 끝나면 2025에 다른 폴더가 있는지 확인해야 한다. 그 작업이 끝나면 다시 사진에 남은 ..
서버 A의 기록에는 주문 변경이 10시 00분 05초, 서버 B의 기록에는 알림 발송이 10시 00분 04초라고 적혀 있다. 숫자만 보면 알림이 먼저 나간 것 같다. 하지만 두 서버의 시계가 같은 순간을 정확히 가리킨다는 보장은 없다. A의 시계가 2초 빠르다면 실제로는 주문 변경 뒤에 알림이 나갔을 수 있다.여러 서버가 함께 일할 때 표시된 시각과 사건의 순서를 구분해야 하는 이유다. 기록의 시각은 장애를 찾는 데 유용하지만, 그것만으로 두 사건의 원인과 결과를 확정할 수는 없다.각 서버의 시계는 조금씩 다르다타임스탬프(timestamp)는 사건에 붙인 시각 또는 순서 값이다. 서버는 보통 운영체제가 제공하는 시계를 읽어 기록한다. 독립된 컴퓨터의 시계는 기준 시각과 흐르는 속도가 서로 조금씩 다를 수..
주문 목록을 최신순으로 보다가 배송 상태별로 다시 묶는다고 하자. 같은 상태의 주문은 어떤 순서로 보여야 할까? 최신순이 유지되길 기대할 수도 있고, 주문 번호순으로 보길 기대할 수도 있다. “정렬한다”는 말만으로는 답이 정해지지 않는다. 무엇을 기준으로 비교하고, 기준이 같을 때 어떤 순서를 남길지부터 정해야 한다.지난 글에서는 주문 수가 늘 때 검색 방법의 작업량이 어떻게 달라지는지 살펴봤다. 정렬에도 작업량이 들지만, 결과의 순서가 맞는지를 먼저 확인해야 한다. 빠르게 끝났더라도 같은 상태의 주문을 매번 다른 순서로 보여 준다면 원하는 정렬이 아닐 수 있다.무엇을 비교해야 할까정렬(sorting)은 여러 값에 순서를 정해 나열하는 작업이다. 숫자만 정렬할 때는 작은 값과 큰 값을 비교하면 된다. 주..
로그인 화면에서 비밀번호를 한 번 입력한 뒤에는 상품을 보고, 주문을 확인하고, 페이지를 새로 고쳐도 대개 로그인이 유지된다. 매 요청마다 비밀번호를 다시 보내는 게 아니라, 서버가 로그인 결과를 이어서 확인할 방법을 만들었기 때문이다.이 방법을 세션(session)이라고 한다. 세션은 여러 요청을 같은 로그인 상태와 연결하는 기록이다. 이 글에서는 서버가 상태를 보관하고 브라우저에는 식별자만 전달하는 방식을 예로 든다. 로그인 상태를 담는 방법은 서비스마다 다르므로 모든 웹사이트가 이 방식으로 구현됐다는 뜻은 아니다.비밀번호 확인과 이후 요청은 다른 일이다로그인할 때 서버는 계정 상태와 입력한 인증 수단을 확인한다. 인증(authentication)은 지금 요청한 사람이 그 계정의 정당한 사용자라는 근..
육아휴직 8주차.아기를 데리고 처음으로 장거리 운전을 해서 안동에 다녀왔다. 아기가 딱 백일 되는 날도 안동에서 맞았고, 아내와 오랜만에 같이 뛰고, 나는 처음으로 10km를 달렸다. 가족들과 함께 보내다 보니 일주일이 금방 지나갔다.아기와 첫 장거리 운전, 안동으로9월 21일 월요일은 안동으로 내려가는 날이었다. 전날부터 짐을 열심히 챙겼고, 아침 9시에는 대여했던 백일상을 반납했다. 남은 짐까지 차에 싣고 출발! 아기가 중간중간 쉬어가야 해서 전날 운전 코스도 미리 짜뒀다. 덕평휴게소와 단양휴게소를 들르면 대략 3분의 1, 3분의 2 지점에서 쉴 수 있었다.덕평휴게소에서 기저귀를 갈고 분유를 먹이는데 아내가 갑자기 “야!” 하고 소리쳤다. 무슨 일인가 했더니 아내의 절친과 그 어머님, 아기도 거기 있..
주문이 세 건일 때는 목록에서 번호 하나를 찾는 일이 금방 끝난다. 주문이 만 건이면 이야기가 달라진다. 지난 글에서 배열, 해시 테이블, 큐로 같은 주문을 다르게 다루는 이유를 살펴봤다. 이번에는 주문 수가 늘 때 확인해야 할 항목이 얼마나 늘어나는지 세어 보자.빅오(Big-O notation)는 입력 크기가 커질 때 작업량이 어떤 속도로 늘어나는지 나타내는 표기다. 실제 실행 시간을 초 단위로 약속하는 표기는 아니다. 컴퓨터의 속도, 데이터가 놓인 위치, 구현 방식이 달라도 입력이 늘 때 반복 횟수가 어떻게 변하는지 비교하는 데 쓴다.앞에서부터 찾으면 몇 건을 확인할까주문 번호를 배열 [17, 42, 23, 31, 55]에 접수 순서대로 담았다고 하자. 17번을 찾으면 첫 비교에서 끝난다. 55번은 ..