개구리의 개발 블로그 개구리의 개발 블로그

브라우저가 URL을 분석한다. (HTTPS 여부, 도메인 주소, PORT 번호, 파일의 경로 등) DNS에서 IP 주소를 가져온다. 브라우저의 캐시에는 DNS 기록들이 저장되어 있다. 가장 먼저 이곳을 확인한다. OS 캐시, router 캐시, ISP 캐시 순서대로 최대한 빠르게 DNS 기록을 찾는다. 캐시 서버에 DNS 기록이 없다면 로컬 DNS 서버에서 URL 주소에 해당하는 IP 주소를 요청한다 로컬 DNS 서버에 없다면 로컬 DNS 서버가 IP 주소를 찾기 위해 루트 DNS 서버, 도메인 DNS 서버, 등 하위 DNS 서버로 차례대로 요청한다. IP 주소를 이용해 라우터에서 포워딩을 한다. 라우터의 라우팅 프로세서가 만든 라우팅 테이블을 이용한다. ARP 프로토콜을 통해 논리적인 주소인 IP 주소..

0. DNS의 동작 www.frog.blog.com을 검색한다. 대부분의 로컬 DNS 서버에 매핑이 존재한다. 만약 없다면, 루트 DNS 서버에 질문을 하고 답변이 로컬 DNS 서버에 전달된다. 하위 DNS 서버로 재귀적으로 질문과 답변을 얻으며 최종적으로 하나의 A 레코드(IP 주소)를 받는다. 이 때, DNS 캐싱을 통해 지연 성능을 향상시킬 수 있다. 1. DNS 동작 원리 중앙 집중 데이터베이스는 확장성이 없다. 무수히 많은 도메인을 매핑하기 위해 분산 계층 데이터베이스를 사용한다. 계층으로 구성된 크게 3가지 유형의 DNS 서버가 있다. 만약 DNS 클라이언트가 호스트 네임 www.amazon.com에 접속하려고 한다면 클라이언트가 루트 서버 중 하나에 접속한다. 루트 서버는 최상위 레벨 도메인..

백준 2836번 수상 택시 파이썬 문제 링크 - https://www.acmicpc.net/problem/2836 2836번: 수상 택시 상근이가 살고 있는 도시에는 큰 강이 흐르고 있고, 모든 사람의 집은 이 강 근처에 있다. 집은 0번부터 M번까지 강을 따라서 번호가 매겨져 있고, 인접한 집 사이의 거리는 모두 1 킬로미터이다. www.acmicpc.net 스위핑 알고리즘 문제이다. 스위핑 알고리즘이라고 해서 특별한 방법이 있는 것은 아닌 것 같고 전체를 탐색하며 마주하는 이벤트를 바로바로 처리하면서 푸는 유형이다. 그렇기 때문에 스위핑 자체에 집중하기보다 시간복잡도를 줄여 문제를 풀기 위한 방법을 떠올려야 한다. M명의 사람을 모두 태울 수 있기 때문에 순방향 구간을 태워줘야 하는 경우 신경 쓸 필..

백준 2370번 시장 선거 포스터 파이썬 문제 링크 - https://www.acmicpc.net/problem/2370 2370번: 시장 선거 포스터 첫줄에는 포스터의 개수 n(1 ≤ n ≤ 10,000)이 주어지고, 그 다음 n줄에는 각 포스터의 왼쪽 끝의 위치와 오른쪽 끝의 위치 l, r이 주어진다. (1 ≤ l

백준 14427번 수열과 쿼리 15 파이썬 문제 링크 - https://www.acmicpc.net/problem/14427 14427번: 수열과 쿼리 15 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 : 수열에서 크기가 가장 작은 값의 인덱스를 www.acmicpc.net 세그먼트 트리 문제를 공부해야겠다고 생각한 지 벌써 3개월은 된 것 같다. 심지어 이 문제도 트리를 이용한 해시 문제를 풀기 위해 시도했지만 도저히 안풀려서 알고리즘 분류를 보고 세그먼트 트리를 공부하게 되었다. 우선 쿼리 문제이기 때문에 python을 사용한다면 sys.stdin.re..

냅색 분류인 것을 보고 풀었기 때문에 일단 2차원 배열을 만들어야겠다는 생각을 했다. 풀긴 했지만 코드가 깔끔하지도 않고 시간도 꽤나 오래 걸렸다. 1106번 문제를 풀기 전에 1차원 배열을 이용해 평범한 배낭 문제를 풀이하는 방법을 알아보자. 0. 일반적인 냅색 문제 풀이(1차원 / 2차원 배열 이용) 12865번 평범한 배낭 문제를 기준으로 설명하겠습니다. https://www.acmicpc.net/problem/12865 2차원 배열에서 dp[i][j]에 i번째 보석까지 j 무게를 사용했을 때 얻을 수 있는 최대 가치를 저장한다. 모든 보석에 대하여 1에서 최대 용량까지 반복문을 실행하며 dp[i][j] = max(dp[i-1][j], dp[i-1][j-cost]+ benefit)로 갱신한다. 2차..

백준 2015번 수들의 합 4 파이썬 문제 링크 - https://www.acmicpc.net/problem/2015 2015번: 수들의 합 4 첫째 줄에 정수 N과 K가 주어진다. (1 ≤ N ≤ 200,000, |K| ≤ 2,000,000,000) N과 K 사이에는 빈칸이 하나 있다. 둘째 줄에는 배열 A를 이루는 N개의 정수가 빈 칸을 사이에 두고 A[1], A[2], ..., A[N]의 순서로 www.acmicpc.net 연속하는 부분수열의 합이 K가 되는 구간의 개수를 찾는 문제였다. 주어진 수열의 순서를 바꿀 수 없었기 때문에 누적합을 우선 구하고 시작했다. 그리고 만약 수열의 크기가 작았다면 어떻게 접근했을 지 고민했다. 누적합 배열의 원소들 중 2개를 골랐을 때 차가 K인 경우의 수를 완전..

가독성이 떨어지는 것 같아 이번 글부터는 번역이 잘 안되는 부분만 참고하기 위해 영어로 작성하겠습니다. 1. Operating-System Services An operating system provides an environment for the execution of programs. User interface 대부분의 운영체제는 UI를 갖고 있다. 인터페이스는 I/O를 지시하고 메뉴에서 선택하고 텍스트를 입력하는 등의 역할을 하는 시스템이다. 인터페이스는 다양한 형태를 가질 수 있으며 일반적으로 GUI가 사용된다. 키보드와 마우스, 터치스크린을 통해 컴퓨터에 명령을 내린다. 또 다른 인터페이스에는 command-line interface(CLI)가 있다. 사용자가 텍스트를 통해 명령을 내리는 방법이..