알고리즘 1655

백준 Hello, AlKon! 2025

백준 33701번 새천년관단순 구현 문제 백준 33702번 비밀번호DFS와 비트마스크를 결합한 백트래킹으로 그래프 상의 모든 해밀토니안 경로를 세는 문제 백준 33703번 건덕이의 돌탑하노이 탑 이동 문제와 달리 `중간에 있는 돌도 한 번에 꺼낼 수 있다`는 제약 완화 덕분에어떤 방석에서 가장 큰 돌을 제외한 모든 돌은 언제든지 단 한 번의 이동으로 꺼낼 수 있고꺼낸 돌을 놓을 때에도 빈 방석 또는 더 큰 돌이 있는 방석 위에만 놓으면 되므로 그 방석 내 정렬이 자동으로 보장됨 위 두 가지를 이용하면, 개별 돌 하나를 세 번째 방석에 놓기까지 필요한 이동 횟수를 돌 크기별로 합산하는 방식으로 해를 구할 수 있음맨 밑의 돌이 아니라면 한 번에 꺼낼 수 있으므로, 돌 k를 꺼내는 데는 그 위에 있는 더..

알고리즘/BOJ 2025.05.17

백준 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    지적, 조언, 질문 환영합니다! 질문 남겨주세요~