PS32 [C++] 백준 1261 - 알고스팟 (메모리 초과 이슈) 백준 1261 - 알고스팟 난이도 : 골드 4 시간 : 30분 소요 문제 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 풀이 방법 해당 문제는 bfs를 사용하면 쉽게 풀릴 줄 알았다. 그래서 깊게 고민해보지 않고, 바로 코드를 적었지만 메모리 초과가 발생했다. 초기 코드 #include #include #include using namespace::std; int N, M; int map[101][101]; int v[1.. 2023. 3. 15. [C++] 백준 2407 - 조합 백준 2407 : 조합 난이도 : 실버 3 시간 : 30분 소요 문제 https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 풀이 방법 이 문제에서는 2가지만 고려하면 된다. 1. 이항 계수의 성질 2. long long을 넘는 큰 숫자 다루기 3. 메모이제이션 이항 계수의 성질 이항계수의 성질 중 파스칼의 삼각형이 있다. 삼각형의 각 항은 위의 두 항을 더한 값이다. 예를 들어, 다음과 같은 파스칼의 삼각형이 있다. 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 여기서 4C2 는 6이 된다. 이 파스칼 삼각형을 일반화하여 점화식을 유도하면 아래와 같다. n .. 2023. 3. 14. [C++] 백준 11444 - 피보나치 수 6 백준 11444 : 피보나치 수 6 난이도 : 골드 2 시간 : 알고리즘 수업자료 참고 문제 https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 과정 이 문제를 본 순간 어제 알고리즘 수업에서 배운 피보나치 행렬 풀이법이 기억났다. 따라서 나의 직관으로 풀진 못했고, 배운 내용 + 다른 사람의 코드를 참고하면서 풀었다. 먼저 피보나치 수열의 점화식 F(n+2) = F(n+1) + F(n)을 통해 위 그림과 같은 행렬을 유도할 수 있다. 해당 식을 생각하면 그 이후에는 어렵지 않게 유도할 수 있다. 하지만 어떻게 해당 식.. 2023. 3. 13. [C++] 백준 1034 - 거짓말 (유니온 파인드는 모르겠고) 백준 1034 : 거짓말 난이도 : 골드 4 시간 : 40분 소요 문제 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 풀이 과정 해당 문제를 풀고, 여러 사람들의 풀이를 봤는데 다들 유니온 파인드 알고리즘을 사용해서 해결했었다. 이 기회를 통해 알게 되었지만 나는 해당 문제는 큐를 사용해서 풀었다. 비슷한? 동일한? 방법인지는 더 공부해봐야 겠다. 변수 정의 int S[MAX]; vector v[MAX]; queue q; 1. S[i] == 1 : i번.. 2023. 3. 3. 이전 1 2 3 4 ··· 8 다음
