알고리즘 1654

백준 2025 중앙대학교 프로그래밍 경진대회

백준 33674번 하늘에서 떨어지는 N개의 별각 점 i에서 청소 없이 f일간 별이 쌓이면 각 점의 누적 별은 f × s_i폭발은 별의 개수가 K를 초과할 경우 발생하므로, 각 점에서 안정하게 유지하기 위해서는 f × s_i ≤ K 를 만족해야 함따라서 각 점 i에 대해 f ≤ floor(K / s_i) 이어야 함모든 점에 대해 동시에 만족시키려면 `f ≤ min_{1≤ i ≤ N} floor(K / s_i)` 가 됨해당 값을 m이라고 정의했을 때, 한 청소 사이에 연속해서 최대 m일 동안 별 쌓기를 안전하게 할 수 있음 D일을 m일 간격으로 나누면, 필요한 청소 횟수는 ceil(D / m) - 1초기 상태는 이미 0이므로 첫 구간은 청소할 필요 없음  백준 33675번 L-트로미노 타일링 N이 홀수인 경..

알고리즘/BOJ 2025.04.13

[Programmers] 격자 뒤집기 미로

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/389630 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 비트마스크를 통해 풀 수 있는 문제였습니다. 알고리즘은 다음과 같습니다.1. 격자의 모든 칸의 visible 값을 더해 기본 점수를 구하고, 각 칸에서 hidden과 visible의 차이를 diff로 계산합니다. 2. 각 행을 뒤집거나 그대로 두는 모든 경우 {2^(행 수}) 가지를 고려하여, 뒤집힌 행의 수에 따른 비용을 기본 점수에서 차감해 기준 점수를 정합니다. 3. 각 열에서 "열을 그대로 둘 때”와 “열을 뒤집을 때..

[Programmers] 경사로의 개수

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/214290 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 행렬 DP 문제였습니다. 알고리즘은 다음과 같습니다.1. 격자의 각 칸을 하나의 상태로 보고, d 수열 한 번의 이동을 전이로 표현합니다. 2. 각 상태에서 시작했을 때 경사 이동 한 번에 따른 이동 가능 경로의 수를 계산하여 전이 행렬 M를 구성합니다. 3. k번 연속해서 경사 이동을 수행한 후의 결과를 구합니다.2번에서 구한 전이 행렬 M을 k번 제곱한 M^k 4. 격자 내 모든 출발 상태에서의 경로 수를 Mk 행렬의 모..

[Programmers] 봉인된 주문

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/389481 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 백준에서 K번째 수 구하기 문제 시리즈와 비슷한 문제였습니다. 알고리즘은 다음과 같습니다.1. 각 길이 L에 대해 전체 문자열 중에서 삭제되지 않은 주문의 개수를 구합니다. 2. 누적 개수를 이용해 n번째 주문이 어느 길이에 속하는지 판별합니다. 3. 해당 길이 내에서 사전순으로 정렬된 모든 문자열에 대해, 봉인된 주문을 제외하고 남은 문자열 중 n번째 주문을 찾아냅니다. 4. 찾은 숫자 값을 길이 L의 문자열로 변환하여 반..

[Programmers] 완전범죄

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/389480 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 이차원 배열 DP를 통해 A의 누적 흔적이 a, B의 누적 흔적이 b인 상태 가능 여부를 계산하면 되는 문제였습니다.  개발환경: Programmers IDE    지적, 조언, 질문 환영합니다! 질문 남겨주세요~

[Programmers] 서버 증설 횟수

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/389479 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 지문에서 주어진 대로 구현하면 되는 문제였습니다.  개발환경: Programmers IDE    지적, 조언, 질문 환영합니다! 질문 남겨주세요~

[Programmers] 홀짝트리

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/388354 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr Union Find 알고리즘 문제였습니다. 알고리즘은 다음과 같습니다.1. 각 노드에 연결된 간선의 개수인 degree를 기록하고 간선 정보를 이용해 각 노드들이 어떤 트리에 속하는지 파악합니다. 2. 각 노드가 홀짝 트리 또는 역홀짝 트리의 루트로 선택될 수 있는지 확인 후, 두 그룹으로 분류합니다.(node % 2) == (degree % 2) → 루트로 쓰일 수 있음(node % 2) != (degree % 2) → 루..

[Programmers] 지게차와 크레인

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/388353 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr BFS 알고리즘 문제였습니다.컨테이너 제거 방법은 두 가지이며 두 케이스 모두 고려하여 구현하면 되는 문제였습니다.요청 문자열 길이가 2인 케이스: 해당 알파벳과 일치하는 모든 컨테이너를 별도의 조건 없이 제거요청 문자열 길이가 1인 케이스현재 창고 상태에서 접근 가능한 컨테이너만 제거접근 가능하다는 의미는 해당 컨테이너의 4면 중 적어도 한쪽이 창고 외부 또는 창고 외부와 연결된 빈 공간과 연결되어 있어야 한다는 의미  개..

[Programmers] 비밀 코드 해독

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/388352?language=cpp 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 서로 다른 5개의 번호를 입력하는 문제이므로 5중 반복문을 이용해 풀면 되는 구현 문제였습니다.  개발환경: Programmers IDE    지적, 조언, 질문 환영합니다! 질문 남겨주세요~

[Programmers] 안티세포

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/86054 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr a의 길이가 최대 20만이기 때문에 DP로 접근해야 하는 문제였습니다.늦잠님 블로그 글을 참고하여 풀었습니다.https://velog.io/@woolzam/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4Lv.4Java-%EC%95%88%ED%8B%B0%EC%84%B8%ED%8F%AC [프로그래머스/Lv.4][Java][C++] 안티세포출처 : https://school.prog..