문제 파악https://www.acmicpc.net/problem/1937풀이이 문제는 각 칸마다 상하좌우로 이동하면서 나무의 값이 더 큰 칸으로만 이동할 수 있으며, 이는 DFS로 탐색하였다.각 시작점으로부터의 경로에서는 나무의 개수가 무조건 증가해야 하므로 한 번 최대 경로를 구하게 되면 추가 연산이 불필요하다.따라서 주어진 대나무 숲과 일치하는 depth[N][N] (r,c 시작점으로부터 판다의 경로 최대값) 배열을 선언해 메모이제이션에 사용했다.이 둘을 혼합하면 DFS 과정 중의 중복 탐색을 방지해 복잡도를 줄일 수 있게 된다.또한 DFS 과정은 재귀를 사용했다.depth[r][c] == 0 일때 depth[r][c] 리턴다음 위치(상/하/좌/우)의 최대 깊이 연산(혹은 참고)후 (r,c) 위치 ..

문제 파악https://www.acmicpc.net/problem/1174풀이조합보다는 BFS(Queue)를 사용하여 구현하면 더 쉽고 간단하게 풀이할 수 있다.큐에 적재하는 숫자는 다음과 같다.0---110--220-- 21210-330-- 31310- 32320- 3213210...990-- 91910- 92920- 92192101열(0,1,2,3...,9), 2열(10,20,21,30...98), 3열(210,310,...987), ... 순서대로 큐에 적재된다.poll 한 원소의 끝 자리(poll%10)보다 작은 숫자를 붙여 다시 큐에 적재해준다.예를 들어 만약 93이 최신 숫자였다면, 다음 뎁스의 감소하는 숫자는 [930, 931, 932]이 되겠다.또한 FIFO로 순서가 보장되기 때문에 큐..

들어가며트랜잭션 경합이 빈번하거나 분산 환경에서 동시성 문제가 발생할 수 있는 상황에서,RDB에 의존하는 낙관적 락 대신 독립적인 외부 분산 락 시스템을 사용하는 것에 관심이 생겼다.이번 기회에 정리하며 적용해보고자 한다. Redisson의 장점Redis 클러스터, Sentinel 환경과의 호환성까지 갖춰 운영 환경에서도 안정적으로 사용할 수 있다.Java 생태계에 친화적이며, elasticcache 등 redis 인프라가 이미 구축된 경우 쉽게 확장 가능하다.Lettuce, Jedis보다는 RLock, RReadWriteLock, RedLock, Watchdog(락 재연장) 등 제공하는 기능이 다양하다.Redisson 구조Redisson Lock 종류Redisson에 사용되는 락 종류는 가장 하단 추상..

문제 파악https://www.acmicpc.net/problem/12970풀이문제가 꽤나 간단해보인다만,, 완전탐색(재귀)로 풀면 시간초과가 발생한다. O(N^2)잘 들여다보면 규칙을 찾을 수 있다.A를 기준으로 뒤에 있는 B의 개수만 신경쓰면 된다. ex) AABB = [2, 2, -, -] = 4이 규칙을 활용해 정답 문자열을 만들어 보았다.모든 자리수를 B로 채우고, 0부터 N-1 번째 자리수를 돌며 k를 업데이트하는 방향으로 구현하면 좀 더 직관적이다.좀 더 쉽게 이해하기 위해 n = 10, k = 20이라고 가정하여 아래 과정을 만족하고자 했다.i [0,n)순환 인덱스pairCounti번째 자리수가 B->A로 바뀔때 만족하는 추가 순서쌍 수k남은 순서쌍 수targetIdxaCounts[i]09..

문제 파악https://www.acmicpc.net/problem/1301풀이모든 상태를 해시맵에 담는 방법으로 풀이했더니, OOM이 발생했다 😇N의 범위 [3,5]가 상당히 한정적이므로 다차원 배열을 선언해 상태를 저장하기로 결정했다.(참고로 최대 개수인 5로 고정해 연산을 진행하였다.)또 3개가 연속하면 안 되는 제약조건 때문에 [마지막에서 두 번째 구슬 종류][마지막 구슬 종류]도 DP 배열에 반영해야 한다.그러므로 DP 배열은[1번째 구슬 개수][2..][3..][4..][5번째 구슬 개수][마지막에서 두 번째 구슬 종류][마지막 구슬 종류]로 7차원 배열을 가진다.DP 배열만 잘 선언해주면, 나머지는 풀이가 그렇게 어렵지는 않다.이미 계산한 상태(문제)의 결과를 저장해 두고, 같은 계산을 다..

문제 파악https://www.acmicpc.net/problem/1039풀이문제는 주어진 수 N의 자릿수 중 두 자리를 최대 K번까지 바꾸어가장 큰 수를 만드는 문제다.단, 교환 결과의 수가 0으로 시작하면 안 되며, 숫자 자리수가 1개인 경우 교환 자체가 불가능하다.최대 depth가 K인 트리를 탐색하는 문제라고 판단했다.BFS로 탐색하기로 결정했으며,동일한 depth(교환 횟수)의 문자열의 중복을 제거하는 것이 핵심이라고 생각했다.이 문제에서는 중복 제거를 위해 Map 자료구조를 활용했다.사용한 Map은Key : 교환 횟수 [0, K]Value : 해당 횟수에서 만들 수 있는 수들을 저장하는 집합 (Set)로 구성된다.BFS 탐색을 위해 큐를 순회하며 다음 depth에 위치를 바꾼 문자열을 삽입한다..