반응형
(백준/c++) 1238 - 파티 / 최단경로그래프, 플로이드 워샬
📃 coding test/◽ 백준2024. 8. 22. 17:12(백준/c++) 1238 - 파티 / 최단경로그래프, 플로이드 워샬

"(백준/c++) 1238 - 파티 / 최단경로그래프, 플로이드 워샬"https://www.acmicpc.net/problem/1238 🏆 solved.ac 난이도: 골드3 🔸 문제 핵심 단방향 도로갔다가 돌아오는 최단경로  🔹 주요 코드 부분파란줄: form ~ stopper 시작점부터 경유지까지 무한이면, 연결되어 있지 않는다는 뜻이기 때문에 무시해주자.노란줄: 시작점부터 도착점 > 시작점부터 경유지 + 경유지부터 도착점이 구조를 외우지 말고 완화(relax)를 이해하자. #include#include#includeusing namespace std;//vector> students[1'001]; int students[1'001][1'001];int result[1'001];int main(v..

[ Algorithm / 벨만 포드 알고리즘 ] + 백준 1865 웜홀 문제풀이
👨🏻‍💻 programming/◽ 알고리즘2024. 8. 22. 15:26[ Algorithm / 벨만 포드 알고리즘 ] + 백준 1865 웜홀 문제풀이

"벨만 포드(bellman-ford) 알고리즘 " 알고리즘 이름이 맘에 안든다. =3= 알고리즘이나 수학적 법칙을 보면 발견한 사람들의 이름으로 이름을 만든다. 직관적이지 않아서 계속 까먹게 된다. 직관적으로 이름을 지어줬으면 좋겠다. 예를 들어, "음수사이클 다익스트라" 이런식으로 ~  1. 최단 경로 트리 (shortest-path tree), 최적해 구조(optimal substructure 알고리즘이다. 답은 여러개가 존재 할 수 있으면 가중치가 있는 그래프로 최단 경로를 찾는다.  2. 음수 사이클의 유무를 확인할 수 있다. 다익스트라랑 다른 점!!으로 음수 사이클의 발생으로 최단 경로가 무한으로 빠지는 음수차이클을 찾는다.  3. 모든 음수 간선이 문제다 ? 아니다. (-) 마이너스 값이 있는..

(백준/c++) 10026 - 적록색약 / BFS, 그래프
📃 coding test/◽ 백준2024. 8. 20. 16:12(백준/c++) 10026 - 적록색약 / BFS, 그래프

"(백준/c++) 10026 - 적록색약 / BFS, 그래프"🏆 solved.ac 난이도: 골드5  #include#includeusing namespace std;char grid[101][101];bool visited[101][101] = {false,};bool visitesd[101][101] = { false, };int direction[4][2] = { {-1, 0} , {0, 1}, {1, 0}, {0 ,-1} };int mTC;int normalCount = 0;int blindnessCount = 0;queue> normalPerson; queue colorblindness;void normalFunc(int i, int j);void bilndnessFunc(int i, int j..

(백준/c++) 11724 - 연결 요소의 개수 / BFS, 그래프
📃 coding test/◽ 백준2024. 8. 16. 16:17(백준/c++) 11724 - 연결 요소의 개수 / BFS, 그래프

"(백준/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, 그래프
📃 coding test/◽ 백준2024. 8. 16. 12:39(백준/c++) 14940 - 쉬운 최단 거리 / DFS, 그래프

" (백준/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에 넣..

(백준/ C++) 12101- 1, 2, 3 더하기2 / 다이나믹 프로그래밍, 재귀
📃 coding test/◽ 백준2024. 7. 19. 18:27(백준/ C++) 12101- 1, 2, 3 더하기2 / 다이나믹 프로그래밍, 재귀

"(백준/ 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 - 다리 놓기 / 다이나믹 프로그래밍, 재귀
📃 coding test/◽ 백준2024. 7. 19. 16:23(백준/ C++) 1010 - 다리 놓기 / 다이나믹 프로그래밍, 재귀

"(백준/ 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 더하기 / 다이나믹 프로그래밍, 재귀
📃 coding test/◽ 백준2024. 7. 19. 11:37(백준/ C++) 9095 - 1, 2, 3 더하기 / 다이나믹 프로그래밍, 재귀

" ( 백준/ 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 - 내리막길 / 다이나믹 프로그래밍
📃 coding test/◽ 백준2024. 7. 18. 17:23(백준/ C++) 1520 - 내리막길 / 다이나믹 프로그래밍

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

(백준/ C++) 11049 - 행렬 곱셈 순서 / 다이나믹 프로그래밍
📃 coding test/◽ 백준2024. 7. 18. 12:48(백준/ C++) 11049 - 행렬 곱셈 순서 / 다이나믹 프로그래밍

"(백준/ 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..

반응형
image