문제 파악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 이상의 수들로 구성된 단조..

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

문제 파악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로 순서가 보장되기 때문에 큐..

문제 파악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..