노는 게 제일 좋아

이것도 재밌고 문제로 나오지 않을까? 싶다. https://www.acmicpc.net/problem/2146 #맞은 풀이 #include using namespace std; #define X first #define Y second int dx[4] = {1,-1,0,0}; int dy[4] = {0,0,1,-1}; int N; int conti[100][100]; int area[100][100]; int dist[100][100]; int flag = 1; int minDist = INT_MAX; void DFS(int x, int y){ area[x][y] = flag; for(int dir = 0; dir= N || ny = N)continue; if(area[nx][ny]..

나의 좁은 식견에 안타까워하며 배운 상태 저장방법!! 행렬을 문자열로 문자열을 행렬로 변환하는 방법!! 행렬 자체를 저장하는 것이 메모리가 많이드므로 문자열로 저장하는 방법!!! 배울 것이 많은 문제다. https://www.acmicpc.net/problem/1525 #맞은 풀이 #include using namespace std; int dc[4] = {1,-1,0,0}; int dr[4] = {0,0,1,-1}; string start = ""; //상태를 문자열로 저장함 int answer = -1; //answer가 갱신되지 않는 것은 아무리 시도해도 만들 수 없는 것을 의미 int main(){ queue q; //string(상태), int(실행횟수) set check; //상태가 중복되는 ..

이런 문제를 싫어하지만.. 자주 나오는듯 하다. 내용이 많아서 어려운 문제다. 게다가 6초나 준다.. 시간이 얼마나 많이 걸릴 지 예상이 가는 문제다. https://www.acmicpc.net/problem/9019 #맞은 풀이 #include using namespace std; const int MAX = 10000; int A,B; bool visited[MAX]; int main(){ int T; cin >> T; //테케 while(T--){ cin >> A >> B; //초기화 for(int i = 0; i

음.. 처음 생각하기 정말 어려웠다. 어떻게 BFS로 푼다는 거지..? BFS는 모든 단계 탐색이 비용이 같아야하는데.. 쟤는 0초인데?? 우선순위 큐를 쓰라는 말을 들어도 못알아듣다가 다른 분의 코드를 조금 보고나서야 알았다. https://www.acmicpc.net/problem/13549 #맞은 풀이 #include using namespace std; int N, K; bool visited[100002]; int main(){ cin >> N >> K; //왜 우선순위 큐를 사용해야하느냐?? //+1,-1의 노드를 탐색하는 것과 *2 노드를 탐색하는 것은 다르다. //즉, *2를 하는 것은 할 수 있는 만큼 하고 +1과 -1을 해야한다. //즉, 단계도 단계지만 시간으로 구분되어야 한다. //..

사실 처음 들었을 때 이분그래프의 정의가 알아듣기 힘들었다. 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. ??음.. 무슨 말이지?? 즉, 나는 내 집합의 정점과 연결되면 안된다...? 그렇다. 그냥 색을 2가지로 칠할 수 있을 때 인접한 노드가 나와 같은 색을 가지면 안된다는 말과 같다. https://www.acmicpc.net/problem/1707 #맞은 풀이 #include #include #define X first #define Y second #define MAX 20001 using namespace std; int K; // 테스트케이스 수 in..

[CS Interview] - 비선형 자료구조를 사용하는 이유 우리는 선형구조만으로 모든 것을 표현하지 못한다. 그래서 Tree를 그려내었고 Tree는 하나의 노드에서 다른 노드로 이동하는 경로가 하나만 존재하기 때문에 순환 또는 원형의 종속성을 표현할 수 없다. 때문에 우리는 또 다른 자료구조인 Graph를 구현하고자 한다. 즉, 노드 간의 더 자세한 경로의 표현을 하고싶다면 Tree 보다는 Graph가 더 적합한 자료구조라고 할 수 있다. Graph는 우선 노드에 대한 데이터를 가지고 있을 뿐만 아니라 노드 간의 간선 데이터도 가지고 있어야 한다. 즉, 해당 노드의 값과 해당 노드와 연결된 노드에 대한 정보를 가지고 있어야 한다는 것이다. edge, 간선은 무방향, 일방향 이 존재하고 해당 edge에..

우리가 흔히 보는 위와 같은 그림이 트리구조이다. 왜 Tree냐면 나무를 거꾸로 박아놓은 것처럼 생겼기 때문이다. 그래서 시작이 Root Node라고 부른다. 실제로 물론 한 노드에 여러가지 노드를 가질 수 있지만 우리는 이진 트리, Binary Tree라고 가정하고 진행한다. 각 노드는 자신의 밑에 있는 2개의 노드를 가리킨다. struct Node{ std::string data; node* first; node* second; }; 각 노드들은 자신의 하위 노드를 가리킨다. 즉, 이를 통해서 계층적 구조를 나타낼 수 있다. 트리구조를 처음 만들기 위해서는 Root Node가 필요하다. 해당 노드는 처음에 first와 second가 NULL이다. 내가 예전에 썼던 글이다. 내가 다시 쓰기보다 아래 글..

저번 글을 너무 힘들게 써가지고,, 이건 좀 간단하게 해야 것습니다. 앞에 배운 Dijkstra와의 차이점은 얘는 실행하면 모든 정점사이의 최단경로를 한꺼번에 찾아준다는 것인디 어떻게 구성하느냐? 2차원 배열 A를 이용하여 3중 반복을 하는 루프로 구성 하는데 이게 무슨말이냐 하면은 그냥 반복한다는 것이다.ㅋㅋ •배열 A의 초기 값은 인접 행렬 weight •인접 행렬 weight 구성 1. i==j이면, weight[i][j]=0 2. 두 정점 i, j 사이에 간선이 존재하지 않으면, weight[i][j]=∞ 3. i, j 사이에 간선이 존재하면, weight[i][j]는 간선 (i, j)의 가중치 말보다 더 간단히 하자면 이런식이라는 것인데 조금 어려울 수 있으니 풀어서 설명해보자면 Ak [i][j..

이제 우리가 가장 친숙한 가중치 그래프의 응용이 나올건데 바로바로 최단경로( shortest path) 를 배울겁니다. 보통 최단 거리, 최소 시간, 최소 비용 등등 뭐 가중치마다 다르게 설정되니까 각각 알아내면 되겠지? 아무튼 얘가 우리가 실생활에서 접하는 진짜 필요한거지 ㅋㅋㅋ 이런식으로 설정되어 있다면,,? - 경로1: (A,B,C,D): 비용 = 7 + 4 + 2 = 13 - 경로2: (A,E,B,C,D): 비용 = 3 + 2 + 4 + 2 = 11 - 경로3: (A,F,B,D): 비용 = 10 + 6 + 10 = 26 경로1이 최소비용을 가진 경로고 사용자에게 추천을 하겠지?? 이제 들어가기 전에! 여기에도 MST와 비슷하게 2가지 알고리즘이 있어,,, 우선 이름을 알아보자면 Dijkstra 와..

그래프의 탐색은 가장 기본이라고 할 수 있을거야. 그럼에도 조금 나중에 배우는 이유는 제일 중요해서 그래 기본이 가장 중요한거지 그래프에서 탐색은 특정한 것을 찾는다기보다는 "시작 정점부터 차례대로 모든 정점들을 한 번씩 방문" 을 의미해 또한 연결되었는지 안되어있는지가 중요한 회로같은 경우 탐색만으로도 문제를 발견할 수 있는거지 •도로망 예: 특정 도시에서 다른 도시로 갈 수 있는지 여부 •전자회로 예: 특정 단자와 다른 단자의 연결 여부 우선 탐색에는 2가지 정도가 있어. 1. 깊이우선탐색(Depth First Search) DFS 2. 너비우선탐색(Breadth First Search) BFS 이렇게 2가지가 있는데 비교는 이제부터 할거야 1. 깊이우선탐색 깊이부터 가자 갈수 있을 때까지 계속 가다..