문제 파악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에 위치를 바꾼 문자열을 삽입한다..

문제 파악https://www.acmicpc.net/problem/2132풀이트리의 지름을 활용해서 푸는 문제이다.이 문제는 가중치를 트리의 지름에 반영한다는 점이 독특하다.트리의 지름이면..? DFS를 두 번 수행해야겠다 😊임의의 정점에서 시작해 가장 많은 열매를 먹을 수 있는 경로를 찾는다.이 때, 해당 경로의 종점을 저장하자. (1번째 탐색)저장해 둔 종점에서 다시 트리 순회를 시작해 가장 많은 열매를 먹을 수 있는 경로를 찾는다. (2번째 탐색).그림으로 보면 다음과 같다. 가장 긴 경로를 찾게 되면 두번째 탐색 경로가 결국 첫 번째 경로를 포함하는 형태가 나올 것이다.그러므로 두 번째 탐색 시의 시작점, 종점 중 큰 점을 가중치와 함께 반환해 주면 정답이 나온다고 판단했다.이를 코드로 풀어 내..