본문 바로가기

분류 전체보기

 (328)
Redis란? Redis 란? Key, Value 구조의 비정형 데이터를 저장하고 관리하기 위한 오픈 소스 기반의 비관계형 데이터베이스 시스템 데이터베이스, 캐시, 메세지브로커로 사용되며 인메모리 데이터 구조를 가진 저장소 입니다.Cache Server란? 데이터베이스가 있는데도 Redis라는 인메모리 데이터 구조 저장소를 사용하는 이유(?) 인메모리 데이터베이스가 아니라면 사용자가 많아 질 수록 부하가 느려집니다. ( HDD,SDD 접근 ) 과부하를 방지하기위하여 캐시 서버(Redis)를 도입한다.Look aside cache 클라이언트가 데이터를 요청 웹서버는 데이터가 존재하는지 Cache 서버에 확인 Cache서버에 데이터가 있으면 DB데이터를 조회하지않고 Cache 서버에 있는 결과값을 클라이언트에게 바로 반환..
[백준] 1038번 : 감소하는 수 https://www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 해당 문제는 다이나믹 프로그래밍으로 문제를 해결 하였습니다. N 자리수의 값을 구할때 N-1 자리수에서 가져와 이어 붙힙니다. 예를들어서30,31,32 을 (두번째자리) 구한다고하면 3보다 작은 N-1 자리수에 3을 이어붙힌 값인 310, 320, 321 입니다. [10]은 1로 시작하는 2번째 자리수, [20,21] 2로 시작하는 2번째 자리수 입니다. dp[3] = prev_dp..
[백준] 17142번 : 연구소 3 https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, www.acmicpc.net 해당 문제는 완전탐색 + 너비우선탐색 + 조합 문제로 해결하였습니다. 1. 완전탐색 : 가능한 모든 경우의 수를 다 탐색해본다 ( M개의 활성바이러스를 가질 수 있는 경우의 수를 모두 탐색해본다.) 2. 너비우선탐색 : 해당 바이러스에서 빈방으로 바이러스를 퍼트린다. (최소 거리 탐색이기때문에 너비우선탐색 선정) 3. 조합 : M개의 활성화 바이러스를 가질 수 있는 경우의 수를 모두 구한다. 생각해야할 ..
[백준] 2589번 : 보물섬 https://www.acmicpc.net/problem/2589 2589번: 보물섬 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 www.acmicpc.net 해당 문제는 메모리제이션 기법과 완전탐색, 너비우선탐색으로 문제를 해결 하였습니다. A(x1,y1), B(x2,y2) : A,B 각각 육지일때 dp[x1][y1][x2][y2] = 최소거리 1. 2중 for문으로 육지일때 각각의 육지에 대한 거리를 계산하여 dp 테이블에 넣습니다. 2. 육지의 그룹이 2개 이므로, 해당 육지내에서만 이동할 수 있으므로 조합을 생성하여 조합중 거리의 최대값을 리턴하면 ..
[백준] 1068번 : 트리 https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 자기자신으로부터 방문할 수 있는 노드를 graph의 배열에 넣어둔뒤, 루트노드로부터 자식 노드들을 방문해가면서 각각의 노드들의 자식노드가 0일경우 cnt값을 증가시켜 문제를 해결 하였습니다. 루트노드가 지워진 노드일경우는 트리 자체가 사라지기 때문에 0으로 예외사항을 추가 했습니다. N = int(input()) nodeInput = list(map(int ,input().split())) ..
[백준] 16638번 : 괄호 추가하기 2 https://www.acmicpc.net/problem/16638 16638번: 괄호 추가하기 2 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net 해당문제는 식에다가 괄호를 추가하지 않거나 추가했을때의 모든 경우의수의 값을 구하여 최대값을 구하는 문제로 완전탐색, 구현 문제 입니다. 연산자의 우선순위는 곱하기가 제일 우선순위가 높고 그다음에 빼기, 더하기 임으로 곱하기는 괄호를 해도 식에 결과에는 상관이 없기때문에 곱하기 연산자는 무시합니다. 또한 빼기 더하기 연사자에 괄호를 추가할때 이전에 있던 연산자에 괄호가 추가되어..
[백준] 1285번 : 동전 뒤집기 https://www.acmicpc.net/problem/1285 1285번: 동전 뒤집기 첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위 www.acmicpc.net 해당 문제는 브루트포스 + 비트마스킹으로 문제를 해결 하였습니다. 행을 먼저 뒤집은뒤 -> 열을 뒤집어보며 최적의 개수를 구합니다. 행을 뒤집은 경우와 뒤집지 않은 모든 경우의 수를 구합니다. 2^N의 경우의수가 나오는데, 이 모든 경우의 수를 각각의 테이블을 구한다면 메모리 복잡도와, 시간복잡도로 해결 할 수 없습니다. 그래서 각 행을 뒤집었는지 뒤집지 않았는지 비트마스킹을 활용합니다. 모든..
[백준] 1929번 : 소수 구하기 https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 해당 문제는 에라토스테네스의 체와 소수를 제곱근까지 확인하여 구하는 방식으로 시간복잡도를 최적화 할 수 있다. 우선 소수를 구할때에 제곱근까지 구하는 방식을 사용한다. 예를들어 20의 소수를 구할때 2부터 20까지 모든 수를 나누어 보면서 나누어 떨어지는지 나누어 떨어지지 않는지 확인하며 소수인지 아닌지 판별한다. 그러나 이 문제는 모든 수를 확인해야 함으로 O(n)의 시간 복잡도가 든다. 그러나 모든 수를 확인하지 않고 제곱수..

티스토리툴바