꾸준함

[Programmers] 매출 하락 최소화

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/72416 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 트리 DP 알고리즘 문제였고 각 노드에 대해 두 상태를 정의하여 해결할 수 있습니다.attendedDp[node]: 노드가 참석했을 때 최소 비용cost = sales[node] + 자식들의 상태와 상관없이 각 자식에 대해 min(attendedDp[child], notAttendedDp[child])의 합 notAttendedDp[node]: 노드가 참석하지 않았을 때 최소 비용이 경우 node가 팀장이면 반드시 자식 중 한..

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/67260 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr BFS를 응용한 알고리즘 문제였습니다. 알고리즘은 아래와 같습니다.1. 트리를 구성한 뒤 각 방에 대해 `방문하기 전에 반드시 방문해야 하는 방`을 저장하는 배열 pre를 정의합니다. 2. BFS를 통해 0번 방에서 시작해서 방문합니다.만약 시작점인 0번 방 이전에 방문해야 하는 방이 있다면 탐험 자체가 불가능하므로 바로 종료인접한 방 (next)에 대해, 만약 pre[next] (next 이전에 방문해야 하는 방)가 아직 방..

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/60060 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 이분 탐색 알고리즘과 문자열 처리를 접목시킨 문제였습니다. 알고리즘은 다음과 같습니다.주어진 단어들 전처리 진행단어의 길이에 따라 wordsByLength 배열에 단어들을 저장접두사에 와일드카드가 등장하는 쿼리를 효율적으로 처리하기 위해, 각 단어를 뒤집어서 reversedWordsByLength 배열에도 저장 쿼리 처리쿼리의 길이에 해당하는 단어 그룹이 없으면 0을 결과에 추가.쿼리의 첫 글자가 알파벳이면 와일드카드가 접미사..

백준 월간 향유회 2025. 01. 대회 문제들이 올라와서 풀어봤습니다.문제들이 제 기준 쉽지 않았기 때문에 실제 대회에 참가했다면 최대 2 솔이었을 것 같습니다.마지막 문제인 XOR 머신은 제 역량으로는 도저히 못 푸는 문제인 것 같아 나중에 고수님들의 해설을 보고 풀어야 할 것 같습니다. 백준 33272번 TAIDADA이 문제의 핵심은 `어떤 수 x를 골랐을 때, x와 x ⊕ K 두 수는 동시에 고를 수 없다`는 점 이를 그래프로 해석하면, 정점이 1부터 M인 그래프에서 x와 (x ⊕ K)를 간선으로 연결한다고 할 때 인접 정점을 동시에 고를 수 없는 집합을 찾는 문제  백준 33273번 multiple sequence이차원 dp를 사용하는 문제였고 알고리즘은 다음과 같습니다.x_i 기준으로 오름차순..

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/76504 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr BFS와 DP를 활용하여 푸는 알고리즘 문제였습니다.현재 있는 도시에 움직이지 않을 경우 z 원씩 쌓을 수 있으므로 z * n원을 얻은 뒤 도로 이동을 통해 잔여 금액인 (query - z * n) 원을 얻는 것이 핵심인 문제였습니다. 알고리즘은 다음과 같습니다.1. BFS를 통해 [0원, limit원]까지 각각을 만드는 최소 턴 수를 전부 구합니다.limit원 이하의 돈을 정확히 만드는 최소 턴 수만 미리 전부 구해둘 경우 ..

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/42894 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr `3 * 2, 2 * 3 형태로 구성된 블록을 찾을 수 있으면 지운다`를 반복하는 알고리즘 문제였습니다. 알고리즘은 다음과 같습니다.1. 각 열마다 `가장 위쪽 블록의 행 번호`를 추적하여 topRowInCol 배열에 업데이트합니다.1.1 topRowInCol 배열은 실제 검사해야 할 행 범위를 빠르게 결정할 수 있도록 지원합니다. 2. 3 * 2 나 2 * 3 영역에서 다음 조건이 해당하면 블록을 제거해 줍니다.빈칸이 정확히..

문제 링크는 다음과 같습니다: https://school.programmers.co.kr/learn/courses/30/lessons/150364?language=cpp 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 트리 내 경로가 각 회차마다 유일하므로 `떨어지는 i 번째 숫자가 최종적으로 도달하는 리프 노드가 사실상 정해져 있다`는 아이디어로 구현하면 되는 알고리즘 문제였습니다. 알고리즘은 다음과 같습니다.1. 각 횟차마다 숫자가 어느 리프 노드에 도착하는지 시뮬레이션으로 모두 미리 구합니다.1.1 모든 리프 노드를 1로만 채우는 케이스가 최악의 경우이므로 시뮬레이션은 target 배열의 합만큼 돌..

문제 링크입니다: https://www.acmicpc.net/problem/7469 좌표 압축과 퍼시스턴트 세그먼트 트리를 이용하는 문제였습니다.퍼시스턴트 세그먼트 트리 관련해서는 justicehui님 블로그를 참고하시면 될 것 같습니다.https://justicehui.github.io/medium-algorithm/2020/02/29/PST/ Persistent Segment Tree서론 어떤 자료구조가 “persistent하다”라는 것은, 상태의 변화가 생기더라도 과거 상태를 모두 보존하고 있다는 것을 의미합니다. Persistent Segment Tree(PST)는 세그먼트 트리의 갱신 과정을 모두 저justicehui.github.io 알고리즘은 다음과 같습니다.1. 배열 a의 값들이 [-10^..

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/118670 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 2 * 50,000과 같은 케이스가 있기 때문에 이차원 배열을 선언하고 문제에서 주어진 대로 정직하게 구현하면 TLE가 발생하는 문제였습니다.덱을 이용해야한다는 것은 알았는데 Rotate 연산을 어떻게 최적화시켜야 할까 고민하다가 바킹독님 해설을 보고 풀 수 있었습니다. 이 문제의 핵심은 1열과 마지막 열을 별도 Deque으로 분리하고 나머지는 각 행을 기준으로 Deque을 선언해 주는 것입니다.위와 같이 처리해주면 Shif..

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/12929 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 올바른 괄호 문자열의 개수를 구하기 위해 카탈랑 수(Catalan Number)를 구해주면 되는 문제였습니다.점화식은 다음과 같습니다.   개발환경: Programmers IDE   지적, 조언, 질문 환영합니다! 질문 남겨주세요~