프로그래머스 불량 사용자 풀이: 비트마스크 DFS 매칭
프로그래머스 불량 사용자에서 패턴별 후보를 만들고, 한 사용자를 중복 선택하지 않도록 DFS로 배정한다. 비트마스크 집합으로 순서만 다른 조합을 하나로 센다.
#프로그래머스
프로그래머스 코딩테스트 문제를 Python으로 풀고 핵심 아이디어와 구현 과정을 정리한다. 현재 39개의 풀이가 있다.
프로그래머스 베스트앨범 풀이: 해시 집계와 우선순위 정렬
프로그래머스 베스트앨범에서 장르별 재생 합계를 구하고, 장르 안의 곡을 재생 수와 고유 번호로 정렬한다. 장르마다 상위 두 곡을 고르는 과정을 설명한다.
프로그래머스 택배 상자 꺼내기 풀이: 지그재그 위치 계산
프로그래머스 '택배 상자 꺼내기'에서 상자 번호를 층과 열로 바꿔 필요한 상자 수를 계산한다. 지그재그 방향과 마지막 층의 불완전한 열을 처리한다.
프로그래머스 의상 풀이: 카테고리별 조합의 곱셈 법칙
프로그래머스 의상에서 종류별 개수를 센 뒤 각 종류의 선택지를 곱하고, 아무것도 고르지 않은 경우를 뺀다. 곱셈 법칙으로 조합 수를 계산한다.
프로그래머스 섬 연결하기 풀이: 크루스칼 최소 신장 트리
프로그래머스 섬 연결하기에서 비용순으로 다리를 살펴보고 Union-Find로 사이클을 막는다. 서로 다른 연결 요소를 잇는 간선만 골라 최소 신장 트리를 만든다.
프로그래머스 디스크 컨트롤러 풀이: 대기 작업 최소 힙 스케줄링
프로그래머스 디스크 컨트롤러에서 현재 대기 중인 작업 가운데 소요 시간이 가장 짧은 작업을 최소 힙으로 고른다. 요청 시각과 유휴 시간, 평균 반환 시간을 함께 다룬다.
프로그래머스 이중우선순위큐 풀이: 두 힙과 지연 삭제
프로그래머스 이중우선순위큐에서 최소 힙과 음수로 저장한 최대 힙을 함께 사용한다. 값별 개수로 지연 삭제를 처리해 두 힙을 동기화한다.
프로그래머스 가장 먼 노드 풀이: 인접 리스트 BFS
1번 노드에서 BFS로 모든 노드까지의 최단 간선 거리를 구한다. 최댓거리와 같은 거리를 가진 노드 수를 세는 풀이를 설명한다.
프로그래머스 유연근무제 풀이: 시간 변환과 요일 판별
프로그래머스 '유연근무제'에서 HHMM 시각을 분으로 바꾸고 요일을 계산한다. 주말을 제외한 출근 기록으로 조건을 만족하는 직원 수를 구한다.
프로그래머스 지폐 접기 풀이: 긴 변을 줄이는 그리디
프로그래머스 PCCE 지폐 접기에서 매번 긴 변을 절반으로 줄여 지갑에 들어가는지 확인한다. 90도 회전 가능한 크기 비교와 최소 접기 횟수를 다룬다.
프로그래머스 H-Index 풀이: 정렬 후 인용 수와 순위 비교
프로그래머스 H-Index에서 인용 횟수를 내림차순으로 정렬하고 현재 순위와 비교한다. 인용 횟수가 순위보다 작아지는 경계에서 H-Index를 구한다.
프로그래머스 선인장 숨기기 풀이: 2차원 슬라이딩 윈도우
프로그래머스 선인장 숨기기에서 각 칸의 강수 시점을 기록하고, 가로·세로 단조 덱으로 직사각형의 최솟값을 구한다. 최대 500,000칸을 O(mn)에 처리한다.
프로그래머스 힌트 스테이지 풀이: 비트마스크 완전탐색
프로그래머스 힌트 스테이지에서 구매할 번들의 부분집합을 비트마스크로 탐색한다. 각 조합의 힌트 수와 비용을 계산해 최소 비용을 찾는다.
프로그래머스 호텔 방 배정 풀이: 연속 점유 구간을 합치는 유니온 파인드
최대 10^12개의 방을 배열로 만들지 않고, 배정된 방만 Union-Find로 관리한다. 각 연속 점유 구간의 오른쪽 끝을 저장해 다음 빈 방을 찾는다.
프로그래머스 도둑질 풀이: 원형 집을 두 구간으로 나누는 동적 계획법
원형 배치 때문에 양 끝집을 동시에 고를 수 없는 조건을 두 선형 DP로 나눈다. 반열린 구간과 이전 두 상태만 사용해 백만 채 입력도 추가 배열 없이 처리한다.
프로그래머스 중요한 단어를 스포 방지 풀이: 구간 처리와 해시
프로그래머스 '중요한 단어를 스포 방지'에서 단어와 스포일러 구간의 겹침을 찾고, 해시 집합으로 일반 영역의 단어와 중복을 처리한다.
프로그래머스 멀쩡한 사각형 풀이: 최대공약수로 대각선 격자 계산
프로그래머스 멀쩡한 사각형에서 전체 칸 수와 대각선이 지나는 칸 수의 차이를 구한다. 최대공약수로 반복되는 대각선 패턴을 계산하는 방법을 설명한다.
프로그래머스 보석 쇼핑 풀이: 해시 슬라이딩 윈도우
프로그래머스 보석 쇼핑에서 슬라이딩 윈도우로 현재 구간의 보석 종류와 개수를 관리한다. 모든 종류를 포함하는 가장 짧은 구간과 시작 위치 조건을 찾는다.
프로그래머스 조이스틱 풀이: 알파벳 변경과 커서 이동 그리디
프로그래머스 조이스틱에서 알파벳 변경 비용과 좌우 이동 비용을 나눠 계산한다. 연속된 A 구간을 건너뛰는 경로까지 비교해 최소 조작 횟수를 찾는다.
프로그래머스 점프와 순간 이동 풀이: 홀수 위치만 점프하는 그리디
프로그래머스 점프와 순간 이동에서 목적지부터 거꾸로 이동하며 홀수 위치에서만 배터리를 쓴다. 짝수 위치는 순간 이동으로 절반씩 줄여 최소 점프 수를 구한다.
프로그래머스 구명보트 풀이: 정렬과 양끝 투 포인터 그리디
프로그래머스 구명보트에서 가장 무거운 사람과 가장 가벼운 사람을 함께 태울 수 있는지 확인한다. 정렬된 배열의 양끝 포인터로 필요한 보트 수를 센다.
프로그래머스 리프 노드 수 최대화 풀이: DFS와 그리디
프로그래머스 리프 노드 수 최대화에서 깊이별 자식 수를 DFS로 선택하고, 분배 노드를 다음 단계로 넘기는 그리디 전략을 적용한다.
프로그래머스 숫자 게임 풀이: 정렬과 그리디 매칭
프로그래머스 숫자 게임에서 두 팀의 숫자를 정렬하고, A팀을 이길 수 있는 가장 작은 B팀 숫자를 짝짓는다. 불필요하게 큰 수를 아껴 최대 승점을 만든다.
프로그래머스 숫자 문자열과 영단어 풀이: 문자열 순차 변환
프로그래머스 숫자 문자열과 영단어에서 왼쪽부터 숫자와 영단어를 구분해 정수로 바꾼다. 입력 순서를 유지하며 O(n) 시간에 값을 복원한다.
프로그래머스 공원 풀이: 가장 큰 돗자리 찾기
프로그래머스 PCCE 공원에서 큰 돗자리부터 각 시작 위치에 놓을 수 있는지 확인한다. 2차원 배열에서 정사각형 영역이 모두 비어 있는지 검사한다.
프로그래머스 퍼즐 게임 챌린지 풀이: 이분 탐색으로 최소 숙련도 찾기
프로그래머스 퍼즐 게임 챌린지에서 숙련도별 총 소요 시간을 판정하고 이분 탐색으로 최소 숙련도를 찾는다. 실패 횟수에 따른 시간 계산과 단조 조건을 설명한다.
프로그래머스 순위 풀이: 승패 전이 관계를 확정하는 플로이드-워셜
프로그래머스 순위에서 경기 결과를 방향 그래프로 나타내고 플로이드-워셜로 간접 승패 관계를 구한다. 승리·패배 수의 합으로 순위를 확정할 수 있는 선수를 찾는다.
프로그래머스 비밀 코드 해독 풀이: 조합 완전탐색과 교집합
프로그래머스 비밀 코드 해독에서 1부터 n까지 중 다섯 숫자를 고르는 조합을 탐색한다. 각 시도와 비밀 코드의 교집합 크기를 비교해 가능한 비밀 코드를 센다.
프로그래머스 비밀지도 풀이: 비트 OR와 고정 길이 이진수
프로그래머스 비밀지도에서 두 지도의 값을 비트 OR로 합쳐 벽과 공백을 구분한다. 이진수 변환 뒤 앞쪽 0을 채워 고정 길이 지도를 만든다.
프로그래머스 서버 증설 횟수 풀이: 만료 시점을 관리하는 구현
프로그래머스 서버 증설 횟수에서 시간별 운영 서버와 반납 시점을 관리한다. 필요한 서버 수와 현재 서버 수의 차이로 추가 증설 횟수를 계산한다.
프로그래머스 스킬트리 풀이: 선행 스킬 접두사 판정
프로그래머스 스킬트리에서 선행 스킬에 포함된 문자만 추려 순서를 확인한다. 추출 결과가 선행 스킬 순서의 접두사인지 판정한다.
프로그래머스 기지국 설치 풀이: 빈 구간 길이 계산 그리디
프로그래머스 기지국 설치에서 기존 기지국 사이의 빈 구간만 살펴보고, 한 기지국의 전파 범위로 나누어 필요한 수를 구한다. 아파트를 전부 순회하지 않는 경계 처리와 올림 나눗셈을 설명한다.
프로그래머스 주식가격 풀이: 하락 시점을 찾는 단조 스택
프로그래머스 주식가격에서 아직 하락 시점을 만나지 않은 인덱스를 단조 스택에 보관한다. 가격이 처음 낮아질 때 지속 시간을 확정해 모든 시점을 O(n)에 처리한다.
프로그래머스 단속카메라 풀이: 종료 지점 기준 그리디
프로그래머스 단속카메라에서 차량 경로를 종료 지점 기준으로 정렬한다. 아직 감시되지 않은 경로의 끝에 카메라를 두어 필요한 대수를 최소화한다.
프로그래머스 기차 선로 풀이: DFS와 백트래킹으로 경로 세기
프로그래머스 '기차 선로'에서 DFS와 백트래킹으로 가능한 경로를 탐색한다. 선로 연결 방향과 3번 십자 선로의 처리 방식을 설명한다.
프로그래머스 여행경로 풀이: 사전순 DFS와 후위 경로 구성
프로그래머스 여행경로에서 출발지별 도착지를 역순 정렬하고 스택 기반 DFS로 항공권을 모두 사용한다. 막다른 공항을 후위에 기록해 사전순 경로를 구성한다.
프로그래머스 올바른 괄호 풀이: 카운터로 여는 괄호 관리
프로그래머스 올바른 괄호에서 여는 괄호와 닫는 괄호의 잔량을 카운터로 관리한다. 닫는 괄호가 앞서는 순간 종료하고 마지막 잔량을 확인해 O(1) 공간에 판정한다.
프로그래머스 동영상 재생기 풀이: 시간 변환과 시뮬레이션
프로그래머스 PCCP 동영상 재생기에서 시각을 초로 바꿔 명령어를 시뮬레이션한다. 오프닝 자동 건너뛰기와 영상 끝 경계를 처리하는 방법을 다룬다.
프로그래머스 바이러스 파이프 풀이: 파이프 순서 DFS와 감염 BFS
프로그래머스 바이러스 파이프에서 DFS로 파이프 배치 순서를 정하고 BFS로 같은 종류의 파이프를 따라 감염을 퍼뜨린다.