1018번: 체스판 다시 칠하기 (acmicpc.net) 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net #문제 간단 정리 문제 상황: 지민이는 MxN 크기의 보드를 발견했습니다. 이 보드는 검은색(B)과 흰색(W)의 정사각형으로 구성되어 있습니다. 지민이는 이 보드에서 8x8 크기의 체스판 부분을 잘라내고 싶습니다. 조건: 체스판의 규칙에 따라 각 칸은 검은색과 흰색으로 번갈아가면서 칠해져야 합니다. 체스판의 맨 왼쪽 위 칸의 색깔에 따라 두 가지 색칠 방식이 있습니다. 목표: 8x8 크기로 잘라낸 ..
https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net #문제 간단 정리 핵심: 최단거리 문제는 BFS 를 사용하자 DFS를 사용하면 시간 초과가 난다 쉽게 생각해보면 하나의 길을 끝까지 갔다가 다시 되돌아 와서 다시 가니까 BFS보다 시간이 훨씬 더 걸릴 거라는 것을 알아낼 수 있다. #문제 해결 방법 전역 변수 선언: maze[100][100]: 미로 정보 저장 (1은 이동 가능, 0은 이동 불가능). check[100][100]: 해당 위치를 방문했는지 여부를 저장. dist[..
전체 코드 #include #include #include using namespace std; typedef long long ll; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int arr[10001] = { 0, }; int n; cin >> n; for (int i = 1; i > input; arr[input]++; } for (int i = 1; i
https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 문제 간단 정리 원으로 앉아있고 K번째마다 제거되기 때문에 K 번째가 아닐때는 제외하고 큐를 사용하여 뒤를 넘겨주면 구현이 가능할테지만... 큐를 사용하지 않고 풀었다, 큐를 사용해서 푼 블로그 참조 https://cocoon1787.tistory.com/234 하지만 나는 그냥 큐 사용을 안하고 구현될 것 같아서 다르게 풀었다. 문제 해결 방법 대략 내가 직접 하나하나 세가면서 한다 생각하고 구현하였다. 수를 제거함을 알기위해서 count 변수, 지금 가리키고 있는 수인 포인터 ..
문제 간단 정리 정렬문제 아마도 내장함수를 사용하지 않는다면 n logN의 시간복잡도를 갖는 정렬로 풀어야한다. 문제 해결 방법 sort 내장함수 사용 >> n; for (int i = 0; i > input; vec.push_back(input); } sort(vec.begin(), vec.end()); for (int a : vec) { cout
https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 문제 간단 정리 문제 해결 방법 https://dfdfg42.tistory.com/entry/%EB%B0%B1%EC%A4%80-14246%EB%B2%88-K%EB%B3%B4%EB%8B%A4-%ED%81%B0-%EA%B5%AC%EA%B0%84-C 참고 전체 코드 #include #include using namespace std; typedef long lo..
https://www.acmicpc.net/problem/14246 14246번: K보다 큰 구간 $n$개의 자연수로 이루어진 수열이 주어질 때, 특정 구간 $[i,j]$ ($i≤j)$의 합이 $k$보다 큰 모든 쌍 $(i, j)$의 개수를 출력하시오. www.acmicpc.net 문제 간단 정리 구간합으로도 될 것 같다. 하지만 투 포인터로 풀어보자 만약 12345 이고 K가 5일때 현재 123을 합한상태라면 4 5 는 더할 필요 없이 +3만 해주면 된다. 이를 유의해서 풀 문제 해결 방법 투 포인터를 이용해서 풀어보자.. 인덱스를 조심해야된다 전체 코드 #include #include using namespace std; typedef long long ll; int main() { ll N, M; ..
문제 간단 정리 '' 생략 문제 해결 방법 이 문제는 섬과 섬 사이의 연결 관계를 파악해야 하는 그래프 관련 문제입니다. 이를 효율적으로 파악하기 위해 Union-Find 알고리즘을 사용합니다. Union-Find는 그래프의 연결 요소를 식별하고 관리하기 위한 알고리즘입니다. Union-Find 알고리즘에서 'union' 연산은 두 집합을 하나로 합치고, 'find' 연산은 특정 원소가 어떤 집합에 속하는지를 찾는 데 사용됩니다. 본 문제에서는 다리 하나가 무너져 서로 왕복할 수 없는 섬들이 생겼습니다. 이때 두 섬을 다시 다리로 이어서 모든 섬이 왕복 가능하도록 해야 합니다. 이를 위해 먼저 주어진 섬 간 연결 정보를 이용해 각 섬의 부모 노드 정보를 업데이트합니다. 이렇게 하면 어떤 섬이 어떤 섬과 ..
문제 간단 정리 구현문제이다 각 블럭들을 돌아가면서 조사하면 되는 간단한 구현문제지만 어떻게 구현하냐에 따라서 시간이 달라질것이다. 나는 그냥 모든 블럭들을 조회하는 무식한 방법으로 풀었다. 이렇게 풀면 오류도 많고 틀릴 가능성이 높으니 아마 각 블럭 모양을 만들고 회전시키는 방법이 가장 바람직하지 않을까 싶다 https://stack07142.tistory.com/299 예시 문제 해결 방법 #include #include #include using namespace std; int main() { int arr[100][100]; int count = 1; while (1) { int N; cin >> N; if (!N) break; //i 세로 j 가로 int temp = 0; int max = -..
https://www.acmicpc.net/problem/11687 11687번: 팩토리얼 0의 개수첫째 줄에 M (1 ≤ M ≤ 100,000,000)이 주어진다.www.acmicpc.net #문제 간단 정리이하생략 #문제 해결 방법끝의 0의 개수는 2*5의 개수로 정해지고,2는 2의배수만큼 5는 5의 배수만큼 존재하기 때문에 2가 항상 5보다 많다때문에 5의 개수만 세주면 0의 개수와 같다 이분탐색의 범위는 m*5! 이 무조건 m개의 5의개수보다 많은 5를 가지므로right를 m*5로 설정해주면 된다. 또한 포함된 5의 개수는 5부터 5의제곱수들을 차례대로 나눈 몫을 구하면 5의 개수를 구하는함수를 만들 수 있다. #전체 코드#include #include #include #include #inclu..
