판교의 메타몽

링크 : www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. � www.acmicpc.net 이 문제는 먼저 유의 사항을 파악해야하는데, 입력값이 다닥다닥 붙어있으며, 입력 값을 굳이 int형 숫자라고 명시하지 않았다는 점이다. 코드를 구현하고 답을 체크할때, 이상하게 프로세스가 제대로 종료되지 못하는 현상이 발생할 수 있다. 만약 테스트 케이스가 다음과 같이 공백을 두고 입력되었다면 문제가 없었을 것이다. 고안해본 해결책은 다음과 같다. (1) 문자열로 값을 입력 받는다. 이렇게 해서 입력 ..

링크 : www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진� www.acmicpc.net 문제 풀이는 다음과 같다. (1) 사람의 숫자가 1번부터 100번까지 주어질 수 있으므로, 배열의 크기는 101번까지 지정해준다. (vector로 풀어도 무방하다) (2) 1번과 3번이 부모자식 관계라면, 배열의 [1][3], [3][1]모두 값을 증가시켜준다. 두 가지를 모두 증가시켜야 하는 이유는 n에서 DFS를 시작하건 m에서 DFS를 시작하건 무방하게 답을 구하기 위함이다. (3..

링크 : www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 � www.acmicpc.net 문제 풀이는 다음과 같다. (1) 배열의 0,0부터 N,M까지 for문을 돌려서, 해당 위치가 1이고 방문해본적이 없다(false)면 DFS를 진행한다. (2) 해당 위치는 방문한 표시를 해두고(true), 해당 위치의 상하좌우 위치를 탐색하여 1번과 동일하게 1의 값을 가지고 방문해본적이 없으면 DFS를 진행한다. (3) 더이상 방문 가능한 공간이 없으면 DFS를 종료하고 벌레의 값을 +1 해준다. 이렇게 해..

링크 : www.acmicpc.net/problem/14620 14620번: 꽃길 2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다. 진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므 www.acmicpc.net 문제풀이는 다음과 같았다. 조건 : 꽃을 심을 자리에 이전에 심어본 적이 없다면 (false 상태) (1) 꽃의 방향대로 자리값을 합산해주고 동시에 꽃을 심었다고 true로 표시해준다. (2) '기존 sum + 꽃의 방향대로 추가된 자릿값', 씨앗 갯수 -1로 DFS 진행 -> 재귀를 통해 새롭게 꽃을 심을 자리를 찾으러감 (3) 다시 리셋(첫 번째로 꽃을 심을 자리를 변경)을 위해, 심었던 적이 있..

링크 : www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어�� www.acmicpc.net 이 문제를 푸는데 이해가 안된다면, 먼저 LV2 문제인 #11724 연결 요소의 개수 (C++)을 보고 오는 것을 추천한다. 푸는 로직이 11724번과 거의 동일하다. 문제 풀이는 다음과 같았다. (1) 연결된 모든 노드를 순회한다. (2) 이때 1번 노드와 연결되어 있으며, 접근한 적이 없었던 노드 (Bool문이 false로 표시됨)을 발견하면, 해당 노드를 DFS한다. (3) 해당 노드를 DFS하기 ..

링크 : www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주�� www.acmicpc.net 글만 봐서는 무슨 문제인지 감이 안잡히는데, 해당 예제 입력1을 따라 그림을 그려보면 위의 그림이 나온다. 보시다시피 결과적으로 나누어지는 연결 요소는 크게 2개로 나누어진다. 이처럼 각 선을 연결해봤을때 최종적으로 나누어지는 연결요소의 개수를 출력하는 것이 문제의 핵심이다. 문제 풀이는 다음과 같았다. (1) 모든 노드를 순회한다. (..

링크 : www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도� www.acmicpc.net 문제 풀이는 다음과 같았다. (1) 방문하지 않은 섬을 DFS한다. (2) 해당 섬을 방문한 것으로 표기한 뒤, 해당 섬의 전방위에 섬이 있을 경우 그 위치를 DFS한다. (3) 만약 해당 섬의 위치가 주어진 영역을 초과하거나, 섬이 아니었거나, 이미 방문했던 전적이 있으면 DFS를 종료한다. #include #include #include #include //memset using namesp..

#include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); long long N,M,min = 0, maxn = 0; cin >> N >> M; long long v[N]; for(int i=0; i> v[i]; maxn = max(maxn,v[i]); } while(min

#include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N,M = 0; vector n1; vector m1; cin >> N; for(int i=0; i> a; n1.push_back(a); } cin >> M; for(int i=0; i> b; m1.push_back(b); } sort(n1.begin(), n1.end()); // 이진탐색 진행을 위한 조건 - 정렬 for(int i=0; i

이진 탐색(Binary Serach) 정의 참고 링크 : www.youtube.com/watch?v=W7RGHiN0Mmw&t=96s 1) 저장된 값을 정렬한다. 2) 왼쪽 = 첫번째 값 / 오른쪽 = 맨 마지막에 위치한 값 / 중간값 = 그 중간의 값 3) 중간값과 원하는 값의 차이에 따라 탐색하는 값의 범위를 변경해 나간다. (ex : 원하는 값이 중간값보다 크다 -> 왼쪽 = 중간값 + 1 원하는 값이 중간값보다 작다 -> 오른쪽 = 중간값 -1) 4) 원하는 답이 나올때까지 3번의 과정을 반복한다 이진 탐색(혹은 이분 탐색, 이분 검색)은 탐색 기법 중 하나이며, 원하는 값을 탐색 범위를 두 부분으로 분할하여 찾는 방식이다. 단, 이미 오름차순 혹은 내림차순으로 정렬된 구조에서 사용 가능하다는 조건..