[백준] 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.

[백준] 1003번 피보나치 함수 C++ 문제풀이

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 문제 풀이 처음에는 재귀 함수 안에 count를 했는데, 시간초과가 나왔다. 따라서 pair fibo 배열을 만들어서 first에는 0이 나오는 횟수, second에는 1이 나오는 횟수를 저장하고 2부터 40까지 증가하는 순서로 배열을 채웠다. 소스 코드 #include using namespace std; pair fibo[41]; int main() { int T; cin >> T; //fibo 배열 만들기 fibo[0].first = 1; fibo[0].second = 0; fibo[1]..

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

[백준] 2606번 바이러스 C++ 문제풀이

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 문제 풀이 dfs를 이용해 방문한 지점들에 대해서 check 배열을 true로 바꿔주었다. check 배열의 true값의 갯수를 이용해서 count를 구했다. 소스 코드 #include #include using namespace std; bool check[101] = { false }; vector graph[101]; void dfs(int idx) { if (check[idx] == false)..

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