Doby's Lab

https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net Solved By: DFS 해당 문제에 따라 DFS를 짜는 것에 있어서 어려웠던 부분이 있었습니다. DFS를 짤 때, 총 Recursive가 n + 1번이 되고, DFS의 now가 첫 시작 노드라면 마지막에 첫 시작 node로 돌아올 때는 DFS를 어떻게 다시 Recursive Call을 할지 문제였습니다. 구글링을 해보면 사실 마지막 Node를 향해 ..

https://www.acmicpc.net/problem/5651 5651번: 완전 중요한 간선 입력은 여러개의 테스트케이스로 이뤄진다. 첫째 줄에는 테스트케이스의 수 K (1> v >> u >> w; // 데이터 저격 조건문 if(v == 3 && u == 4){ w = 3; } edges.push_back({v, u}); adj[v].push_back(u); adj[u].push_back(v); c[v][u] = w; } cout u >> w; getEdges.push_back({v, u}); adj[v].push_back(u); adj[u].push_back(v); c[v][u] += w; } edmondsKarp(1, n); int ans = bfs(getEdges); cout

https://www.acmicpc.net/problem/10292 10292번: Man in the Middle Nowadays, social networks are one of most active research topic. A social network represents friendships between people. We say that two people are direct friends if they accept each other as friends. But friendship is an amazing thing. It is possible that www.acmicpc.net Solved By: Articulation 주어진 Directed Graph 가운데 Articulation이 ..

https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net Solved By: Disjoint Set, Map string으로 받아들인 값을 노드화 시키는 것에 대해서는 map을 사용해야겠다 생각했습니다. 하지만, 이들의 번호를 어떻게 매길지 감이 오지 않아 솔루션을 찾아보았습니다. (https://chanhuiseok.github.io/posts/baek-21/) 입력으로 받아들이면서 해당 string이 map내에 존재하지 않는다면 번호를 매..

https://www.acmicpc.net/problem/11266 11266번: 단절점 첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B www.acmicpc.net Solved By: Articulation Articulation 구현에 대해 아쉬운 점이 한 가지 있었습니다. 바로 minOrder 부분이 이해가 되지 않는 것이었는데 minOrder를 주석에 달아두었듯이 'Now Node의 *Child Node로써 갈 수 있는 Node* 중 가장 일찍 방문한 Node'라고 생각하면 쉽습니다. (이 말도 100% 이해를 하기에는 애매..

바로 직전의 포스팅에서 Python을 이용하여 DFS를 구현해보았는데 C++에서는 당연히 사용하던 테크닉들을 정리하여 보았습니다. [Adjust List 구현] adj = [[] for i in range(0, n)] [Global Variable] DFS 코드의 일부분입니다. 문제를 풀면서 당황했던 부분이 이 부분이었습니다. '왜 result에 cnt값이 할당이 안 되지?' 이유를 찾아보았더니 Python에서는 함수 외부에 선언된 전역 변수를 사용하려면 함수 안에서 같은 변수 명의 Global 변수 선언을 해주어야 했습니다. ... result = -1 def dfs(node, cnt): if node == k: global result #global 변수를 사용하여 전역변수를 사용하겠다는 뜻 resu..

https://www.acmicpc.net/problem/17204 17204번: 죽음의 게임 중앙대학교 소프트웨어대학 새내기들을 맞이하게 된 17학번 김영기는 두 학번이라는 차이를 극복하기 위해 새내기들과 친해지려고 노력하고 있다. 그 노력 중 하나는 바로 새내기들과의 술자 www.acmicpc.net Solved By: DFS Python을 이용하여 Adjust List, Recursive Call Function, Global Variable을 사용하여 DFS를 구현해보았습니다. n, k = map(int, input().split()) adj = [[] for i in range(0, n)] visited = [False for i in range(0, n)] result = -1 def dfs(..

예전부터 인공지능을 공부하고 싶은 마음을 가지면서 최근 들어 파이썬을 배우고, 여러 시도를 해보고 있습니다. 파이썬은 백준의 브론즈, 실버 급 문제들을 풀 수 있는 수준으로 다루고 있습니다. (조금 문법적으로나 더 자연스러운 코딩을 위해서 더 공부해야 한다고 생각하고 있습니다.) 그리고, 구글에서 제공하는 Colab을 통해 이것저것 만져보고는 있습니다만 아직 서투릅니다. (당장의 IDE에서도 서투른 거 같네요) 하지만, 제일 문제라고 느끼는 부분은 '공부하고 있는 것에 대한 의미'입니다. 예를 들어 'numpy를 공부하고 있다고 치면 이게 어디에 쓰이는 거지?', '선형대수학의 Transposed Matrix는 인공지능에서 어떤 의미인지?'에 대해 헷갈려하는 시간들을 보내고 있습니다. 그리고, 항상 관련..