[백준] 1012번 유기농 배추 C++ 문제풀이

https://docs.google.com/forms/d/e/1FAIpQLSdZT0EGrU9YrYOU0lqHelC4cDRry-35RLb3QwLoCpxKCH7yKQ/viewform Google Forms: 로그인 이메일 또는 휴대전화 accounts.google.com 문제 풀이 DFS를 이용해 문제를 해결했다. visited 배열을 만들어서 방문 여부와 land값이, 1인 경우 count를 진행했다. 소스 코드\ #include using namespace std; int M, N, K; int dx[4] = { 0,0,-1,1 }; int dy[4] = { 1,-1,0,0 }; bool check[51][51]; int land[51][51]; int cnt; void dfs(int x, int y) ..

• format_list_bulleted 알고리즘
• · 2023. 9. 8.

[백준] 1926번 그림 C++ 문제풀이

https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 문제 풀이 DFS를 이용해 문제를 해결했다. visited 배열을 만들어서 방문 여부를 체크하고, 1인 경우 dfs를 계속 진행했다 소스 코드 #include using namespace std; int n, m; int cnt; int dx[4] = { 1, -1, 0, 0 }; int dy[4] = { 0, 0, 1, -1 }; int map[501][501] = { 0 }; bool visited..

• format_list_bulleted 알고리즘
• · 2023. 9. 7.

[백준] 7562번 나이트의 이동 C++ 문제풀이

https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 문제 풀이 맨 처음에 DFS를 이용해 풀었는데 Stack Overflow가 나왔다. 아무래도 깊이 우선 탐색은 무한정으로 깊어지는 경우에는 사용하기가 어려운 것 같다. 따라서 Queue와 BFS를 이용해서 문제를 해결했다. 소스 코드 #include #include using namespace std; int N, x, y, futu_x, futu_y; int dx[8] = { -1, -2, -2,..

• format_list_bulleted 알고리즘
• · 2023. 9. 6.

[백준] 2630번 색종이 만들기 C++ 문제풀이

https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 문제 풀이 분할 정복 문제였다. N / 2로 나눠가면서 종이가 완성이 되는지를 확인했다. 맨 처음 제출하니 70%쯤에서 틀렸다고 나와서 생각을 해보니, 처음부터 완성된 종이를 준 경우를 처리하지 않았다. 따라서 처음 탐색 과정을 추가해 처음부터 종이가 완성된 경우는 0 1을 출력하고 아닌 경우는 분할 정복을 이용해 문제를 해결했다. 소스 코드 #include using ..

• format_list_bulleted 알고리즘
• · 2023. 9. 4.

[백준] 11659번 구간 합 구하기 4 C++ 문제풀이

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 문제 풀이 누적합 배열을 생성해서 구간 합 문제를 해결했다. 처음 제출했을 때 시간복잡도가 O(N)이였는데도 시간초과가 나와서 당황했다. ios::sync_with_stdio(false); cin.tie(nullptr); 코드를 작성해서 main안에 넣어주니 시간 초과 문제가 해결되었다. 위의 코드들에 대해서는 다음번에 자세히 설명해 볼 예정이다. 소스 코드 #include..

• format_list_bulleted 알고리즘
• · 2023. 9. 3.

[백준] 1764번 듣보잡 C++ 문제풀이

https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 문제 풀이 문자열 정리와 이분 검색을 통해서 문제를 해결했다. 소스 코드 #include #include #include #include using namespace std; int main() { int a, b; cin >> a >> b; int cnt = 0; int i, j, k; vectorA; vectorB; for (i = 0; i >..

• format_list_bulleted 카테고리 없음
• · 2023. 9. 2.