분류 전체보기

[Python] 백준 13335번 - 트럭

문제: https://www.acmicpc.net/problem/13335 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 구현문제라 문제에서 요구하는 사항들만 제대로 넣어주면 제대로 동작한다. 나는 다리에 올라가기 전의 트럭(truck), 다리 위의 트럭(bridge), 다 건넌 트럭(done)을 각각 만들어 풀었다. (사실 done은 없어도 된다. 그리고 트럭은 앞 차부터 빠져나가기 때문에 리스트에서 빼기 쉽게 queue를 활용해 풀이했다. from colle..

[Python] Set과 List의 시간 복잡도 차이

코딩테스트 공부를 하는데, List를 사용하면 시간 초과가 나왔던 문제가 Set을 사용하자 통과가 됐었다. 관련 포스팅: https://jjung0326.tistory.com/65 [Python] 백준 1987번 - 알파벳 문제: https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 jjung0326.tistory.com 이유는 List에서 x in s 연산을 하면 O(n)시간이 걸리는 반면 Set에서 x in s 연산을 하면 O(1)시간이 걸리기 때문이다. 이러한 차이가 생기는 이유가 뭘까? 이유는 Python에서 Se..

[Python] 백준 1987번 - 알파벳

문제: https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 문제를 보고 한 루트를 깊이 있게 팠다가 다른루트를 파기 때문에 가장먼저 DFS가 떠올랐다. DFS대로 풀면서 백트래킹문제라는걸 알게되었다. 처음에는 좌표에 대한 visited과 visited된 알파벳에 대해 각각 조회해주어야 한다고 생각했다. 그런데 생각해보니 어차피 4방향의 근접 알파벳 조회여부를 돌기때문에 좌표에 대한 visited는 따로 둘 필요가 없겠다는걸 알았다. 처음 제..

[시스템 설계] 무상태(stateless) 웹 계층

시스템의 웹 계층을 수평적으로 확장시키려면 웹 서버에서 상태 정보(세션데이터 등)을 제거해야 한다. 만약 상태정보를 가진 채로 웹 계층이 동작하면, 다음과 같은 일이 발생한다. 사용자가 http요청을 통해 웹에 접속하려고 할 때, 해당 사용자에 대한 상태 정보가 존재하는 서버에만 요청을 해야 결과 값이 반환된다. 로드밸런서는 이러한 기능을 지원하기 위해 고정 세션(sticky session)이라는 기능을 제공하지만, 이는 LB에 부담을 준다. 또한 특성 서버에만 부하가 몰리는 문제가 생길 수 있다. 이러한 문제에서 벗어나기 위해 무상태(stateless) 아키텍처를 구성한다. 웹 계층에서 상태 정보를 떼어내 RDBMS나 NoSQL과 같은 공유 저장소(shared storage)에 저장하고, 필요할 때 가..

캐시 전략 (Cache Strategy) 종류

캐싱은 시스템 성능을 높이는 방법 중 하나이다. 캐시를 통해 데이터베이스 부하를 줄이고 빠른 응답속도를 가져올 수 있다. 캐싱을 하는 방법과 종류가 다양한데, 데이터의 유형마다 이를 달리하여 적절한 캐시 방식을 구현하는 것이 좋다. 먼저 두가지의 읽기 정책을 알아보자. 1. Cache-Aside 동작방식 읽기 요청이 들어오면, 애플리케이션이 캐시에 해당 데이터가 있는지 확인한다. 캐시가 있는 경우, Cache Hit이 일어나고 조회가 끝난다. 캐시가 없는 경우, Cache Miss가 일어나고 DB에 조회를 한다. 애플리케이션이 DB에서 데이터를 가져온 후 캐시에 직접 저장한다. (주체가 애플리케이션) 해당 방식을 사용하게 되면, 캐시서버가 죽어도 애플리케이션이 직접 DB에 접근하기 때문에 캐시오류에 탄력..

[Python] 백준 9205번 - 맥주 마시면서 걸어가기

문제 https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 처음 문제를 풀 때는 왜 bfs로 풀어야하는지 몰라서 일반 구현처럼 요구사항대로 풀었다. # Try #1 t = int(input()) for _ in range(t): n = int(input()) start = list(map(int, input().split())) conv = [] for _ in range(n): conv.append(list(map(int, input().sp..

[시스템 설계] 서버 응답시간(latency) 개선 (캐시, CDN)

서버 응답시간은 캐시를 붙이고, 정적 컨텐츠를 CDN으로 캐싱하여 개선할 수 있다. 캐시 캐시는 자주 참조되는 데이터를 캐시 서버에 임시 저장하여 요청이 빨리 처리될 수 있도록 하는 저장소이다. 캐시를 사용하면 DB의 부하가 줄어들어 어플리케이션 성능을 향상시킬 수 있다. 다만 캐시 사용시 아래 사항을 고려해야 한다. 캐시 만료 정책: 너무 짧으면 DB에 자주 접근하게 되고, 너무 길면 데이터가 원본가 차이 날 수 있다. 캐시는 TTL(Time To Live)에 명시된 기간동안 캐싱된다. 일관성 유지: 데이터의 원본과 캐시 사본은 같아야 한다. 저장소의 원본을 갱신하는 연산과, 캐시 업데이트 연산이 동시에 일어나지 않으면 이 일관성은 깨질 수 있다. 캐시 서버 분산: 캐시서버를 한대만 두면 Single ..

[시스템 설계] Failover 시스템 설계

가상면접 사례로 배우는 대규모 시스템 설계 기초 책을 읽고 이해한 내용을 글로 정리하고자 포스팅 한다. 책 내용은 단일 서버부터 시작해서 사용자가 늘어나면 이것도 필요하고, 저것도 필요하고.. 이런식으로 점점 살을 붙여나간다. 책의 흐름과 동일하게 점점 고도화된 시스템을 설계하는 구조로 정리해보려고 한다. 단일 서버 단일 서버는 위와 같이 구성한다. 웹, 데이터베이스, 캐시 등이 모두 단일 서버 1대에서 실행된다. 단일 서버의 동작방식은 다음과 같다. 1. 사용자가 DNS서버에 질의 2. DNS 서버에서 도메인 네임에 대한 IP 반환 3. IP주소로 서버에 HTTP 요청 4. 서버에서 응답 반환 데이터베이스 사용자가 늘어나면 단일서버로는 감당하기가 어려워진다. 따라서 서버를 웹 트래픽 처리 용도(웹 서버..