문제 파악https://www.acmicpc.net/problem/2169 풀이보자마자 직관적으로 떠올린 풀이는 DFS / DP이다.하지만 DFS로 접근할 경우, 같은 행에서 좌우 이동이 가능하기 때문에방문 처리 여부에 따라 무한 루프 또는 최적 경로 차단 문제가 발생한다.규칙을 찾기 위해 재방문하지 않고, 위쪽으로 방향을 틀지 않는 로봇의 경로를 그려보았다N번째 행에서의 로봇의 경로는 N + 1 행으로 아랫방향 이동 : ⬇️우측으로만 이동 : ⬇️ ➡️➡️➡️좌측으로만 이동 : ⬅️⬅️⬅️ ⬇️뿐이다. 만약 우측으로 갔다가 좌측으로 간다면 반드시 같은 칸을 재방문하게 되므로 규칙에 위배된다.👉 즉, 한 행 안에서는 한 방향만 선택 가능하다는 중요한 제약이 생긴다. DP 상태 정의그럼 DP 배열을 선언..

문제 파악https://school.programmers.co.kr/learn/courses/30/lessons/258705어려운 점보자마자 “DP 문제다” 라고 느껴졌지만, 정확한 규칙을 찾는 데 시간이 꽤 걸렸다.특히 상태를 어떻게 정의할지 고민하는 과정에서 여러 번 막혔다 ^.ㅠ 🐸 풀이비트마스크 + DP로 풀어볼까 라고 생각했지만 상태 정의를 비트마스크로 하면 경우의 수가 늘어나 점점 꼬였다 🥲좀 더 단순한 규칙을 찾아보기로 했다.먼저 위와 같이 구역을 나눠 규칙을 더 찾아보면 마름모 퍼즐을 아래와 같이 배치하는 경우에만 타 영역을 침범하는 걸 볼 수 있다.보다시피 이전 영역의 가운데 삼각형 부분에 걸쳐 자리잡고 있다... 그렇다면 1️⃣중간 지점을 빼고 배치하는 경우의 수와, 2️⃣중간 부분..

문제 파악풀이요약하자면 높이 [0, 1, ... h-1] 지점에 장애물이 몇개 있는지 판별하여, 장애물의 최솟값과 최솟값을 가지는 지점 수를 리턴하는 문제이다 예를 들어 석순 크기 3짜리가 높이 7인 동굴에 배치되어 있다면 구간 (0,1,2) 에 장애물이 하나씩 생긴다이 때 (0,1,2) 구간마다 장애물의 카운터를 하나씩 늘려 주게 된다면 최악의 경우 복잡도는 O(H*N), 10^11가 될 것이다 🥲 위 방법 대신 장애물이 [0,h-1] 구간에 끊김 없이 배치되어 있기 때문에장애물의 시작, 종점+1에 각각 증감인 +1, -1만 기록해주자그 후 높이 H에 대해 누적합을 계산하면 복잡도가 O(H)로 줄게 된다.구현 순서는 다음과 같다증감을 기록할 일차원 배열(collision: int[N])을 사용하도록 ..

문제 파악풀이당연히 이중 for문을 사용하면 O(N^2)로 시간초과..🥲원소를 순회할 때마다 이전 인덱스까지의 수를 참고해야 한다는 사실은 변함이 없으나,탐색 범위와 탐색 회수를 줄이는 방법을 생각해야겠다 그를 위해서 예시로 주어진 [6,9,5,7,4]에서 마지막 원소인 4에 다다랐을 때, 온전한 이전 배열 [6,9,5,7]에서 4보다 큰 수를 찾기보다[6,9,5,7] => [9,7]에서 가장 최신 원소인 7의 인덱스를 정답 배열에 기록해 주면 될 것이다. `가장 최신의 원소`, `내림차순`(혹은 오름차순)의 특성을 반영하기 위해 단조 스택을 이용하여 풀이하자 구현 순서는 순회하는 원소의 값(input)을 바탕으로 1. input 값 기준 내림차순 단조 스택 확립- input 이상의 수들로 구성된 단조..

가상 면접 사례로 배우는 대규모 시스템 설계 기초 中 4장. 처리율 제한 장치의 설계를 읽으며 기록한 포스팅입니다.들어가며Resilience4j Rate Limiter를 사용해 보면서 ip당 특정 엔드포인트 처리율 제한을 구현한 적이 있었다.Rate Limiter에는 어떤 종류가 있고, 어떤 사례에서 쓰이는지 알아보고 싶던 때에 좋은 책에 필요한 목차가 있어 해당 내용을 정리하였다.처리율 제한(Rate Limiter)서버의 부하를 제어하기 위해 단위 시간당 허용 가능한 요청 수를 제한하는 기술이다.예를 들어 다음과 같은 제한을 둘 수 있다.SNS 서비스에서 하루 글쓰기 횟수 제한친구 추가, 팔로우 요청 횟수 제한API 호출 횟수 제한이러한 제한을 두지 않으면 서비스는 짧은 시간 내에 부하가 급격히 증가하..

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