백준 풀이

📌 문제 정보 번호: 1818 제목: 책정리 난이도: Gold 2 분류: 이분탐색, 가장 긴 증가하는 부분 수열(LIS) 💡 접근 방식 > 최소 횟수로 책을 정렬하는 문제입니다. > 움직이지 않아도 되는 책의 최대 개수 = LIS의 길이이므로 > 정답 = N - LIS 길이입니다. 🔹 1단계 – 핵심 관찰 이미 올바른 순서로 놓인 책들은 움직...

📌 문제 정보 번호: 6523 제목: 요세푸스 한 번 더! 난이도: Gold 2 분류: 구현, 자료구조, 해시 💡 접근 방식 > ax²+b mod N 점화식으로 다음 사람을 선택하는 게임에서 술을 마시지 않는 사람의 수를 구하는 문제입니다. > 처음에는 HashMap으로 방문 횟수를 관리했으나 메모리 초과가 났고, > 플로이드 순환 찾기 알고리즘(...

📌 문제 정보 번호: 32645 제목: 트리 게임 난이도: Gold 3 분류: 트리, 게임 이론, DFS 💡 접근 방식 > 트리에서 두 플레이어가 번갈아가며 간선을 제거하는 게임에서 승패를 구하는 문제입니다. > 현재 노드의 자식 중 하나라도 패배 상태(0)가 있으면 현재 노드는 승리 상태(1)입니다. > 처음에는 트리가 방향 그래프인 줄 알고 풀...

📌 문제 정보 번호: 4902 제목: 삼각형의 최대 합 난이도: Gold 1 분류: 다이나믹 프로그래밍(DP), 누적 합 💡 접근 방식 > N행 삼각형에서 계단 모양으로 선택한 원소들의 합의 최댓값을 구하는 문제입니다. > 각 행의 누적합을 1차원 배열에 저장해두고, > 홀수 인덱스(아래 방향)와 짝수 인덱스(위 방향) 두 가지 방향으로 탐색합니다...

📌 문제 정보 번호: 17954 제목: 투튜브 난이도: Gold 1 분류: 수학, 그리디 💡 접근 방식 > 2×N 배열에 1~2N을 배치해서 점수의 합을 최대화하는 문제입니다. > 큰 수를 앞쪽 열에 배치할수록 이후 열에서 계속 더해지므로 최대한 앞에 배치해야 합니다. > 배치 식을 직접 생각하지 못해서 찾아봤습니다. 🔹 1단계 – 점수 계산 ...

📌 문제 정보 번호: 1655 제목: 가운데를 말해요 난이도: Gold 2 분류: 자료구조, 우선순위 큐(힙) 💡 접근 방식 > 수를 하나씩 입력받을 때마다 중앙값을 출력하는 문제입니다. > 최대 힙과 최소 힙 두 개를 유지하면서 중앙값을 관리합니다. 🔹 1단계 – 두 힙의 역할 maxHeap — 중앙값 이하의 수들 (최대 힙) minHeap...

📌 문제 정보 번호: 16566 제목: 카드 게임 난이도: Gold 1 분류: 자료구조, 분리 집합(Union-Find) 💡 접근 방식 > 민수의 카드보다 큰 철수의 카드 중 가장 작은 카드를 찾는 문제입니다. > 단순 반복문 → TreeSet → Union-Find 순으로 최적화했습니다. 🔹 1단계 – 단순 반복문 O(K×N) N이 최대 4...

📌 문제 정보 번호: 4991 제목: 로봇 청소기 난이도: Gold 1 분류: 그래프 탐색, BFS, 비트마스킹, 다이나믹 프로그래밍(DP) 💡 접근 방식 > 더러운 칸을 모두 청소하는 최소 이동 횟수를 구하는 문제입니다. > 더러운 칸이 최대 10개이므로, 시작점과 더러운 칸들 사이의 최단거리를 BFS로 미리 구해두고 > 비트마스크 DP로 모든 ...

📌 문제 정보 번호: 17842 제목: 버스 노선 난이도: Gold 2 분류: 트리, 그래프 이론, 수학 💡 접근 방식 > 트리에서 리프 노드(차수가 1인 정점)의 개수를 세고, > 이를 이용해 필요한 최소 개수를 계산하는 문제입니다. 트리의 끝점인 리프 노드들끼리 짝을 지어 연결한다고 생각하면, 리프가 1개면 1 리프가 2개면 1 리프가 3개...

백준 15823번 '카드 팩 구매하기' 풀이입니다. 이분 탐색으로 팩 길이 L을 결정하고, 슬라이딩 윈도우로 중복 없는 연속 구간을 M개 만들 수 있는지 확인합니다. 처음에는 가능한 N을 모두 시도하려 했지만 시간 초과가 예상돼 이분 탐색을 적용했고, 중복 없는 구간의 효율적 탐색에 슬라이딩 윈도우가 필요함을 깨달았습니다. 📌 문제 정보 번호: 158...

백준 4256번 '트리' 풀이입니다. 전위/중위 순회 결과로 후위 순회를 구하는 문제입니다. 전위 순회의 첫 원소가 루트이고, 중위 순회에서 루트 위치로 서브트리를 나눠 재귀 호출하면 됩니다. pos 배열로 중위 순회에서의 위치를 O(1)에 찾아 전체 O(N)에 해결했습니다. 각 순회 순서와 재귀 범위 설정이 헷갈렸습니다. 📌 문제 정보 번호: 425...

백준 3178번 '코코스' 풀이입니다. 앞쪽 K글자는 공통 접두사를, 뒤쪽 K글자는 공통 접미사를 최대한 공유하도록 만들어야 합니다. 각 단어를 앞뒤로 나누고, 뒷부분은 뒤집어서 저장한 뒤 각각 정렬해 인접 문자열끼리 비교했습니다. 그래프를 직접 구성하려 했으나 복잡해서 레퍼런스를 통해 이 방식을 알게 되었습니다. 📌 문제 정보 번호: 3178 제목:...

백준 18808번 '스티커 붙이기' 풀이입니다. 각 스티커를 최대 4번 회전하며 노트북의 왼쪽 위부터 붙일 수 있는 위치를 완전 탐색하는 시뮬레이션 문제입니다. 배열을 90도 회전하는 공식 (r, c) → (c, R-1-r)을 기억해두면 유용합니다. 붙일 수 있으면 즉시 붙이고 다음 스티커로 넘어가는 그리디 구조입니다. 📌 문제 정보 번호: 18808...

백준 14438번 '수열과 쿼리 17' 풀이입니다. 구간 최솟값 질의와 값 변경이 최대 100,000번씩 주어지므로, 매 쿼리마다 순회하면 시간 초과가 납니다. 세그먼트 트리를 이용해 구간 최솟값과 점 업데이트를 모두 O(log N)에 처리했습니다. 트리 배열 크기를 4*N으로 잡는 이유, 완전 포함 조건에서 바로 반환하는 원리를 새롭게 이해했습니다. �...

백준 1103번 '게임' 풀이입니다. 동전의 최대 이동 횟수를 구하되, 무한 루프 가능 여부도 판별해야 합니다. DFS 탐색에 메모이제이션(DP)을 결합하고, 현재 경로에서 재방문 시 사이클로 판단해 -1을 반환했습니다. 단순 DFS로는 시간 초과가 났고, DP를 적용해 이미 계산한 위치를 재사용해 O(N×M)에 해결했습니다. 📌 문제 정보 번호: 1...

백준 2629번 '양팔저울' 풀이입니다. 추들로 만들 수 있는 모든 무게 차이를 DP로 구한 뒤, 구슬의 무게가 해당 차이와 같은지 확인하는 방식입니다. 상태를 구슬 무게가 아닌 양쪽 무게 차이로 정의하는 것이 핵심으로, 0/1 배낭 문제의 변형입니다. 각 추를 사용할 때 같은 편(+w)과 반대편(|d-w|)에 추가하는 두 가지 전이가 발생합니다. 📌 ...

백준 1082번 '방 번호' 풀이입니다. 예산 M으로 숫자를 구매해 만들 수 있는 가장 큰 수를 구하는 그리디 문제입니다. 자릿수가 길면 무조건 더 크므로, 먼저 자릿수를 최대화한 뒤 남은 돈으로 왼쪽 자리부터 더 큰 숫자로 업그레이드하는 방식으로 해결했습니다. 자릿수 최대화 후 자리 업그레이드라는 그리디 패턴을 새롭게 익혔습니다. 📌 문제 정보 번호...

백준 17472번 '다리 만들기 2' 풀이입니다. 섬을 정점으로, 섬 사이 최소 다리 길이를 간선으로 구성한 뒤 최소 신장 트리(MST)를 구하는 문제입니다. BFS로 섬 라벨링, 직선 탐색으로 다리 후보 구성, 크루스칼 알고리즘으로 최소 연결 비용을 계산했습니다. 섬 사이 최소 다리까지는 구했지만 MST 개념을 몰라서 크루스칼을 찾아 적용했습니다. 📌...

백준 25587번 '배수로' 풀이입니다. 두 도시를 합칠 때 전체 배수 용량과 강수량의 합을 비교해야 하므로, 유니온 파인드로 대표에게 데이터를 모아 관리했습니다. 공사할 때마다 홍수 카운트를 실시간으로 갱신하는 totalFlood 변수를 활용해 매번 전체 순회 없이 O(M)에 해결했습니다. 📌 문제 정보 번호: 25587 제목: 배수로 난이도: Go...

📌 문제 정보 번호: 1036 제목: 36진수 난이도: Gold 2 분류: 수학, 구현, 그리디 알고리즘, 문자열, 임의 정밀도 / 큰 수 연산 💡 접근 방식 > 각 자릿값(0~35)을 Z(35)로 바꿀 때 합의 증가량을 미리 계산하고, 이득이 큰 K개를 그리디로 선택. > 처음에는 실제 교체 후 합을 다시 구하려 했으나, "이득 합산" 방식이 훨...

📌 문제 정보 번호: 16209 제목: 수열 섞기 난이도: Gold 3 분류: 그리디 알고리즘, 정렬 💡 접근 방식 > 내부 원소는 이웃이 2개 → 절댓값이 큰 값일수록 가운데에 배치해야 이득 > 음수끼리는 곱이 양수이므로 양수 그룹 / 음수 그룹을 분리해 각자 지그재그 배열 후 연결 > 처음엔 전체를 단순 내림차순 정렬 후 지그재그를 적용했는데,...

📌 문제 정보 번호: 1300 제목: K번째 수 난이도: Gold 1 분류: 이분 탐색 💡 접근 방식 > "mid 이하인 값이 배열에 몇 개 있는가?"를 O(N)으로 계산할 수 있다면, 이분탐색으로 K번째 값을 찾을 수 있음 > 배열을 실제로 만들지 않고, 조건 함수만으로 정답을 좁혀나가는 Parametric Search 방식 🔹 단계별 풀이 ...

📌 문제 정보 번호: 28132 제목: 기벡을 안배운다고? 난이도: Gold 4 분류: 수학, 해시를 사용한 집합과 맵, 정수론, 유클리드 호제법 💡 접근 방식 > 벡터 쌍마다 내적을 직접 계산하면 O(N²)로 시간 초과 → HashMap으로 방향이 일치하는 벡터를 묶어서 O(N) 처리 > (x, y) 에 수직인 벡터는 (y, -x) 방향임을 이용...

📌 문제 정보 번호: 1006 제목: 습격자 초라기 난이도: Platinum 3 분류: 다이나믹 프로그래밍 📝 문제 요약 원형 도넛 모양 진영(외각 N, 내각 N, 총 2N칸)을 점령하는 데 필요한 최소 소대 수 구하기. 한 소대는 한 칸 또는 인접한 두 칸을 동시 점령 가능 (단, 두 칸 적군 합 ≤ W) 💡 접근 방식 > 직선이면 4상태 ...

📌 문제 정보 번호: 1028 제목: 다이아몬드 광산 난이도: Platinum 5 분류: 다이나믹 프로그래밍 📝 문제 요약 R×C 격자(0/1)에서 1로 이루어진 마름모(다이아몬드) 경계 중 가장 큰 크기 찾기. 크기 k 마름모는 가로 폭 (2k−1), 세로 높이 (2k−1)의 속이 빈 마름모 💡 접근 방식 > 각 칸에서 4방향(↖ ↗ ↙ ↘...

📌 문제 정보 번호: 10350 제목: Banks 난이도: Ruby 5 분류: 수학, 애드 혹, 누적 합, 불변량 찾기 💡 접근 방식 > 백준 서버 종료 전에 마지막으로 루비 문제 한 번은 풀어보고 싶어서 도전. 마법 이체가 "음수만큼 가져와 다시 분배"하는 구조라 전체 합이 바뀌지 않는 불변량부터 잡고 시작. 수식만으로는 안 풀려서 작은 케이스 ...