푸으름

✏️ 문제 링크https://www.acmicpc.net/problem/16929  ✏️ 문제 설명  ✏️ 문제 풀이주어진 배열 안에서 사이클의 유무를 찾는 문제이며, dfs로 접근할 수 있습니다. bfs로도 똑같은 방식으로 문제를 풀어봤는데 자꾸 예제 2번에서 틀리다고 나와서 포기했습니다... 가로와 세로의 길이가 50보다 작거나 같기 때문에 모든 점에 대해서 dfs로 탐색을 해도 시간초과가 발생하지 않습니다. dfs함수에서 조건을 조금만 생각하면 쉽게 풀 수 있습니다다음으로 가고자 하는 mx와 my의 값이 배열의 범위를 벗어나지는 않는가?다음으로 가고자 하는 map[mx][my]가 이전에 방문했던 알파벳 값과 동일한가?다음으로 가고자 하는 visit[mx][my]가 이전에 이미 방문한 적이 없는가? ..

✏️ 문제 링크https://www.acmicpc.net/problem/2589  ✏️ 문제 설명  ✏️ 문제 풀이그냥 단순히 모든 육지인 지점은 찾아서 그 지점에서 가장 먼 거리를 BFS를 탐색해서 구해준 후거리들의 최댓값을 구해주면 됩니다처음에는 트리의 지름을 구하는 방식으로 접근을 해봤는데 계속 2%에서 틀려서...포기  ✏️ 문제 코드#include #include #include using namespace std;struct Node{ int y, x, depth;};const int dy[4] = { -1,1,0,0 };const int dx[4] = { 0,0,-1,1 };int N, M, ret;char adj[50][50];bool visited[50][50];vector> v;void..

✏️ 문제 링크https://www.acmicpc.net/problem/31778  ✏️ 문제 설명  ✏️ 문제 풀이얼마 전 포스텍 open contest에 나왔던 문제입니다.군대에서 짜투리 시간 내서 참가해서 도전했었던 문제인데 계속 풀지를 못했던 문제입니다..분명 딱 봤을 때 투포인터랑 dp를 이용해야 한다는 거는 알았는데 11번 제출해서 모두 틀렸습니다 하하하 거두절미하고 문제 본론으로 넘어가보겠습니다.문자열을 교환하고 PPC 문자열을 만들 수 있는 개수를 출력해야 하는데, 교환은 최대 k번할 수 있습니다.이 말은 꼭 k번을 교환할 필요는 없다는 말입니다. 문자열 교환의 핵심은 P가 최대한 앞으로 C가 최대한 뒤로 가야 합니다.여기서 투 포인터 방식을 이용해서 교환을 해야 합니다. 자세한 내용은 코..

✏️ 문제 링크https://www.acmicpc.net/problem/24416  ✏️ 문제 설명  ✏️ 문제 풀이피보나치 함수를 재귀함수와 동적프로그래밍으로 계산했을 때 각 함수를 얼마나 호출하는지에 관한 문제입니다.전역변수로 cnt1을 선언하고 재귀함수 부분에서 return (fib(n - 1) + fib(n - 2));을 호출하기 직전에 cnt1에 1을 더해주시면 됩니다. 차피 n==1일때나 2일때까지 가고나면 알아서 계산을 다 해주기 때문에 이렇게 재귀 호출 횟수를 구할 수 있습니다 동적 프로그래밍으로 하는 계산횟수는 for문을 돌리기보다 쉽게 생각해보면 n-2번 호출하게 됩니다.fib(n)값을 구하기 전에 미리 fib(1)과 fib(2)값을 지정해놓기 때문에 위의 사진처럼 for문을 돌린다면 ..