전체 글

시간 복잡도 줄이는 기술 5. +1-1 technique

+1-1 Technique N개의 선분을 2개의 시작, 끝 정점으로 나눠 각각 +1, -1 가중치를 줘서 x가 증가하는 순서대로 정렬하는 방법을 +1 -1 Technique 예시 - 수직선 상 겹치는 구간 문제 - 가장 많이 겹치는 구간 일직선 위에 n개의 구간이 주어졌을 때, 구간이 가장 많이 겹치는 부분에서 몇 개의 구간이 겹치는지를 구하는 프로그램을 작성하세요. 아이디어 먼저, 배열을 생성해서 선분이 있는 구간마다 1을 더해 최댓값을 구하는 식은 시간초과가 났다. → 선분의 구간을 for로 돌며 1을 더하는 것이 문제 선분의 시작점과 끝점에 +1,-1을 한다. 모든 점마다 겹치는 선분을 세줌 코드 n=int(input()) arr= [tuple(map(int,input().split())) for ..

시간 복잡도 줄이는 기술 4. LR 배열

마라톤 중간에 택시타기 마라톤 코스는 N개의 체크포인트로 구성되어 있으며, 1번 체크포인트에서 시작해서 모든 체크 포인트를 순서대로 방문한 후 N번 체크포인트에서 마라톤이 끝납니다. 게으른 개발자 A는 막상 대회에 참가하려 하니 귀찮아져서 중간에 있는 체크포인트 한 개를 몰래 건너뛰려 합니다. 단, 1번 체크포인트와 N번 체크포인트를 건너뛰면 티가 많이 나기 때문에 이 두 체크포인트는 건너뛰지 않으려고 합니다. 개발자 A가 체크포인트 한 개를 건너 뛰어서 마라톤을 완주하려고 할 때, 최소 거리를 구하는 프로그램을 작성해보세요. 단, 거리 계산은 ∣x1−x2∣+∣y1−y2∣ 로 계산하는 것을 의미합니다. 또한, 체크 포인트의 좌표는 겹쳐져 주어질 수도 있으며, 이 경우 개발자 A가 체크포인트를 건너뛸 때 ..

시간복잡도를 줄이는 기술 3. 전처리 - 숫자들의 합이 7의 배수

문제 N개의 서로 다른 숫자가 차례대로 주어집니다. 이들 중 연속하게 고른 숫자들의 합이 7의 배수가 되게 그룹으로 묶으려 합니다. 이렇게 만든 그룹 중 최대 크기를 구하는 프로그램을 작성해보세요. 아이디어 기록하는 새로운 배열을 만들어 해결하는 것이 포인트 합 배열을 구한다.(Prefix_sum) 맨 뒤 (모든 수의 합)에서 부터(for i range(N,0,-1) - 맨 앞의 수( for j in range(0,i)를 을 빼가며 7의 배수인지 체크한다. 만약 7의 배수가 있다면, for j 를 탈출한다. (앞에서 부터 돌기 때문에, 가장 큰 그룹이다. 뒤에는 돌 필요 X) 코드 N=int(input()) arr= [0] # 합 배열을 구한다. # 맨 뒤에서 부터 for _ in range(N): ar..

Redis cache 설정 (Node.js)

출처: https://inpa.tistory.com/entry/REDIS-📚-Redis를-클라우드로-사용하자-Redislabs [Inpa Dev 👨‍💻:티스토리] [REDIS] 📚 Node.js 에서 redis 모듈 사용법 (캐싱 & 세션 스토어) Node 프로젝트에서 pm2로 다중 클러스터 인프라를 구축했다면 세션 불일치 문제가 생기게 마련이다. 만일 서버가 종료되어 메모리가 날라가면 접속자들의 로그인이 모두 풀려버리게 된다. 따라서 inpa.tistory.com 이 분의 글을 토대로 작성했다. 이분의 글에는 redis 설정 뿐만 아니라 캐싱 전략이나 redis로 세션관리를 하여 복수 서버 환경(클러스터링)에서도 세션을 공유할 수 있는 방법이 나와있어 도움이 많이 된다! 1. Redis Labs 로 클..