"(백준/c++) 11403 - 경로찾기 / BFS, 그래프"https://www.acmicpc.net/problem/11403  🏆 solved.ac 난이도: 실버1 오늘 쉬는 날이라 문제 푸는게 재미있다.Array 변수 이름은 Floyed이지만? 플로이드 와샬보다 BFS를 사용해서 푸는게 더 편할거 같아서 BFS로 풀었다. 다른 BFS와 다른 점은 모든 점에서 방문을 초기화 시켜줘야한다. ex ) 1 -> 5 -> 6 -> 7  이런 연결이 있을 때, 1을 5, 6, 7을 모두 방문 할 수 있다는 표시를 해줘야하고 그 다음 5번, 6번, 7번점도 이전에 방문 했더라도 연결되었는지 확인하기 위해 점 시작점에서 방문을 초기화 해야한다. #include#include#include#includeusing..

"(백준/c++) 11724 - 연결 요소의 개수 / BFS, 그래프"https://www.acmicpc.net/problem/11724🏆 solved.ac 난이도: 실버2 난이도는 쉬웠다. DFS, BFS 아무거나 골라서 풀수 있는 문제이다. 하지만~ 나는 5번 정도 틀렸다. 이유는 방향성이 없는 그래프인데 방향성이 있게 한 쪽만 입력해주고 있었다. ㅠㅠ 방향성이 없는 그래프라면 꼭 정점 양쪽을 비교할 수 있도록 해주자.  // 연결 요소의 개수 #include#include#includeusing namespace std; bool visit[1001] = { false, }; vector distributingLine[1001]; queue que;int main(void){ int N, M; ..

" (백준/c++) 14940 - 쉬운 최단 거리 / DFS, 그래프 "https://www.acmicpc.net/problem/14940 🏆 solved.ac 난이도: 실버1이 문제는 쉽게 풀어서 solved.ac에 검색해봤는데 실버 1 문제당.. 힝 !!! 내 실력은 아직 골드5, 실버1 정도 되는거 같다 ㅠㅁㅠ 넓이 우선 문제로 시작점부터 찬찬히 넓혀가면 되는 문제다. 항상 BFS문제에서 실수하는 부분을 다시 짚고 넘어가려고 작성한다.  que에 조건이 되는 노드를 push 할 때 방문처리를 해주는거다. pop 하면서 방문처리하니깐 괜찮지 않나? 생각하면서 항상 빼곤 한다.그렇게 되면 아래와 같이 E가 que에서 pop되고 방문처리하기 전에 D에서 'visit false군!!" 하면서 que에 넣..

" Algorithm/ KMP 알고리즘 " 🔸 KMP( Knuth, Morris, Prett ) Algorithm? 대표적인 상수시간 내에 할 수 있는 문자열 검색 알고리즘이다. 명칭은 알고리즘 쓰임새와 상관없이 만든 사람이름이다. 문자열 매칭 알고리즘이라고 부르는게(?) 더 좋을거 같다.  🔸 해답https://www.acmicpc.net/problem/1786"baekjoon 1786번 - 찾기"와 함께 kmp 알고리즘을 배우고 풀어보자. P: 패턴(길이: m) T: 텍스트(길이: n) 만약 모든 매칭을 하나하나 확인한다면? (n - m + 1) x m  = 시간 복잡도 O(nm)목표: 시간 목잡도 O(n) 만들기.  🔥 step 1.  찾으려는 문자열 전처리 과정 거치기 접두사(이을 접 : 接..

"(백준/ C++) 12101- 1, 2, 3 더하기2 / 다이나믹 프로그래밍, 재귀"https://www.acmicpc.net/problem/12101  https://cclient.tistory.com/128 (백준/ C++) 9095 - 1, 2, 3 더하기 / 다이나믹 프로그래밍, 재귀" ( 백준/ C++ ) 9095 - 1, 2, 3 더하기 "https://www.acmicpc.net/problem/9095 문제 보자 마자.. 음 ? 재귀 ? 했고, n은 11보다 작은 양수였다. dp로 안 풀어도 되는 문제 아닌가 생각했다. 아래와 같이 어떠한 방법cclient.tistory.com이 문제 연장선이다. 별로 어렵지 않았지만 꾸역꾸역 넣은 느낌이든다. DFS 이기 때문에 중위순회로 되어있다. 위 ..

"(백준/ C++) 1010 - 다리 놓기 / 다이나믹 프로그래밍, 재귀"https://www.acmicpc.net/problem/1010 N을 늘려보면서 비교를 해보니 규칙을 쉽게 발견 할 수 있었다. N(강 서쪽)의 맨 위 다리가 M(강 동쪽)에 위치할 수 있는 조건은 N은 빠짐 없이 모두 연결은 되야 하므로 M - N + 1이 된다. DP [ N ][ M ] 이라고 만들 때, 아래 그림과 같이 규직을 찾을 수 있는데 N이 1일때는 M의 개수 만큼 경우의 수가 생긴다. 이 조건은 함수의 return(반환) 조건으로 사용하면 된다.또 N과 M이 같을 때는 모든 다리를 연결 하므로 언제나 하나의 경우의 수이다. 이거 또한 함수의 return(반환)조건으로 사용한다. N(강 서쪽)의 맨 위 다리를 M(강 ..

" ( 백준/ C++ ) 9095 - 1, 2, 3 더하기 "https://www.acmicpc.net/problem/9095 문제 보자 마자.. 음 ? 재귀 ? 했고, n은 11보다 작은 양수였다. dp로 안 풀어도 되는 문제 아닌가 생각했다. 아래와 같이 어떠한 방법이든 합이 N이 되면 되기 때문에 N이 되면 결과값을 ++ 해주게 코딩 했다. 개행을 안 붙여서 틀렸었는데 4%에서 틀렸다고 하면 개행 안 붙여서 이다. // 9095 - 1,2,3 더하기#includeusing namespace std;int aResult = 0;void Func(int pNum, int pTarget){ if (pNum > pTarget) return; if (pNum == pTarget) { aResult++; ..

"(백준/ C++) 1520 - 내리막길 / 다이나믹 프로그래밍" 이건 DP 중 어려운 문제에 속하는게 아닌거 같은데 잘못 생각해서 계속 틀렸다.. 처음 생각했을 때 높은 곳에서 낮은 곳으로 이동한다고 해서 위로 ↑ 갈 수 없다고 생각했는데 높은 곳과 낮은 곳의 기준은 배열 안의 숫자지 배열의 위치를 따지는 것이 아니다. 그럼 즉  → 우  ↑ 위   ← 좌  ↓ 아래 모두 가능하다.  다른 사람들의 풀이를 보면 0, 0 부터 M-1, N-1까지 오는 경로에만 1을 리턴 해준다. 나는 거꾸로 생각했고, 목적지 부터 스타트 까지 갈 수 있는 방법으로 구현했다. 사실 상 같다.  그리고 나처럼(?) 바보같이 모든 if문을 나누지 말고.. for문을 이용하자. 다른 사람들의 문제 풀이를 보면 좌,우,상,하 모..

"(백준/ C++) 11049 - 행렬 곱셈 순서 / 다이나믹 프로그래밍" 해도해도 어려운 DP .. 혼자 못 풀었다. 유투브 설명 보고 풀었다 .. ㅠㅠ 핵심은 AEH 사이의 (ABCDE) (FGH)가 어떠한 방법으로 연산을 했든지 간에 (ABCDE) 의 최종행렬의 크기는 { a , f } (FGH)의 최종행렬 크기는 { f , i }가 된다. 라는 사실이다.  점화식:  a x f x i + Func(x , k) + Func (k+1, y)    //== [ 행렬 곱셈 순서 ] ==#include #include #include using namespace std;int col[500], row[500];int dp[500][500];int func(int idx_x, int idx_y){ if (d..

" (백준/ C++) 7579 - 앱 "  https://www.acmicpc.net/problem/7579 7579 - 앱입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활성화 되어 있는 앱 A1, ..., AN이 사용 중인 메모리의 바이트 수인 m1, ..., mN을 의미하며, 셋째 줄의 정수는 각 앱을 비활성화 했을 경우의 비용 c1, ..., cN을 의미한다.www.acmicpc.net 다이나믹 프로그래밍으로 풀어야 하는 문제. 처음에는 무게로 DP를 만들면 되겠다 ~ 했지만 ?? 무게(M)이 최대 10,000,000 이였다. DP[ n ][ m ] 이건 ..