문제: 보석 도둑 (백준 1202번)문제 분석이 문제는 풀이법이 바로 떠오른다면 쉽게 해결할 수 있지만, 그렇지 않다면 접근법을 찾기 어려운 웰메이드 문제이다.알고리즘 자체는 복잡하지 않으나, 핵심 아이디어를 도출하는 것이 도전 과제다.핵심 아이디어정렬가방과 보석을 무게 순으로 오름차순 정렬한다.작은 가방부터 차례로 탐색하며 해당 가방에 들어갈 수 있는 보석들을 선택한다.우선순위 큐현재 가방에 들어갈 수 있는 보석들을 모두 우선순위 큐에 삽입한다.이때, 우선순위 큐는 보석의 가치를 기준으로 내림차순 정렬되도록 설정한다.우선순위 큐의 맨 앞에 있는 보석은 현재 가방이 담을 수 있는 최고 가치의 보석이다.탐욕적 선택작은 가방부터 순서대로 처리하며, 현재 가방이 담을 수 있는 최고 가치의 보석을 선택한다.이를..

문제: 낚시왕 (백준 17143번)간만에 빡구현 문제를 풀어보았다.각각의 알고리즘 자체는 어렵지 않지만, 구현할 내용이 많아 세심한 작업이 필요했다.이 문제의 핵심은 상어의 이동 계산이다. 이동을 시뮬레이션할 때 1칸씩 이동하지 않고 최종 위치를 계산하는 방식으로 처리해야 한다.이 부분만 주의하면 큰 시간 초과 없이 문제를 해결할 수 있다.상어 클래스 정의상어의 위치, 속도, 이동 방향, 크기를 관리하기 위해 Shark 클래스를 작성했다.생성자에서는 초기 위치와 속도, 방향, 크기를 입력받아 초기화한다.또한, 상어의 이동을 처리하는 Move 메서드를 구현하여 방향과 속도에 따라 위치를 업데이트한다.class Shark {public: int x, y; int speed; int direc..

문제: 사이클 게임 (백준 7579번)우리는 주어진 앱들의 메모리 사용량과 비활성화 비용을 바탕으로, 필요한 메모리 M 이상을 확보하기 위해 최소 비용을 계산해야 한다.이 문제는 0-1 Knapsack 문제를 응용한 형태로 볼 수 있다.핵심 아이디어앱의 메모리 사용량을 배낭 문제의 "가치", 비활성화 비용을 "무게"로 해석한다.목표는 최소 비용으로 M 이상의 메모리를 확보하는 것이다.비용(c)을 역순으로 탐색해 중복 계산을 방지한다.dp[j]는 "비용이 j일 때 확보할 수 있는 최대 메모리"를 나타낸다.코드 전체#include using namespace std;int main() { ios::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m;..

문제: 빙산 (백준 2573번)간만의 구현 문제이다. 구현 문제는 말 그대로 구현하는 데 시간이 많이 걸리기 때문에 사용하는 알고리즘 자체는 크게 어렵지 않은 경우가 많다. 이번 문제도 그런 케이스이며, 전체적인 로직은 다음과 같다.문제 의도배열에 1 이상의 수가 남아있는 동안 반복time을 증가시키고2차원 배열을 돌며 상하좌우의 0의 개수와 해당 좌표를 저장저장해둔 0의 개수만큼 해당 좌표의 값을 감소 (0 미만이 되지 않도록)2차원 배열을 돌며 BFS로 그룹 개수 체크그룹 개수가 2개 이상이면 반복문을 정지배열의 1 이상의 수가 있으면 time을 출력아니면 0을 출력알고리즘 개요시간(time) 증가매번 반복할 때마다 시간을 증가시킨다.녹을 빙산 계산 각 좌표에서 상하좌우로 바다가 몇 칸 있는지 계산하..

문제: 사이클 게임 (백준 20040번)지문을 딱 보자마자 눈살이 찌푸려진다. 처음 이 문제의 지문을 읽었을 때 문제의 의도를 도출하는 데 꽤 시간이 걸렸다. 글자도 많고, 마치 비문학을 읽는 것처럼 의도하는 바가 무엇인지 이해하기 쉽지 않다.문제 의도와 핵심이 문제에서 요구하는 결론은 n개의 정점(노드)의 사이클 생성 여부를 알아내라는 것이다. 지문이 복잡하게 설명되었지만, 실제로는 간단한 Union-Find 알고리즘을 활용하여 사이클을 판별하는 문제다.같은 알고리즘을 사용하는 골드 5 난이도의 문제도 있는 걸 보면, 지문 이해 난이도가 추가되어 골드 4로 책정된가 아닌가 싶다.문제 요구 사항n개의 정점과 m개의 간선이 주어진다.간선이 입력될 때마다 사이클이 발생하는지 확인한다.사이클이 발생하면 해당 ..

C++에서 제공하는 정렬 함수: IntroSortC++의 알고리즘 헤더에서는 sort() 함수를 지원한다. 정말 많은 sort 알고리즘이 존재하지만 C++에서 제공하는 정렬 함수는 어떤 알고리즘을 사용하는지 알아보자.정렬 알고리즘의 종류와 시간 복잡도여러가지 알고리즘에 대한 간략한 설명과 시간 복잡도를 보면 다음과 같다.알고리즘시간 복잡도 (최선)시간 복잡도 (평균)시간 복잡도 (최악)공간 복잡도퀵 정렬 (Quick Sort)O(n log n)O(n log n)O(n²)O(log n)힙 정렬 (Heap Sort)O(n log n)O(n log n)O(n log n)O(1)삽입 정렬 (Insertion Sort)O(n)O(n²)O(n²)O(1)C++의 IntroSort이런 널리 알려진 정렬 알고리즘과 달리..

문제 링크https://www.acmicpc.net/problem/17404문제 분석비슷한 유형의 RGB 거리보다 조금 더 심화된 DP 문제라고 할 수 있다.이전 문제에서 각 1번째 집의 색깔이 마지막 집(N-1)의 색과 동일하면 안 된다는 조건이 추가된 응용 버전인데, 시작을 1번째 집의 색깔을 R, G, B로 선택했을 때 각각에 대한 DP 배열을 이전 문제와 같이 채우면 되는 문제이다.DP 배열 구성DP 배열의 크기는 3(1번째 집의 색깔을 고르는 경우의 수) * n * 3이다.1번째 집의 색을 R로 선택했을 때의 경우를 예로 들면, 2번째 집에서는 1번째 집의 G, B에 해당하는 값을 선택하면 안 된다.여기서 아이디어가 필요한데, 본인은 DP 배열에서 1번째에서 선택한 집을 제외한 나머지를 임의의 ..

문제 개요문제 링크: 스도쿠 (2239)9x9 스도쿠 퍼즐을 완성하는 전형적인 백트래킹 문제.입력에서 0은 빈 칸을 나타내며, 이 빈 칸에 1부터 9까지 숫자를 채워야 한다.사전순 출력: 가장 먼저 완성된 스도쿠를 출력. 문제 접근이번 문제는 전형적인 백트래킹 문제로, 빈 칸에 가능한 숫자를 하나씩 채워넣으면서 모든 경우를 탐색하는 방식으로 해결할 수 있다.다만 이번 문제는 입력이 9x9의 문자열 형태로 주어지기 때문에, 이를 처리하여 숫자로 변환하고,각 빈 칸의 좌표를 따로 저장하여 백트래킹을 효율적으로 수행할 필요가 있다.아래 코드는 입력을 처리하는 부분과 백트래킹의 구조를 살펴본다.for (int i = 0; i > s; for (int j = 0; j 여러 백트래킹 문제를 풀어보면서 느낀 점..

파이프 옮기기 문제 정리 및 풀이문제 개요파이프 옮기기 1: nn의 최대 크기가 16으로, 단순한 탐색 알고리즘으로도 풀이 가능.파이프 옮기기 2: nn의 최대 크기가 32로, 단순 탐색은 시간 초과 발생.두 문제는 기본적인 로직은 동일하지만, 입력 크기에 따라 효율적인 접근 방식이 필요하다. 파이프 옮기기 1 (탐색 방식)탐색 방식으로 모든 경로를 BFS로 탐색하여 풀이한다.탐색할 때 파이프의 세 가지 상태(가로, 대각선, 세로)를 기준으로 이동 가능 여부를 판단한다.코드 설명BFS 탐색queue를 이용해 파이프의 현재 상태를 관리한다.이동 가능한 위치를 계산하고, 조건을 만족하는 경우 dpdp 배열에 이동 경로를 추가한다.결과 출력dp[n−1][n−1]dp[n-1][n-1]: 도착점까지의 경로 수 출..

[Silver II] 신나는 함수 실행 - 9184문제 설명지문에 주어진 의사 코드 형태의 재귀 함수를 구현해서 (a, b, c) 값에 따른 결과를 출력하는 문제다.하지만, 재귀 함수를 그대로 돌리면 당연히 타임아웃이 날 게 뻔하므로, 다른 방법을 생각해야 한다. 첫 번째 조건 확인먼저, 지문에서 다음 조건을 확인할 수 있다:if a 이 조건은 a, b, c 중 하나라도 0 이하일 때, 결과가 항상 1이라는 것을 의미한다.이 부분은 간단히 처리 가능하다.DP 문제임을 파악하기이 문제를 풀 때 DP 문제라는 걸 눈치챌 수 있는 포인트는 지문이 짧고 이전 값을 재활용하는 식이 들어가 있다는 점이다.보통 이런 문제는 DP로 접근하면 된다.재귀 호출로 매번 계산하면 시간 초과가 날 게 뻔하기 때문에, DP 배열..