0과 1의 쉼터

풀이 가중치가 없는 방향 그래프가 주어질 때, 모든 정점 간 연결이 가능한지 아닌지를 탐색 후 인접 행렬 형식으로 표현해주면 된다. Floyd Washall 을 사용해서 풀이했다. 가중치는 없지만, 결국 모든 탐색 가능한 정점에 대해 정점 간 연결이 존재하는 경우 또 다른 정점간의 간접적 연결이 되기 때문이다. 단, 단순히 정점간의 간접적 연결에 대한 유무 판단만 하면 되기에 아래의 조건만 충족한지 살펴보자 소스코드 소스코드 보기 출처 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net

풀이 입력으로 주어진 문자열 S 안에 2N + 1길이의 Pn이 겹침을 허용해서 몇 개 존재하는지 찾으면 되는 문제다. 최대 길이 M에 대한 Pn의 길이는 (100만 - 1) 이기 때문에, 아래처럼 모든 구간에서의 Pn을 구하면 시간초과가 발생한다. N = 2, M = 15, S = IOIOIOIOIOIOIOI 일 때, IOIOI IOIOI IOIOI ... 처럼 매번 2N + 1 길이만큼의 문자열이 주어진 문제의 조건을 만족시키는지 확인하면 시간초과가 발생할 것이다. 때문에, 이미 조건을 만족시키는 문자열을 다시 확인하지 않고 풀이하는 방법이 필요하다. 먼저, 올바른 Pn이 만들어지는 조건을 살펴보자 Pn은 'I' 부터 시작한다. 문자열 S의 M - 1 번째가 'I' 아니면, Pn은 만들어지지 않는다. ..

풀이 처음에 주어진 입력이 모두 0이거나 1일 경우 '0' 또는 '1'이 정답이 되지만, 위의 경우가 아닌 경우 사분면을 'Z' 순서대로 살펴보며 주어진 영역에 대해 모두 하나의 값이 존재할 때까지 recursive call 방식으로 풀이하면 된다. 문제에서 주어진 예제를 살펴보자. 색 (빨 - 주 - 연) 순서대로 분할할 것이며, 색상별 동그라미는 각 분할 시점의 기준 좌표가 된다. 기준좌표에 recursive를 거쳐 줄어든 크기(size)만큼의 영역에 대해 다시 탐색을 시도해 나가며 풀이하면 된다. 참고로 입력의 제한 중 다음과 같은 조건이 있기 때문에 "N은 언제나 2의 제곱수로 주어지며" recursive할 영역을 무조건 2로 나누어 범위를 재설정하면 된다. 소스코드 소스코드 보기 출처 1992번..

풀이 'Six Degrees of Separations' theory로도 불리는 이론이다. 자신과는 아무 연관성(inf or V) 없는 사람일지라도, 만약 친구가 한 명 이상 있다면(connected), 대부분 6단계(5명의 관계)를 걸쳐 알 수 있게 된다는 이론이다. 즉, 당신이 6단계를 넘어선다면 아싸일 확률이 매우 높... 문제에서 "모든 사람은 친구 관계로 연결되어져 있다." 라고 하여 주어지는 TC에 대한 별도의 예외처리는 없다. Floyd Warshall을 이용해 모든 친구 관계에 대해서 최단 단계를 구해주고, 각각의 유저가 모든 유저간에 대한 단계의 합으로이루어진 집합(step) 속 최솟값의 순번을 구하자. 소스코드 소스코드 보기 출처 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의..

풀이 최대 200개의 아이스크림 중 3개로 이루어질 수 있는 조합의 개수만 세면 된다. N의 최대값이 작으므로 주어지는 입력을 그래프로 구현 후 모든 경우를 다 살펴보자. ban_list [n1] [n2] : (n1, n2) 조합의 불가능 여부 단, 섞어먹으면 안되는 조합이 항상 오른차순으로 주어진다는 보장이 없어 양방향 그래프로 구현하자. 3개의 조합을 선별해야 하므로 순서는 상관없다. 또한, 양방향 그래프이기 때문에 그리디 로직(먼저 고른 수는 나중에 고른 수보다 항상 작음)을 적용시킬 수 있다. 조건을 모두 만족 (조합이 성립)하는 경우에만 아이스크림 조합의 수를 증가시켜 주자. 소스코드 소스코드 보기 출처 2422번: 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 첫째 줄에 정수 N과 M이 주어진..

풀이 수빈이가 동생한테 가는 방법은 현 위치(N)에 대해 3개의 방법(N + 1, N - 1, 2N)이 있다. 항상 N이 K에 가까워지는 방법이 정답이라는 보장이 없기 때문에 모든 경우에 대해 탐색을 해봐야 한다. Queue에 수빈이의 범위 내의 새로운 위치를 담아주고, 다시 꺼낼 때 이동 횟수를 기록한다. 단, 이미 방문한 위치를 재 방문할 때는 이동횟수가 같거나 크기 때문에 최소 이동횟수 기록을 보장하기 위해 방문하지 않은 경우에만 Queue에 담아두었다. Queue의 변화에 대해 궁금하다면 아래를 참고하자. 처음에 주어진 N(5)에 대한 3가지 이동 방법을 모두 기록하며, Queue에서 새로운 위치(nx)를 꺼낼때마다 이에 대한 이동 방법 또한 기록한다. 빨간색 대각선은 동일한 이동시간을 가진 위치..

풀이 배추흰지렁이는 인접한 배추(기준이 되는 배추로부터 상하좌우에 위치한 배추)로 퍼져나갈 수 있다. 따라서 인접한 배추들을 전부 탐색하고, visited에 탐색한 배추를 기록하고자 한다. 결국 인접한 배추들의 덩어리인 연결 요소(Connected Component)의 개수를 구하는 문제이다. 배추가 위치한 장소만을 탐색하기 위해 배추의 위치를 입력받을 때 배추의 위치를 location에 기록한 후, DFS의 시행횟수를 세어 풀이했다. 소스코드 소스코드 보기 출처 및 참고자료 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net

풀이 두 좌표를 기준으로 반지름만큼의 원이 형성될 때 원의 둘레가 겹치는 좌표의 개수를 구하면 된다. 아래의 그림은 주어진 Test Case에 대한 시각화 자료이다. 만약 입력으로 주어지는 두 원이, 동일한 좌표와 반지름을 가진다면 '류재명'이 있을 수 있는 위치는 무한대이다. 두 원의 정보에 대한 입력을 struct Circle을 통해 입력받고, 두 원의 중심거리(d)와 두 원의 반지름의 차(diff_radius), 두 원의 반지름의 합(sum_radius)을 구해서 다음과 같은 비교를 통해 문제를 해결할 수 있다. 입력받은 두 원의 정보가 동일하다면 류재명이 있을 수 있는 위치는 무한대이다. d == sum_radius 이거나, d == diff_radius(아래 그림 참고)이면 한 접점에서만 만난다..

풀이 "백준 6588, 골드바흐의 추측"과 비슷한 문제이다. 단, 가능한 골드바흐 파티션이 여러 가지인 경우에 두 소수의 차이가 가장 작은 것을 출력해야 한다. N = 4인 경우에는 예외로 처리해줬다. 소스코드 #include #include #include #define MAX 10001 bool cNum[MAX]; int main(){ int sq = sqrt(MAX-1); for (int i = 2; i

풀이 에라토스테네스의 채로 소수가 아닌 수들을 먼저 구한 후 풀이를 했다. 두 수의 합이 N과 같고, 두 수가 소수인경우에만 반복문을 종료해 답을 출력해주면 된다. 소스코드 #include #include #include #define MAX 1000001 int main(){ int sq = sqrt(MAX-1); bool not_prime[MAX] = {0,}; for (int i = 2; i