NEVER ENOUGH

안녕하세요. 오늘 풀어볼 문제는 백준 마인크래프트 입니다.https://www.acmicpc.net/problem/18111 마인크래프트는 구현 문제에요.줄글로는 직관적이지만 막상 소스 코드로 옮기려면 여러가지로 고려해야 할 것들이 있습니다. 마인크래프트라는 게임을 모른다면 줄글을 이해하는데도 시간이 걸릴 수 있겠네요. DP로 해결해야 하나? 라는 생각이 들 수도 있지만 각 원소가 서로 연관이 없고 높이끼리도 독립적이기 때문에 그럴 필요는 없습니다. 모든 높이 h애 대해 h를 만들기 위해 설치해야 할 블럭의 개수, 제거해야할 블럭의 개수를 구하면 h를 만들기 위한 시간도 알 수 있습니다. h를 만들기 위해 설치해야 할 블럭의 개수는 모든 원소에 대해 아래 라인을 수행하면 얻을 수 있습니다.if (map[..

안녕하세요. 오늘 풀어볼 문제는 스택 수열입니다.https://www.acmicpc.net/problem/1874 직관적으로 이해는 되지만 막상 구현할 때 멈칫하게 되는 문제에요.저는 배열로 간단한 스택을 만들어 사용했지만 stl을 사용하셔도 무방합니다. 문제에서 중요한 부분만 짚어 보겠습니다. 1. NO를 출력하는 조건NO를 출력하는 조건을 한 마디로 설명하자면'이미 버린 수를 뽑는 경우' 입니다. 스택에서 입력된 수를 뽑을 때는 '입력된 수까지 채운 다음 pop' 하거나, '입력된 수가 나올 때까지 pop' 해야 합니다.아래 코드에서는 항상 스택을 채우는 작업 다음에 빼는 작업을 하기 때문에 '입력된 수가 나올 때까지 pop'만 고려해주면 되겠죠. 그런데 만약 스택의 top이 입력된 수보다 작다면 이..

안녕하세요. 오늘 풀어볼 문제는 백준 구간합 구하기 5입니다.https://www.acmicpc.net/problem/11660 이 문제는 구간 합 구하기 4의 심화버전이에요.수행하는 기능은 간단하지만 테스트 케이스가 1개 이상이기 때문에 dp를 사용해야 합니다. 문제에서는 입력이 2차원 배열으로 주어지는데요,각 행마다 dp를 적용하면 같은 x 값을 가지는 행들에서의 합을 구할 수 있겠죠.그 합을 구하는 행의 범위에서 모두 더하면 구간 합을 구할 수 있습니다.dp 배열은 0번부터 i번까지 원소들의 합으로 정의합니다.만약 2번부터 5번까지의 합이 알고 싶다면 dp[5] - dp[1]로 구할 수 있어요.dp[2]가 아닌 dp[1]을 빼는 이유는 dp[2]의 값도 포함되어야 하기 때문입니다. #include ..

안녕하세요. 오늘 풀어볼 문제는 백준 N과 M (9)입니다.https://www.acmicpc.net/problem/15663 N과 M은 백준에서 아주 유명한 시리즈 문제입니다.이 시리즈는 모두 N개의 수 중에서 M개를 골라 수열을 출력하는 형식인데요,그 중에서도 이 아홉 번째 문제는 은근 까다로운 조건을 요구해서 유난히 정답률이 낮습니다. 우선 N과 M은 기본적으로 재귀를 통해서 해결하는 문제에요. 입력 받은 각 수에 대해서1. 해당 수를 사용했는지 체크해주고2. 정답 배열에 해당 수를 넣어주고3. 다음 깊이에 대해 재귀를 호출하고4. 해당 수를 사용하지 않는다고 체크해주면 됩니다. Base case는 깊이가 M과 같을 때 정답 배열을 모두 출력해주면 돼요. N과 M (9)에서는 중복된 수가 입력으로 ..

안녕하세요. 오늘 풀어볼 문제는 백준 색종이 만들기입니다.https://www.acmicpc.net/problem/2630 이번 문제는 분할 정복 문제인데요.분할 정복 알고리즘은 상대적으로 큰 문제를 더 작은 단위로 재귀적으로 호출하면서 해결하는 알고리즘입니다. 이 문제는 크게 두 가지 과제로 나눌 수 있습니다.첫 번째는 범위 안의 색종이가 한 가지 색으로만 되어있는지 판별하는 부분구요.두 번째는 색종이를 자르고 각 색종이에 대해 문제를 해결하는 부분입니다.두 번째 과제가 분할 정복 알고리즘이 되겠네요. 첫 번째 색종이 색을 판별하는 방법입니다.크기가 s인 색종이에서 색에 상관없이 칸의 개수는 s*s에요.그럼 색이 파란 칸(1)의 개수를 세었을 때 개수가 0 또는 s*s라면 해당 색종이는 하나의 색으로만..

안녕하세요. 오늘 풀어볼 문제는 백준 바이러스입니다.https://www.acmicpc.net/problem/2606 이 문제는 간단한 DFS 또는 BFS 문제입니다. DFS는 깊이 우선 탐색인데요.연관된 요소의 수준을 우선으로 가장 깊게 탐색하는 알고리즘입니다. BFS는 넓이 우선 탐색입니다.요소의 특정 수준을 모두 탐색한 후 다음 수준으로 넘어가는 알고리즘입니다. 저는 DFS를 사용했어요. 2차원 배열을 사용해서 네트워크의 위상을 표시해줬습니다.DFS로 위상을 따라가며 감염되지 않은 컴퓨터의 수를 하나씩 세어줬어요. 주의해야할 점은 '1번이 감염시킨 컴퓨터 수'를 구하는 것이기 때문에 1번을 포함하면 안되는데요.DFS를 하기 전에 감염 여부를 판단하는 배열에 표시를 해줬습니다. #include usi..

안녕하세요. 오늘은 백준 요세푸스 문제 0을 풀어보겠습니다.https://www.acmicpc.net/problem/11866 이 문제에서 가장 기술을 요구하는 부분은 마지막 사람 이후에 다시 첫 번째 사람으로 돌아오는 과정이에요. 아쉽지만 C++에는 이런 원형 큐를 지원하는 STL이 없습니다.그래서 일반 큐를 사용해서, 원형 큐처럼 동작하게 해주겠습니다.queue q;q.push(q.front());q.pop();  큐가 원형 큐처럼 동작하면서 원소들을 확인할 수 있습니다. 이 외에는 콤마를 출력하는 부분만 신경써주면 됩니다. 아래는 C++ 소스 코드#include #include using namespace std;int N, K;queue q;int main(void) { cin.tie(0); io..

안녕하세요. 오늘 풀어볼 문제는 백준 1로 만들기입니다.https://www.acmicpc.net/problem/1463 가장 간단한 형태의 dp 문제입니다. 1부터 1을 더한 수, 2를 곱한 수, 3을 곱한 수에 대한 연산 횟수를 계산하며 N번 째 수를 구할 수 있는 최소 연산 횟수를 구하면 되는데요. 저는 특정 수에서 1을 뺀 수, 2를 나눈 수, 3을 나눈 수를 참조해서 연산 회수를 계산하는 방법을 썼어요.이렇게 하는 편이 코드가 깔끔했습니다. 아래는 C++ 소스코드.#include using namespace std;int N;int dp[1000005];int main(void) { cin.tie(0); ios::sync_with_stdio(0); cin >> N; dp[1] = 0; for (..

안녕하세요. 오늘은 백준 집합 문제를 풀어보겠습니다.https://www.acmicpc.net/problem/11723 이 문제는 언뜻 간단해 보이지만 시간 제한 때문에 곤란해지는 문제인데요.아마 문제를 몇 번 시도한 이후에 블로그를 찾아오셨을테니 각설하고 풀이로 들어가보겠습니다. 이 문제는 입력될 숫자가 정해져 있기 때문에 실제로 자료구조에 입출력을 하는 게 아니라 자료구조에 저장된 숫자의 여부를 표시하며 풀어야합니다. 이 표시를 1부터 20의 정수 배열에 해도 괜찮겠지만 저는 임베디드 개발자 지망답게 비트 마스킹으로 문제를 해결해볼게요.비트마스킹https://ko.wikipedia.org/wiki/%EB%A7%88%EC%8A%A4%ED%81%AC_(%EC%BB%B4%ED%93%A8%ED%8C%85) ..

안녕하세요. 오늘은 백준 블랙잭 문제를 풀어보겠습니다.https://www.acmicpc.net/problem/2798 저는 STL의 next_permutation 함수로 조합을 구현해서 풀었는데요.더 간단한 방법이 있을지도 모르겠다는 생각이듭니다.next_permutation은 다양한 사용 방법이 있으니 찾아보시면 좋을 거 같습니다.저도 다음에 기회가 되면 자세히 다뤄볼게요. next_permutation을 이용한 조합은 굉장히 흔히 쓰이는 방법인데요. 저도 두고두고 잘 쓰고 있습니다. 구현도 굉장히 쉬워요. 우선 선택할 원소를 저장하는 배열 말고 조합을 위한 정수 배열을 하나 더 만들어야 합니다.정수 배열은 1로 초기화를 해주고요. 선택할 원소 개수 만큼 0을 넣어줍니다.문제에서는 카드 3장을 선택하..