목록알고리즘 (6)

그림판유저의 은밀한 개발

[SWEA] swexpert 2805 - 농작물 수확하기

SW Expert Academy 2805 - 농작물 수확하기 N x N 크기의 농장에서 다음과 같은 규칙을 가지고 수확을 합니다. ① 농장은 크기는 항상 홀수이다. (1 X 1, 3 X 3 … 49 X 49) ② 수확은 항상 농장의 크기에 딱 맞는 정사각형 마름모 형태로만 가능하다. 위의 규칙을 그림을 그려 확인하면 다음과 같습니다. 이것은 N x N 안에 마름모 모양으로 별 찍기라고 생각하면 쉽습니다. 먼저, 마름모 모양의 별을 찍기 위해서는 일단 먼저 두 부분으로 나누어야 합니다. 위, 아래로 나누어 증가하는 부분과 감소하는 부분을 나눌 수 있습니다. 그 후에 아래와 같이 별은 중간에서부터 시작하므로 중간을 나누어 그것을 기준으로 열의 위치를 잡습니다. 처음은 (n/2, n/2), ... (i, n-..
알고리즘/swexpert 2019. 3. 7. 23:49
[BOJ] 백준 2573 - 빙산

백준 2573 - 빙산 이 문제는 빙산을 탐색하고, 빙산 내부의 값을 변경시키고 해당 빙산영역의 개수를 세어주는 문제입니다. 위의 문제에서 요구하는 부분은 두가지입니다. 1. 빙산을 녹인다. (빙산 근처인 상하좌우에 바다가 있는 개수만큼 빙산을 녹입니다.) 2. 빙산의 개수가 2개 이상으로 분리될 경우, 출력한다. 위의 요구하는 부분을 적용시켜 작성한 코드는 다음과 같습니다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293import ja..
알고리즘/acmicpc[백준] 2019. 3. 7. 23:15
[BOJ] 백준 2869 - 달팽이는 올라가고 싶다

백준 2869 - 달팽이는 올라가고 싶다 달팽이는 낮에 a 미터를 올라가고, 밤에 b미터 떨어집니다. (정상을 도달하는 순간 미끄러지지 않으므로, 끝나게 됩니다.) 이런 문제는 DP를 접근하는 것과 같이 작은 문제부터 생각해야 합니다. 먼저, 달팽이는 하루가 지난 다음날 아래와 같이 이동한 것을 알 수 있습니다. 즉, 1일이 지날 때마다 a - b 만큼을 이동하게 됩니다.일반적으로, 1일에 a - b 만큼을 이동한다는 식을 찾게되면, n * (a - b) >= v 인 n 을 찾으려는 오류를 범하게 됩니다. 여기서 주의할 점은 정상을 도달하는 순간 미끄러지지 않는다는 점입니다. (n + 1)번째의 날에 나무 위에 도달한다고 가정한다면,n 번째 날이 지난 달팽이의 이동거리는 n * (a - b) 이게 되고,..
알고리즘/acmicpc[백준] 2019. 3. 7. 22:51
[BOJ] 백준 1799 - 비숍

백준 1799 - 비숍 체스판이 주어졌을 때 비숍은 대각선에 있는 다른 비숍을 잡을 수 있다고 합니다구해야하는 값은 비숍들이 서로를 잡을 수 없도록 하여 체스판 위에 최대로 놓을 수 있는 비숍의 개수를 구하는 문제입니다. N-queen 처럼 백트래킹을 쓰면 쉽게 구현할 수 있을 것 같았지만, 만약 10 x 10 에서 모든 자리가 1로 채워져 모든 자리에 비숍을 놓을 수 있다고 하면 10초안에는 절대로 구할 수 없게됩니다. 따라서 백트래킹을 들어가기 전에 몇가지 경우를 나누어주어야 합니다. 먼저, 체스판을 보게되면 흰색과 검정색으로 나뉘어진 부분을 볼 수 있습니다. (위의 체스판이 아닌 아래의 체스판을 참고해야 합니다.) 검정색 판에 비숍이 놓이게 되면 아래와 같이 흰색 부분에 놓인 비숍은 대각선 위에 위..
알고리즘/acmicpc[백준] 2019. 3. 7. 11:20
[BOJ] 백준 10216 - Count Circle Groups

백준 10216 - Count Circle Groups 각 적군의 진영에서 Ri 이내 거리에 포함되는 모든 지역을 통신영역으로 가진다면진영의 좌표를 (Xi, Yi)라고 할 때 , 적군의 통신영역은 (Xi, Yi)를 중심으로 하며, Ri를 반지름으로 갖는 원이라는 것을 알 수 있습니다. 이를 통해, 적군의 진영(i, j)끼리 통신이 가능하기 위해서는 통신영역의 중심 즉, 두 진영사이의 거리가 두 Ri, Rj 의 합보다 작아야 한다는 것을 알아야 합니다. 아래 그림을 통해 생각해봅시다. 위의 색칠된 부분이 두 원이 겹치는 부분으로 이 경우에 통신이 가능하다고 하며, 그림을 보면 알 수 있다시피 통신이 가능한 경우는 dist ((Xa, Ya) 와 (Xb, Yb) 의 거리) Ra + Rb 입니다. 두 원사이를 ..
알고리즘/acmicpc[백준] 2019. 3. 7. 00:36
[BOJ] 백준 5557 - 1학년

백준 5557 - 1학년 상근이는 덧셈, 뺄셈을 통해 줄 지어진 숫자를 연산하여 가장 마지막 숫자가 나오도록 하고자 한다. 그러나, 연산 도중에 나올 수 있는 숫자는 0이상 20이하라고 한다. 여기서 크기가 21인 배열을 생각할 수 있다. 예시인 "8 3 2 4 8 7 2 4 0 8 8" 을 생각해보자. 처음 8이 올 때, 8이 될 수 있는 경우의 수는 1이다. 8 다음 3이 올 때, 3에서 할 수 있는 연산은 +3, -3 이다. 그 다음 2가 올 때 할 수 있는 연산은 +2, -2 이다. 4가 올 때 할 수 있는 연산은 +4, -4 로 범위를 넘어가면 빼주면 된다. 위의 방식을 코드에 적용하면 다음과 같다. 12345678910111213141516171819202122232425262728293031..
알고리즘/acmicpc[백준] 2019. 3. 6. 18:10
이전 Prev 1 Next 다음