https://www.acmicpc.net/problem/1018 1018번 문제는 체스판 다시 칠하기 문제입니다. 엄청 어렵지는 않지만, 차근차근 코드를 짜는 것이 중요한 문제라고 생각합니다. 문제를 간단히 설명하자면, 지민이가 흰색이나 검정색으로 색칠되어 있는 단위 정사각형으로 이루어진 N * M 크기의 보드를 찾았고, 이 보드를 8 * 8 크기로 잘랐을 때 체스판이 되기 위해 추가적으로 칠해야할 부분의 최소 개수를 구하는 문제입니다. 체스판의 정의는 우리가 잘 알고 있는 체스판처럼 흰색과 검정색으로 번갈아져 색칠되어 있으면 되어져 있는 보드를 의미합니다. 이 때, 체스판은 제일 왼쪽 상단 정사각형의 색이 흰색 혹은 검정색으로 칠해져 있는 총 두가지의 종류로 이루어질 수 있습니다. 저는 이 점을 힌트..
https://www.acmicpc.net/problem/1017 1017번 문제는 소수 쌍 문제입니다. 수의 리스트를 입력 받았을 때, 이를 짝지어 만들 수 있는 각 쌍의 합이 모두 소수가 되게 하는 경우, 첫번째 숫자와 짝지어진 숫자를 답으로 출력하는 문제입니다. 문제의 예시에는 만약 {1, 4, 7, 10, 11, 12} 의 숫자 리스트를 받았다면, 1 + 4 = 5, 7 + 10 = 17, 11 + 12 = 23 또는 1 + 10 = 11, 4 + 7 = 11, 11 + 12 = 23 의 경우가 가능합니다. 즉, 각 경우에서 첫번째 숫자(1)와 짝지어진 4, 10이 답이 됩니다. Hint! 이 문제도 역시 DFS로 접근이 가능합니다. 답에서 중요한 점은 모든 쌍들의 합이 소수가 되었을 때, 첫번째..
https://www.acmicpc.net/problem/1014 오랜만에 알고리즘 글을 올리게 되네요. 저번 학기가 너무 여유가 없었어서 꾸준히 올리고 싶었는데... 풀 때까지 하루종일 잡을거 생각하니 바빠서 손에서 잘 안잡히더라고요. 방학이기도 하고 충분히 쉬었다 싶어서 다시 시작해보려고 합니다. 이번 문제는 제가 이전에 점프하고 넘어갔던 1014번 컨닝입니다. 이 문제는 제가 여러번 시도를 했는데 실패했고 도저히 반례도 찾을 수가 없어서 포기한 문제입니다. 1016번까지 풀고 그래도 마저 풀고 싶다는 생각에, 이래저래 검색도 해보고 공부도 하다가 겨우겨우 풀어냈네요. 그 과정을 다 서술하고 싶지만, 그 내용이 꽤 많아서 저는 최대한 간단히 적고 개념 이해에 도움이 많이 되었던 사이트들을 링크하도록 ..
https://www.acmicpc.net/problem/1016 1016번 문제는 제곱 ㄴㄴ수라는 이름으로 소개되어 있습니다. 최소와 최댓값을 입력받았을 때, 최솟값과 최댓값을 포함한 사이의 값들 중 제곱 ㄴㄴ수의 개수를 찾는 문제입니다. 문제에 의하면 제곱 ㄴㄴ수는 "어떤 수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때의 X"를 의미합니다. 일반적으로, 제곱수는 자연수의 제곱을 의미합니다. 문제만 봤을 때, 구현 자체는 생각보다 간단할 수 있습니다. min부터 max까지 숫자를 순서대로 나열한 list에서 max보다 작거나 같은 제곱수의 배수들을 모두 제외하면 된다고 생각할 수 있지요. 하지만, min의 범위가 1,000,000,000,000 까지 허용되기 때문에 이 방법은 다시 생각해 봐야합니..
