공부하자

https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 정리 그래프 만들고 경로 찾으면 되는 문제 생각 dfs 써서 그래프 연결 유무 확인을 하자! 방문했으면 1, 안했으면 0 출력 코드 #include #include using namespace std; int N, M; int graph[100][100]; bool visited[100]; void dfs(int start){ for(int i=0 ; i> N; for(int i=0 ; i graph[i][j]; } }..

https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 첫째 줄에 노드의 개수 $N$과 거리를 알고 싶은 노드 쌍의 개수 $M$이 입력되고 다음 $N-1$개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 $M$개의 노드 쌍 www.acmicpc.net 문제 정리 주어진 정보로 트리를 만들고 노드 사이의 거리를 출력하는 문제 생각 트리 문제가 너무 오랜만인데... dfs나 bfs 쓰면 될 것 같다 1. 그래프를 만든다 2. dfs로 노드 사이의 최단거리를 구한다 3. 출력 2차원 배열에 두 노드와 노드 사이의 거리를 입력받고 노드를 연결하고 (양방향) 그 후 dfs를 실행하는데 배열이 0이 아니라면 탐색을 하고 0이면 df..

https://www.acmicpc.net/problem/20300 20300번: 서강근육맨 PT 첫째 날에 $1$과 $4$를 선택하고, 둘째 날에 $2$와 $3$을 선택하고, 마지막 날에 $5$를 선택하면 $M$은 $5$가 되며, 이때가 $M$이 최소일 때이다. www.acmicpc.net 문제 정리 근손실 미친놈 근손실 정도 = 입력받은 두 근손실 정도 벡터(또는 배열) 2개의 합 합의 max값이 가장 적게 되는 max(==M)을 구해라! 생각 모든 경우의 수를 전부 구해서 가장 작은 M값을 구하면 될 것 같은데... 중요한 건 두 개를 고르는 경우를 조합으로 구해야 중복도 안나고! 좋을 듯 전에 썼던 조합으로 푸는 dfs를 사용하면 될 것 같다! 근데 이렇게 어려운 문제가 아니었나보다... 그냥 정..

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 문제 정리 팀의 능력치 : 팀에 속한 모든 쌍의 능력치 Sij의 합 = Sij + Sji 두 팀의 능력치 차이의 최솟값을 구하기 생각 모든 경우의 수를 구해야 하긴 하는데… 1. 팀 구성 방식 - 중복이 허용되지 않으니까 순열로 구해야 하긴 함! 한 팀에 속하면 visited로 방문 표시를 하면서 방문한 팀이 n/2될 때 까지 방문하고! 이런 식 2. 팀의 능력치 비교 - 표에서 그대로 가져오는데 두 팀의 능력치 차를..

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제 정리 주어진 도시 정보에서 M개의 치킨집만 남기는데 치킨집과 집 사이의 총 거리가 가장 적게 되도록 M개를 골라서 도시의 치킨 거리의 최솟값을 구하면 됨! (각 집과 치킨집 사이의 거리의 총 합이 최소가 되는) 생각 브루트포스로 모든 M개를 골랐을 때마다 거리를 다 구해놓고 그 중 min을 구함! 근데 M개를 고르는 로직은 어떻게 하지? 모든 경우의 수를 구한다고 하면 ..

https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net + C++의 next_permutation 함수를 사용하면 더 쉽게 풀 수 있다! 하지만 난 안 썼음 생각 1. 계산하고 비교하면서 큰 것만 남긴다! 근데 진짜 어떻게 해야할지 모르겠어 배열의 크기 제한이 8까지니까!! 작으니까 뭔가 하면 될 것 같아 코드 초안 int N, ans; int arr[9]; int result(){ // 일케 계산하는 함수를 따로 만들고! int result = 0; for(int..

https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 정답 코드 #include using namespace std; int N, M; int arr[9]; bool visited[9]; void dfs(int k){ if (k == M){ for (int i = 0; i M; dfs(0); } visited 배열은 0부터 시작해도 상관 없는데 arr에 저장할 땐 +1을 해줘서 1부터 N까지 자연수 중에서 중복 없이..

https://www.acmicpc.net/problem/2178 #include #include #include using namespace std; int N,M; int arr[101][101]; //미로 int visit[101][101]; //방문 int dy[] = {-1,0,1,0}; // 좌표 이동 값 (상, 우, 하, 좌) int dx[] = {0,1,0,-1}; void BFS(int n, int m) { visit[n][m]=1; // 방문 표시 queue q; // 큐를 생성 q.push(make_pair(n,m)); // 시작 점 큐에 추가 while (!q.empty()) // 큐가 비어있을 때 까지 { int x = q.front().first; int y = q.front()..