https://www.acmicpc.net/problem/3015모노톤 스택모노톤 스택은 스택의 요소가 오름차순 또는 내림차순으로 유지되도록 설계된 특수한 스택입니다. 이는 특정 조건을 만족하는 요소를 효율적으로 처리하거나 빠르게 접근해야 할 때 사용됩니다.오름차순 스택: 스택에 쌓인 값이 항상 작아지지 않도록 유지.내림차순 스택: 스택에 쌓인 값이 항상 커지지 않도록 유지.모노톤 스택은 일반적으로 배열이나 리스트의 각 요소와 관련된 "가장 가까운 큰 값" 또는 "가장 가까운 작은 값"을 찾는 문제에 사용됩니다. O(N)의 시간 복잡도로 해결할 수 있어 효율적입니다.문제 접근이 문제 또한 모노톤 스택을 사용하여 해결할 수 있습니다.먼저 서로를 볼 수 있는 조건을 생각해 봅시다.두 사람이 서로 볼 수 있으..

https://www.acmicpc.net/problem/23057 문제 접근숫자의 조합으로 만들 수 없는 수의 합을 구해야한다.결국 만들 수 있는 모든 경우의 수를 구해야 하는데, N이 최대 20이면 최대 경우의 수는 2^20 이므로 DFS와 같은 방식은 시간 초과가 터진다.따라서 다른 방식을 선택해야 한다. 그게 비트마스킹 방식이다.비트마스킹으로 모든 경우의 수 찾기 HashSet sumSet = new HashSet(); int totalSubsets = 1  1 각 이진수 자리에 마스크를 넣어본다. mask 변수의 각 비트는 숫자를 포함할지 여부를 나타낸다. 비트 1이면 해당 숫자를 포함하고, 0이면 포함하지 않는다. 문제에서는 모두 자연수라는 조건 때문에 0을 제외해야 ..

https://www.codetree.ai/training-field/frequent-problems/problems/tree-tycoon/description?page=3&pageSize=10 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai문제 접근구현, 시뮬레이션 문제입니다.특수 영양제 규칙을 준수하여, 크게 특수 영양제 이동 -> 성장 -> 자르기로 로직을 분류합니다. 특수 영양제 규칙영양제는 매년 주어진 규칙에 따라 이동하며, 이동한 칸의 리브로수를 성장시킵니다.대각선 방향에 높이가 1 이상인 리브로수의 개수만큼 추가로 성장합니다.이미 영양제를 투..

이번 글에서는 제가 Spring Data JPA에 기여하기 위해 겪은 과정을 소개합니다.Issue 찾기어느 오픈 소스던, Issue는 있기 마련입니다. 완벽한 소프트웨어는 없으니까요!우선 기여할 오픈 소스 레포지토리를 찾아봅시다.어떤 오픈 소스에 Issue를 선정할 것 인지는 우선 본인이 자주 쓰는 오픈 소스이며, 익숙한 프로그래밍 언어를 사용할수록 이슈를 해결하기 좋을 것입니다. 저는 Spring Data JPA에서 찾아보았습니다.Spring Data JPA는 Spring 프레임워크에서 JPA(Java Persistence API) 기반의 데이터 접근을 더 간단하고 효율적으로 구현하기 위한 라이브러리입니다. ORM(Object Relational Mapping)을 지원하며, 데이터베이스와의 상호작용을 ..

이 글에서는 상품 서비스에 CQRS 패턴을 적용하고, Query를 위해 Elasticsearch를 적용한 것을 다룹니다.문제 상황: RDBMS의 Full Scan 동작으로 인한 상품 검색 성능 저하기존의 상품 검색의 구현은 위와 같이 QueryDSL로 쿼리가 작성되어 있었습니다.주목해야 하는 코드는 containsIgnoreCase입니다. containsIgnoreCase 조건은 productName 필드 내에서 키워드를 위치와 상관없이 검색하므로 RDBMS에서는 일반적으로 앞에 와일드카드가 포함된 (% keyword%) 검색을 수행하게 됩니다. 이러한 검색은 인덱스를 사용할 수 없게 만들어, RDBMS가 테이블의 모든 productName을 평가해야 하기 때문에 전체 테이블 스캔을 하게 됩니다.실행 계..

이 글에서는 설문조사 웹 서비스 백엔드를 개발하면서 해결했던 INSERT 동작에 동시성 문제를 해결하는 과정을 소개합니다.문제 파악: 의도치 않은 동일 설문조사 생성 방지설문조사 생성 시 포인트가 필요하기 때문에 불필요한 중복 생성은 사용자 경험에 악영향을 미칠 수 있습니다.예를 들어, 동일 사용자가 동일한 설문조사 요청을 여러 개 보낼 경우를 생각해 보면 사용자가 설문조사를 생성하는 버튼을 여러 번 클릭할 수 있고, 이는 네트워크 지연으로 인해 응답이 늦어질 때 더 흔하게 발생할 수 있습니다.따라서 중복 생성이 발생하지 않도록 효과적인 동시성 제어가 필요했습니다. 이를 해결하지 않으면 사용자에게 의도치 않은 포인트 소모 및 중복 데이터 생성 문제가 발생할 위험이 있었습니다.대안 1: 비관적 락을 사용해..

코딩테스트 연습 - [PCCP 기출문제] 3번 / 충돌위험 찾기 | 프로그래머스 스쿨 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr처음 문제 풀이대충 중간에 하다가 영 아닌 것 같아서 포기한 코드import java.util.*;class Solution { public int solution(int[][] points, int[][] routes) { int answer = 0; Queue queue = new ArrayDeque(); for (int [] route : routes) { Point point = new Po..

1107번: 리모컨처음 문제 접근BFS인가? 하기엔 시도해야할 경우의 수가 너무 많은 것 같다. 사실상 브루트 포스로 하게 될 듯채널이 0 ≤ N ≤ 500,000니까 배열에 각 최소 횟수를 업데이트 해주는 식으로 해야할 것 같음고장이 안난 리모컨 배열에서 입력할 수 있는 모든 경우의 수를 만들어야 하나? 그럼 백트래킹인가?그럼 for문을 언제까지 돌리고 언제 끝내야하지?답지 보고 문제 접근1. 먼저 리모컨 배열을 만든다. 이 배열에 값이 -1이면 고장난 것을 의미한다. int n = Integer.parseInt(br.readLine()); if (n != 0) { StringTokenizer st = new StringTokenizer(br.readLine..

이 글에서는 프로젝트를 진행하면서 간단한 방법으로 성능 개선을 수행했던 방법들을 소개하고자 합니다. 테스트 데이터는 300만개 입니다.소프트 삭제 정책에 따른 삭제 테이블 분리하기소프트 삭제(Soft Delete)란 데이터베이스에서 실제로 데이터를 삭제하지 않고, 대신 해당 데이터가 삭제된 것처럼 처리하는 방식입니다. 이를 위해 보통 데이터 테이블에 is_deleted와 같은 플래그(삭제 여부를 나타내는 필드)를 추가하고, 해당 값이 true로 설정된 경우에는 해당 데이터를 "삭제된" 것으로 간주합니다. 따라서 매 조회 쿼리 마다 is_deleted = false라는 조건을 추가해야 하는데, 조건을 추가한다는건 결국엔 DBMS가 추가적으로 작업을 시키게 됩니다. 모든 조회 쿼리에 이 조건을 추가하는 것은..

MSA 프로젝트에서 테스트는 특히 외부 의존성을 많이 사용하게 될 경우 복잡해집니다. Redis, DB, Kafka 등 외부 리소스가 있다면, Mocking이나 다수의 서버 및 컨테이너 구동이 필수적이라, 테스트를 생략하고 PR을 진행하는 경우도 빈번하게 발생합니다. 이 글에서는 GitHub Actions를 통해 실제 개발 환경을 자동으로 구성하여 테스트를 자동화하는 방법을 소개합니다.문제 상황: gradle build -x test초기 CI 구성 시에는 gradle build -x test 명령어로 테스트를 건너뛰었다. 외부 Redis, DB, Kafka 등의 의존성이 테스트 중 연결되어야 하는데, 이로 인해 테스트 시 에러가 발생하기 때문이다. 그러나 이렇게 테스트를 생략하면, 서버 실행 후 발생할 ..