전체 글

[프로그래머스 문제풀이]2024 KAKAO WINTER INTERNSHIP 산 모양 타일링

보자마자 DP문제다. DP문제는 점화식을 세워야 한다. 가로의 길이는 2*n+1이므로 현재 위치에서 어떤 타일을 사용해서 모양을 완성시킬 수 있는가에 대해 알아보자 가로로 타일을 채워갈 때 크게 두 가지로 나눌 수 있다. 타일을 정삼각형으로 쌓아야 하는 경우, 역삼각형으로 쌓아야 하는 경우다. 현재 위치가 x일 때, 삼각형 하나만 사용하는 경우엔 가로로 한 칸을 채울 수 있다. 따라서, dp [x] += dp [x-1] 마름모 타일이 서있지 않는 경우, 둘 다 가로로 두 칸을 채울 수 있다. 따라서 , dp [x] += dp [x-2] 마지막으로 마름모 타일을 돌려 높이가 1인 경우다. 이땐 현재 위치에서 타일을 정삼각형으로 쌓아야 하는 경우, 현재 위치보다 한 칸 앞의 타일의 높이가 1인 경우이다. 따..

[프로그래머스 문제풀이]2024 KAKAO WINTER INTERNSHIP n+1 카드게임

문제흐름을 살펴보면 카드가 2장 주어졌을 때, 한 장도 가지지 않을 것인지, 한 장을 가질 것인지, 두 장을 가질 것 인지를 결정해야 한다. 여기서 포인트는 카드를 뽑을 것인가는 당장 정하지 않는다는 것이다. 지금 당장 n+1을 만들 수 있는 카드 조합이 있다면, 카드를 뽑지 않고, 카드 더미에 쌓아두는 것이다. 당장 카드를 뽑지 않아도 나중에 필요할 때 coin을 사용해서 n+1 카드를 만들 수 있는 것이다. 따라서 전체적인 흐름은 아래와 같다. 1. 카드를 카드 더미에 쌓는다. 2. n+1 해결하기 1. 수중에 있는 카드로 n+1을 만들 수 있다면, 다음 카드 뽑기 2. coin을 사용해야 한다. 2-1. coin 없다면 게임 끝 2-2. coin 한 개를 사용해서 (수중에 카드 한 장 + 카드 더미..

[프로그래머스 문제풀이]2024 KAKAO WINTER INTERNSHIP 주사위 고르기

문제의 흐름을 파악하면 크게 3단계로 나눌 수 있다. 1. 모든 주사위 조합을 구한다. 2. 조합들을 비교하여 , A가 B를 이기는 가장 높은 확률의 주사위 조합을 구한다. 3. 가장 확률이 높은 주사위 번호를 오름차순으로 정렬한다. 결국 주사위 n/2개를 뽑은 A가 나머지 주사위를 고른 B를 가장 많이 이기는 주사위 n/2개의 주사위 조합을 구하면 된다. 실제 코딩테스트를 볼 때 위의 단계까진 생각했으나 구현에서 막혔다. 시간 복잡도를 계산하면 n의 범위는 10이므로 A가 가질 수 있는 최대 주사위의 개수는 5개, 5개의 주사위에서 나올 수 있는 주사위의 합은 최대 6*6*6*6*6= 7776개이다. A가 B를 이기는 횟수를 구하기 위해 A가 가질 수 있는 주사위의 합의 개수, B가 가질 수 있는 주사..

분산 시스템에서 메시지 안전하게 다루기

채팅 시스템을 개발하던 도중 코드 리뷰를 받게 되었는데, Kafka를 통해 메시지 발행, 채팅 저장을 하나의 트랜잭션에서 실행하는 코드를 보고, Kafka를 통해 메세지 발행이 실패하여도 채팅이 저장된다는 리뷰를 받게 되었고, 이를 해결하기 위해 여러 가지 방법을 찾아보았습니다. 먼저 문제의 함수를 먼저 보겠습니다. 함수를 간단하게 설명하면 채팅방안에 사람이 있다면 message를 읽은 메세지로 처리하고 메세지를 저장하고 메세지를 발행하는 함수입니다. 메세지 발행(messageSender.send)에서 오류가 생기면 메세지를 저장하지 않고 rollback을 하게 되지만, 메세지 발행은 무사히 됐으나 Transaction commit 과정에서 오류가 생긴다면 메세지를 발행했으나 메세지 저장이 되지 않는 상..

쿠폰 발급 동시성 제어하기, 성능테스트로 성능 개선하기

Coupon을 발행하는 파일럿 프로젝트를 진행하며 겪은 동시성 문제를 해결하는 글입니다. 우선 Coupon을 발행하는 코드입니다. 플로우를 간단하게 살펴보면 사용자가 Coupon을 받을 수 있는지 없는지 체크 한 후 Coupon을 받을 수 있다면 Coupon 발부에 성공하게 됩니다. 동시에 여러명이 Coupon을 발급하였을 때, 정확한 Coupon 개수만큼 발급하는지에 대한 테스트 코드를 작성해보겠습니다. 동시에 Coupon을 발행하게 되면 테스트는 실패한다. 왜 실패할까? 로그를 살펴보자 위 로그를 보면 Lock을 얻는 과정에서 Deadlock이 생긴다고 한다. Lock은 언제 얻을까? 답은 Mysql 연관관계에 있다. 외래 키 계약조건이 있는 테이블에 삽입, 삭제, 갱신을 할 때 제약조건을 위반하는지..

스케줄러와 Transactional 테스트 코드에서 생긴 문제 해결하기

프로젝트 진행 중 상세페이지 한 명이 상세 페이지를 조회 시 조회수를 Update 처리해줘야 하는 과정을 구현하며 겪은 문제들에 대해 얘기해 보겠습니다.저는 상세 페이지를 조회할 때마다 DB에 Update Query를 날려 조회수를 업데이트해주고 있었습니다.문제점하지만 이렇게 상세페이지를 조회할 때마다 DB에 Update쿼리를 날리게 되면 DB에 부하가 증가하고, 또한 Lock으로 인해 성능저하가 생길 수 있습니다. 해결책프로젝트에서 조회수가 아주 중요한 정보는 아니라고 생각하여 Redis에 조회수를 저장한 후 Scheduler를 통해 DB에 Update 하여 저장하기로 하였습니다.이렇게 한 이유는 DB에 Update쿼리를 조회할 때마다 날리지 않아도 되어 성능상 이득을 취할 수 있다고 생각하였기 때문입..

동시성 제어하기

Ticket을 발행하는 파일럿 프로젝트를 진행하며 겪은 동시성 문제를 해결하는 글입니다. Ticket을 받지 않은 사용자에게 Ticket을 발행해 주는 파일럿 프로젝트입니다. 우선 Ticket을 발행하는 코드입니다. 플로우를 간단하게 살펴보면 사용자가 티켓을 받았는지 확인 후 안 받았다면 몇 번째로 예약했는지 번호 담아 Ticket 발부에 성공하게 됩니다. 정확히 동작하고 있는지 테스트 코드를 작성해 보자. 우선 순차적으로 코드를 작성했을 때 테스트코드다. 순차적으로 Ticket을 발행하는 테스트는 통과한다. 하지만 동시에 Ticket을 발행하면 어떻게 될까? 동시에 Ticket을 발행하게 되면 테스트는 실패한다. 왜 실패할까? 로그를 살펴보자 위 로그를 보면 Lock을 얻는 과정에서 Deadlock이 ..

[Python] 백준 20366번 풀이

우선 이 문제는 두 포인터를 활용한 문제다. 두 개의 눈사람 키 차이 중 최솟값을 구하는 문제이다. 문제 풀이를 보고 이해가 안 가는 부분이 있었는데, a, b와 사이엔 최소 2개의 원소가 있어야 그 안에서 투포인터를 돌려 a, b로 이루어진 눈사람의 키와 차이가 가장 적은 눈사람을 만들 수 있다. 정렬된 배열에서 두 포인터를 돌리므로, a