![]()
문제 출저 https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 문제 풀이 주어진 예산을 최대로 쓰는 상한액을 구하는게 이 문제의 요구사항입니다. 상한액을 구하기 위해 이분 탐색을 활용했습니다. int[] board에 주어진 값을 담았습니다. 이분 탐색을 위해 상한액의 범위를 int s, int e로 선언했습니다. int s 는 가장 작은 값으로 0을 했습니다. 상한액의 최대 한도(e)는 주어진 예산 값 중 가장 큰 값으로 했습니다 while(s
![]()
문제 출저 https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 문제 풀이 배열이 주어지고 배열의 다른 숫자로 배열의 숫자를 만들면 좋다 라고 합니다. 주어진 배열이 몇 개의 좋다가 있는지 구하는게 이 문제의 요구사항 입니다. 투 포인터로 문제를 풀었습니다. 다른 숫자이므로 투 포인트가 같으면 넘기는 조건을 추가했습니다. 소스 코드 package baekjoon.backjoon9.day15; import java.io.BufferedReader; import java.io.IO..
![]()
문제 출저 https://www.acmicpc.net/problem/12738 12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 문제 풀이 가장 긴 증가하는 부분 수열 2처럼 이분 탐색으로 대처해가면서 문제를 풀었다. 다만 이번에는 숫자의 범위가 음수여서 처음에 넣은 기본값을 0 이 아니라 Integer.MIN_VALUE 로 넣었습니다. 소스 코드 package baekjoon.backjoon9.day14; /* 가장 긴 증가하는 부분 수열 3 https://www.acmicpc.n..
![]()
개요 Redis는 인메모리 데이터 저장소로 서버가 내려가면 데이터가 소실된다는 단점을 가지고 있습니다. 이를 극복하기 위해 Redis는 데이터를 복구할 수 있는 AOF 방식과 RDB 방식을 지원합니다. 이번에는 RDB 방식에 대해 공부한 내용을 정리해보겠습니다. RDB 특징 RDB는 특정 시점에 스냅샷을 찍어 저장하는 방식입니다. 설정 파일을 통해서 자동으로 저장하게 할 수 있고 SAVE, BGSAVE 명령어를 사용하여 수동으로 저장할 수 있습니다. RDB로 생성된 스냅샷은 dump.rdb 이름으로 생성됩니다. (설정 파일에서 이름을 바꿀 수 있습니다.) AOF와 RDB를 사용하면 AOF를 먼저 실행되고 AOF 파일이 없으면 RDB를 찾아 실행합니다. AOF 파일이 손상되거나 문제가 발생한 경우 RDB를..
![]()
개요 Redis는 인메모리 데이터 저장소로 휘발성 특징을 가지고 있습니다. 즉 예상치 못한 사고로 서버가 내려가면 Redis 에 있는 데이터도 소실됩니다. 이를 방지하기 위해서 Redis 는 데이터를 복구하는 기능으로 AOF 방식과 RDB 방식을 제공합니다. 이번 글에서는 AOF에 대해 공부한 내용을 정리해보겠습니다. AOF 특징 AOF는 Append Only File 에 약자로 Redis에 데이터가 변경되는 작업(입력, 수정, 삭제)이 실행될 때 마다 로그를 저장하는 방식입니다. Redis가 재시작할 때 AOF 파일을 순차적으로 재실행하여 데이터를 복구합니다. AOF의 파일이 너무 커지면 현재의 데이터 상태를 반영하는 새로운 AOF 파일을 재작성 합니다. 재작성을 통해 파일의 크기를 줄이고 재실행 속도..
![]()
문제 출저 https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 문제 풀이 가장 긴 증가하는 부분 수열을 구해야 한다. 다만 n이 커서 for문 돌리기에는 시간 초과가 발생합니다. 시간 단축을 위해 이분 탐색을 도입해야 합니다. 이 문제는 부분 수열의 길이를 구하는 것으로 내용물은 몰라도 되는게 핵심입니다. int[] board 배열을 만들어 주어진 배열을 담았습니다. List list를 생성하여 부분 수열을 만들었습니다. 이 때 처음에 0을 넣는다..
![]()
문제 출저 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 문제 풀이 스도쿠 판이 주어지면 빈 칸의 0에 숫자를 넣어 스도쿠 판을 완성시키는게 이 문제의 요구 사항 입니다. 백트래킹으로 모든 경우의 수를 대입하여 문제를 풀었습니다. 0의 자리에 1~9까지 숫자를 대입하며 스도쿠의 조건을 만족하며 계속해서 탐색해나가는 식으로 문제를 풀었습니다. 소스 코드 package baekjoon.backjoon9.day12; /* 스도쿠 https://ww..
![]()
문제 출저 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 문제 풀이 별들의 좌표가 주어진다. 별들의 거리는 직각 삼각형 공식으로 구할 수 있다. 이 때, 모든 별들을 연결했을 때 가장 적은 거리가 무엇인지 구해야한다. 이 문제는 최소 스패닝 트리로 크루스칼 알고리즘으로 풀었다. 먼저 PriorityQueue pq를 선언하였다. 이 PriorityQueue는 두 별의 거리를 저장하는 용으로 거리를 오름차순으로 정렬했다. dot에는 int s, i..
![]()
개요 이번에는 Write Back 혹은 Write Behind 라고도 불리는 지연 쓰기 전략에 대해 적어보겠습니다. Write Back은 Write Through 처럼 데이터의 변경(수정, 삭제 등)이 일어날 때 캐시를 최신화, 일관성을 유지하는 전략입니다. 다만 다른 점은 Write Through는 캐시 데이터를 변경하면서 동시에 DB에 변경 사항을 반영하는데 Write Back 전략은 변경 사항을 모았다가 한 번에 DB에 반영합니다. 이 방법은 높은 트래픽 상황에서 응답 시간을 최적화 하는데 유용하지만 데이터 손실 위험이 있습니다. 장점과 단점 장점 빠른 응답 시간: 쓰기 요청에 대한 응답은 캐시 업데이트 후 즉시 반환되므로, 사용자에게는 빠른 응답 시간이 제공됩니다. 배치 처리의 효율성: 여러 쓰기..
![]()
문제 출저 https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 문제 풀이 용액의 양이 주어질 때 두 개를 섞어 0에 가까운 두 개의 용액을 찾는 것이 이 문제의 요구사항 입니다. 이 문제를 풀기 위해 투 포인터를 사용했습니다. 정렬된 배열에 처음(s)과 끝(e)으로 투 포인터가 시작됩니다. 두 개를 섞었을 때 0보다 크면 e-1 하여 값을 줄이고 0보다 작으면 s+1 하여 값을 키웁니다. 이것은 s가 e를 만날 기 전 까지 계속 반복합니다. ..
![]()
개요 저번 시간에 Cache-Aside 와 Read Through를 통해 조회할 때 Redis에 캐싱된 정보를 한 번 찾고 Redis에 없으면 DB에서 가져오는 것을 배웠습니다. Cache에서 가장 중요한 것은 데이터가 변경(등록, 수정, 삭제) 될 때 그 내용을 반영하여 항상 최신화를 유지하는 것 입니다. Write Through 전략은 이 최신화를 유지하기 위한 전략으로 데이터를 Cache와 DB에 동시에 저장하는 방식입니다. 이는 캐시와 DB 간에 데이터 불일치가 발생해서는 안되는 상황에서 사용됩니다. 장점 / 단점 Write Through의 주요 장점은 Cache와 DB 사이에 데이터 불일치가 크게 줄어드는 것 입니다. 단점으로는 데이터를 두 군대에 기록하므로 쓰기 작업 성능이 느려질 수 있는 것..
![]()
문제 출저 https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 문제 풀이 정점의 개수(n)가 주어지고 정점을 잇는 선분(m)이 주어집니다. 이 때, 사이클이 몇 번째 순서에서 이루어지는지 구하는게 이 문제의 요구 사항입니다. 이 문제를 풀기 위해 Union-Find를 도입했습니다. 선분이 주어지면 각 시작과 끝의 부모를 비교하여 부모가 같으면 사이클이 이루어진거여서 순서를 저장하고 출력합니다. 부모가 같지 않다면 부모를 같게 만들어줍니다. 이..
