본문 바로가기

전체 글178

비관적 락으로 동시성 문제 해결하기 (Spring Data Jpa, Kotlin) 환경언어 : Kotlin프레임워크 : Spring Boot 3.0.xDB : Oracle 19c트랜잭션 격리수준 : READ COMMITTED문제 개요이번에 리뷰 신고 기능을 개발하게 되었습니다.세부적인 요구사항은 리뷰 신고가 5개 쌓였을 때 리뷰가 삭제되도록 하는 것입니다.이 기능을 애플리케이션 계층에서 구현하게 되었을 때 대략 다음 흐름을 가집니다.리뷰 신고 개수를 조회신고 개수로 판단2-1. 개수가 임계값을 넘어서면 리뷰 제거2-2. 개수가 임계값 이하라면 리뷰 신고 저장동시성 문제 발생 상황조회와 판단을 할 때 다른 트랜잭션끼리 동시성 문제가 발생할 수 있습니다.A, B 트랜잭션 두 개가 동신에 리뷰 신고를 요청합니다.A, B가 동시에 리뷰 신고 개수를 조회하는데이 때 A, B 트랜잭션에서 캡쳐한.. 2024. 10. 1.
leetcode 1024 Stone Game II (DP, Java) 문제 링크문제 요약n([2,7,9,4,4]A, B 가 있으면 게임을 합니다.게임의 내용은 턴제 게임으로 자신의 턴일 때 마다 돌무더기를 가져갑니다.각 턴에 가져올 수 있는 돌무더기의 수는 (1 다음 턴이 될 때 m 은 max(m, x) 로 최신화됩니다.A, B 는 각자 자신의 턴에 최선의 수를 판단합니다.문제 풀이이 문제는 DP 문제이다. 어떻게 판단할 수 있을까요.. 처음 문제를 읽었을 땐 이게 어떤 유형의 문제인지 감이 안잡힐 것입니다. 이럴땐 먼저 brute force 로 접근하는 것입니다.private int rec(int i, int m, int n, int[] suffixSum) { if (i + 2 * m >= n) return suffixSum[i]; int result = 0;.. 2024. 9. 30.
[Algospot] SOLONG 안녕히, 물고기는 고마웠어요! (Python, Trie) [문제 링크](https://www.algospot.com/judge/problem/read/SOLONG)이 문제는 타이핑 시 **빈도가 잦은 문자를 추천**하는 기능을 구현하는 문제입니다.### 제약조건**입력**사전에 포함된 단어의 수 N (1 입력할 단어의 수 M (1 그 후 N 줄에는 한 줄에 하나의 문자열과 정수로 사전에 포함된 단어와 해당 단어의 출현 빈도가 **사전 순서와 무관**하게 주어집니다. **같은 단어가 두번 이상 주어지는 일은 없으며**, 출현 빈도는 1 과 10만 사이의 정수입니다. 그 다음 줄에 M개의 단어로 입력할 문자열이 주어집니다. **모든 단어는 알파벳 대문자이며, 길이는 최대 10입니다.**### 핵심내용단어의 접두사부터 시작해 접미사를 찾아내는데는 `Trie` 가 적.. 2024. 9. 25.
[Algorithm] Trie (Python code) Trie많은 문자열 데이터들이 있을 때 이를 효율적으로 다룰 수 있게 해줍니다.단편적 예시로는 영어사전이 있습니다.아래와 같은 데이터가 있습니다. APPLEAPPLYBANANAKIWI 이 데이터에서 특정 문자열이 이미 존재하는지 찾는다 가정할 때단순한 방식으로는 특정 문자열을 모든 문자열과 비교하는 방법이 있습니다.이 때 시간복잡도는 (국어사전의 모든 문자열의 수 x 특정 문자열의 길이) 이 됩니다. 하지만 Trie 를 사용하게 되면 특정 문자열의 길이만으로 평가할 수 있습니다.Trie 는 최상위 노드부터 시작해 공통적인 경로는 하나의 경로로 관리합니다.APPLE, APPLY 로 예를 들자면 APPLE 과 APPLY 는 APPL 이라는 공통경로를 가집니다.   동작동작은 크게 insert, find 두 .. 2024. 9. 25.
Rotate Matrix Rotate Matrix구현문제 중엔 Rotate Matrix 류가 있습니다. nxm 행렬을 주고 이 행렬을 90도 방향으로 회전시키게 하는 문제들입니다.구현 시 팁, 주의점테두리 단위로 회전을 시킵다. 바깥 테두리부터 회전을 시켜 내부의 테두리들을 재귀적으로 호출하고 테두리가 1이나 0인 경우가 기저케이스가 됩니다.먼저 Swap 기능을 구현할 때처럼 덮어씌워짐에 의해 정보유실이 일어날 수 있어 추가적인 공간에 한 행을 저장시킵니다.그 다음 문제의 요구에 맞게 값들을 이동시켜줍니다. 이 때 인덱스 계산이 꽤 복잡할 수 있습니다.팁을 드리자면 시작좌표(y, x), 행렬길이가 필요합니다.값들의 이동 순서는 아래 이미지에서 볼 수 있듯 빨강부터 시작해 마지막에 주황이 처리될 수 있도록 해야합니다.이미지에서도 .. 2024. 9. 23.
[Thymeleaf decoupled logic] Fragment detection Error 상황 서버를 주로 담당하고 있는 제가 뷰 관련된 html 문서를 작성하고 있습니다. 대부분의 요소들을 모달 형식으로 만들다보니 메인 html 의 크기가 계속해서 커져 이를 요소별(영역별)로 나누고 싶었고 익숙한 Thymeleaf 를 사용하였습니다. 이후 다른 프론트엔드 분에게 인계할 시 Thymeleaf 의 코드가 html 문서에 남아있으면 좋지않을 것이라 생각하여 decoupled logic 을 사용하였습니다. 문제 각 영역을 Fragment 로 분리한 다음 메인 html 의 해당 영역에 replace 하려하니 Fragment 를 잘 찾지 못했습니다. 에러 로그 org.thymeleaf.exceptions.TemplateInputException: Error resolving fragment: "~{u.. 2024. 4. 6.
비트마스킹 보호되어 있는 글 입니다. 2024. 4. 4.
플로이드 워셜 알고리즘 플로이드 워셜 알고리즘 모든 정점에서 모든 정점까지 이동할 때 최소 비용을 얻을 수 있는 알고리즘이다. 모든 정점 사이의 비용을 구하다보니 시간 복잡도는 O(정점의 수 ^ 3) 으로 상당히 높다. 플로우 모든 정점을 대상으로 총 3 번의 중첩 반복문을 실행한다. 가장 외부의 반복문은 이후에 나올 시작 정점, 도착 정점이 반드시 거치게 될 중간 정점을 선택한다. 그 다음 내부의 두 반복문은 시작 정점, 도착 정점을 선택한다. 이를 반복해서 모든 경우를 고려할 수 있다. 너무 생략했나.. 벨만 포드 알고리즘 과 코드만 봐도 쉽게 이해할 수 있을 것이다. 소스 코드 n = int(input()) m = int(input()) INF = float('inf') board = [[(INF, INF,.. 2024. 3. 13.

티스토리툴바