https://www.acmicpc.net/problem/2152문제조건  총 M(1 ≤ M ≤ 100,000)개의 비행로가 존재각각의 비행로는 한 방향으로의 서비스만을 제공S(1 ≤ S ≤ N)번 도시에서 시작해서 T(1 ≤ T ≤ N)번 도시에서 여행을 끝냄  최대로 방문할 수 있는 도시의 개수 각각의 도시는 여행 중에 몇 번이든 방문할 수 있으며, 같은 항공로를 여러 번 이용할 수도 있다.접근방법 문제를 읽고 나서 든 생각은 띠용(?) 이게 뭐야,,, 였다,,문제 조건중 몇 번이든 같은 도시를 방문할 수 있다는 점을 이해하기가 어려웠다.그리고 같은 항공로를 여러 번 이용한다는 말에서 조금 감이왔다. "이거 순환이 될수 있으니까 뭔가 묶어볼수 있지않을까?"우연치 않게 학교 강의에서 들었던 SCC(S..

https://www.acmicpc.net/problem/16946 문제조건N×M의 행렬로 표현되는 맵0 : 이동가능, 1 : 벽각각의 벽에대해 해당 벽을 부수고, 이동가능한 장소로 바꾼뒤 그 위치에서 이동가능한 칸의 개수접근방법 처음에는 정말 단순하게 모든 벽에 대해서 BFS를 돌렸다가 시간초과가 났다.최악의 경우 1000^3 이면 10억인데,, 대략 10초가량 소요되는 것이다.그래서 어떻게 하면 시간을 줄여가며 해결할까 고민 한 결과,,, visited 배열을 각각 벽에대해 초기화 시켜주는 작업을 안해주면 시간제한에 안걸릴것이라고 생각했다. 그래서 벽을 탐색하는 것이아니라, 맵에서 이동가능한 부분인 0인 값에서 부터 BFS를 진행해서 인접한 벽에 누적으로 값을 더하고, visited배열을 초기화해줄 ..

2024.05.08 - [Spring/대용량 트래픽] - Redis Cache로 실습하기 Redis Cache로 실습하기2024.05.07 - [Spring/대용량 트래픽] - Redis Cache 이론 Redis Cache 이론2024.05.07 - [Spring/대용량 트래픽] - Redis Key, Scan 명령어 Redis Key, Scan 명령어2024.05.07 - [Spring/대용량 트래픽] - Redis Transactions Redis Transactlsdiary.tistory.com 이전글에서는 Redis를 Cache로 활용해서 실습을 진행했다.근데 사실 Spring 자체에 Redis를 위한 코드들이 준비가 되어있다. 이 코드들에 대해서 알아보도록하자.https://start.spri..

2024.05.07 - [Spring/대용량 트래픽] - Redis Cache 이론 Redis Cache 이론2024.05.07 - [Spring/대용량 트래픽] - Redis Key, Scan 명령어 Redis Key, Scan 명령어2024.05.07 - [Spring/대용량 트래픽] - Redis Transactions Redis Transactions2024.05.03 - [Spring/대용량 트래픽] - Java에서 Redis 명령어 Javalsdiary.tistory.com 이제 실제 Java로 코딩을 해보겠다.들어가기에 앞서 사전 준비가 필요하다. Docker기반 Mysql 8.0 필요 SpringBoot 프로젝트Redis설치와 마찬가지로 Docker Official Images 를 사용하면..

2024.05.07 - [Spring/대용량 트래픽] - Redis Key, Scan 명령어 Redis Key, Scan 명령어2024.05.07 - [Spring/대용량 트래픽] - Redis Transactions Redis Transactions2024.05.03 - [Spring/대용량 트래픽] - Java에서 Redis 명령어 Java에서 Redis 명령어2024.04.30 - [Spring/대용량 트래픽] - Redis 다양한 데이터 타입lsdiary.tistory.com  Cache 일시적으로 데이터를 저장하는 고속처리를 위한 임시저장소. 빠른 응답속도를 위함.활용예시CPUL1 Cache : 각 코어별L2 Cache : 모든 코어가 공유ApplicationDB, 외부 API요청 : 무거운 쿼..

2024.05.07 - [Spring/대용량 트래픽] - Redis Transactions Redis Transactions2024.05.03 - [Spring/대용량 트래픽] - Java에서 Redis 명령어 Java에서 Redis 명령어2024.04.30 - [Spring/대용량 트래픽] - Redis 다양한 데이터 타입 알아보기 Redis 다양한 데이터 타입 알아보기2024.04.05 - [Spring/lsdiary.tistory.com 이전 글은 Redis에서 트랜잭션에 대해 알아봤다.명령어를 이야기 하기 전에 우선 Redis는 Single thread로 동작한다(순차 처리).빠른 응답속도로 처리되는 in-memory의 장점이 사라진다. 그래서 장점을 살리기 위해서 대부분의 Redis 명령어는 시..

2024.05.03 - [Spring/대용량 트래픽] - Java에서 Redis 명령어 Java에서 Redis 명령어2024.04.30 - [Spring/대용량 트래픽] - Redis 다양한 데이터 타입 알아보기 Redis 다양한 데이터 타입 알아보기2024.04.05 - [Spring/대용량 트래픽] - Redis CLI 실습lsdiary.tistory.com이전까지 Redis CLI를 통해서 다lsdiary.tistory.com이전 글에서 Java에서 기본적인 Redis 명령어들에 대해 알아봤다.Transaction 우선 이번에 얘기할 내용을 다루기 전에 트랜잭션이 무엇인지 부터 알아야한다.트랜잭션이란? IT업계 입장에서 본다면 거래 or 처리의 단위라는 의미이다.몇개의 예시를 보자HTTP Trans..

오늘도 어김없이 팀프로젝트가 있어서 내가 할 부분 프로그래밍 하고, 깃허브에 푸시하려고 하는데, 갑자기 깃허브 계정 복구한지도 얼마 안됐는데, 벌써 부터 짜증나게한다 아무튼 push하고 저런 경고문이 뜨고 다시 로그인 하라고 한다. 당연히 된줄 알았는데, 계속 반복해서 로그인 창만 뜨고 똑같이 깃허브와 연동이 안되어있다는 말만 반복한다. 그래서 한번 찾아봤다.GitHub 토큰 만료 예~전에 토큰 발급받아서 연동 잘해서 썼던 기억이 어렴풋이 나긴한다. 우선 GitHub 나의 프로필로 들어가고 settings로 들어간다.그러면 위처럼 여러 목록이 있을건데 Developer settings로 들어가주자.들어가면 아래와 같은 화면이 나오는데, Tokens (classic)에서 오른쪽 상단에 보이는 Generat..

https://www.acmicpc.net/problem/2234 문제조건 굵은 선은 벽을 나타내고, 점선은 벽이 없어서 지나다닐 수 있는 통로서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, 동쪽에 벽이 있을 때는 4를, 남쪽에 벽이 있을 때는 8을 더한 값이 주어진다.이 성에 있는 방의 개수가장 넓은 방의 넓이하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기를 각각 구하시오접근방법 전체 맵을 탐색한다는 점에서 BFS를 떠올릴 수 있었고, 1(2^0), 2(2^1), 4(2^2), 8(2^3) 로 진행할수 있는지 판단해야한다는 점에서 나에겐 조금 생소한 비트마스킹이 생각났다. 이 문제에서 핵심은 비트를 1부터 왼쪽으로 Shift연산을 통해 벽에 대해 나타낸 숫자와 &연산으로 겹치는 지..

https://www.acmicpc.net/problem/2580 문제조건스도쿠판을 채우자각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.접근방법 문제를 보자마자 떠오른 생각은 N-Queen 문제와 상당히 유사한 문제라는 생각 이었다. 물론 Brute Force로 모든 경우의 수를 탐색해서 구할 수도 있겠지만, O(2^n) 이상의 시간소요로 시간초과가 날 것이 분명했고, N-Queen문제와 같이 백트래킹으로 접근했다.유망한지 판단하고, 유망하다면 DFS를 진행하는 백트래킹 방식에서 시간단축이 됨을 인지하고, 가로, 세로, 3x3 크기의 칸에서 같은 숫자가 하나도 없는지 체크하고 그..