꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/1058 전형적인 플로이드-와샬 알고리즘 문제였습니다. 우선, 자기 자신은 친구가 될 수 없기 때문에 i==j일 때는 0, 'Y'일 때는 1, 그리고 'N'일 때는 INF를 입력합니다.이후에는 플로이드 알고리즘을 수행한 뒤 모든 사람의 친구의 수를 세는데,1. 서로 친구이거나2. 한 다리 건너서 아는 친구까지 세기 때문에 friendsList[i][j] friendsList[i][k] + friendsList[k][j]) friendsList[i][j] = friendsList[i][k] + friendsList[k][j]; }} int main(void){ cin >> N; for (int i = 0; i < N; i++) { ..

문제 링크입니다: https://www.acmicpc.net/problem/2231 생성자를 1부터 시작해서 순차적으로 더해가면서 조건이 성립하는지 확인하는 Brute Force 문제였습니다.특별한 알고리즘을 요구하지 않았기 때문에 쉬운 문제였습니다. #include using namespace std; int N; int findCreator(void) { int creator = 1; //1부터 시작 while (1) { int copy = creator; int sum = creator; //합은 생성자와 생성자의 각 자리 숫자의 합 while (copy) //각 자리 숫자의 합을 구한다 { sum += copy % 10; copy /= 10; } //조건 성립시 혹은 생성자가 없을 경우 if (c..

문제 링크입니다: https://www.acmicpc.net/problem/1012 쉬운 문제였는데 사소한 부분에서 고생한 문제였습니다.저는 그래프에서 좌표를 (y, x) 기준으로 문제를 푸는데 문제는 (x, y) 기준으로 제시되어서 좌표를 입력 받을 때 int x, y; cin >> x >> y; lettuce[y][x] = 1;이런 식으로 입력받아야했습니다.물론, (x, y) 기준으로 문제를 푸시는 분들은 고려하지 않아도 되는 문제입니다. 이후에는, 간단한 DFS로 문제를 해결하면 됩니다!결국, 컴포넌트가 몇개인지 구하는 문제였습니다. #include #include //memset using namespace std; const int MAX = 50; typedef struct { int y, x..

문제 링크입니다: https://www.acmicpc.net/problem/1507 플로이드-와샬 알고리즘을 사용하여 최소의 도로를 선택하는 문제였습니다.플로이드 알고리즘을 적용하여 i에서 j로 가는데 k를 거쳐가는 경우와 같다면 보다 많은 도시를 커버해야하기 때문에 i->j 도로를 선택하지 않고 i->k, k->j 도로를 선택합니다.반면, i->j로 가는 경로의 길이가 k를 거쳐가는 길이보다 크다면 최소 이동거리가 성립하지 않기 때문에 -1을 출력합니다. #include #include //memset using namespace std; const int MAX = 20; int N; int graph[MAX][MAX]; int road[MAX][MAX]; int result; void floyd(v..

문제 링크입니다: https://www.acmicpc.net/problem/2667 DFS(Depth First Search) 혹은 BFS(Breadth First Search) 모두 사용할 수 있는 문제였지만 저는 DFS를 이용해 문제를 해결했습니다.대각선은 고려하지 않으므로 Dir형 배열을 통해 상하좌우를 확인하여 각 단지 내 집을 파악하였고 한 단지 내 DFS를 끝내면 집의 수를 residance 벡터에 추가했습니다.총 단지 수는 residance 벡터의 size를 출력해주면 되고 residance를 정렬하여 모두 출력해주면 간단히 AC 받을 수 있는 문제였습니다! #include #include #include #include using namespace std; const int MAX = 25..

문제 링크입니다: https://www.acmicpc.net/problem/2217 최대 허용 중량이 w인 로프는 각각 하나씩 밖에 없으므로 그리디하게 접근할 수 있는 알고리즘 문제였습니다.로프 중량을 오름차순으로 정렬한 뒤 (N-i+1)개를 병렬로 중첩하여 최대 중량을 찾아내는 식으로 접근하는 문제였습니다! #include #include #include using namespace std; int N; vector rope; long long maxWeight(void) { long long result = 0; //각각의 로프는 한 개씩만 존재하므로 그리디하게 접근 for (int i = 0; i < N; i++) { long long weight = rope[i]; //rope[i]를 병렬로 (N..

문제 링크입니다: https://www.acmicpc.net/problem/7568 pair형 벡터를 이용해 (키, 몸무게, 등수)를 저장하였는데 너무 복잡하다고 생각된다면 다른 방법으로 저장해도 무난하게 풀 수 있는 문제였습니다.for문을 두번 돌려서 자신보다 키와 몸무게가 둘 다 큰 사람이 있을 경우 등수를 올리면 무난하게 AC를 받을 수 있는 문제였습니다! #include #include #include using namespace std; int N; vector v; //키, 몸무게, 등수 void printOrder(void) { for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) { if (i == j) continue; //키와 몸무게가 모두..

문제 링크입니다: https://www.acmicpc.net/problem/2668 DFS(Depth First Search)를 통해 사이클을 이루는 노드들을 찾는 문제였습니다. 알고리즘은 아래와 같습니다.1. DFS 함수의 매개변수로 탐색을 시작하는 노드와 움직인 노드를 전달합니다.2. 사이클을 이루면 cycle 배열에 저장하고 노드의 갯수를 증가시킵니다. #include #include using namespace std; const int MAX = 100 + 1; int N; int cnt; int node[MAX]; bool visited[MAX]; bool cycle[MAX]; bool DFS(int startNum, int nodeNum) { if (visited[nodeNum]) retur..

문제 링크입니다: https://www.acmicpc.net/problem/7576 전형적인 BFS 문제였지만 모든 토마토가 익지 않은 경우도 고려해야했기 때문에 살짝 까다로운 문제였습니다. 알고리즘은 아래와 같습니다.1. 창고를 입력 받는데 1이면 덱에 넣고, -1이면 noTomato를 증가시킵니다.2. 창고에 있는 토마토가 모두 익었다면 0을 출력하고 아니라면 BFS 함수를 호출합니다.3. BFS 함수를 호출하였는데 덱이 비어있다면 모든 토마토가 익을 수 없는 경우이므로 -1을 반환합니다.4. 현재 덱 사이즈만큼 for문을 돌리면서 front에 있는 좌표를 꺼내 창고 범위 내에 있는 상하좌우에 있는 안 익은 토마토를 익힌 뒤 해당 좌표를 덱에 넣고 front를 pop 시킵니다.5. 현재 덱 사이즈만큼..

문제 링크입니다: https://www.acmicpc.net/problem/2846 특별한 알고리즘을 요구하지 않는 문제였습니다. 알고리즘은 아래와 같습니다.1. 시작 위치를 정합니다.2. 시작 위치를 기준으로 인덱스 하나씩 넘어가면서 자신보다 높은 위치이고 시작위치로부터 쭉 오르막길인지 확인합니다.3. 오르막길이 아니면 바로 두 번째 for문을 탈출하여 여태까지 높이차를 구합니다.4. 최대 높이차를 구합니다. #include #include using namespace std; const int MAX = 1000; int N; int hill[MAX]; int maxHeight(void) { int result = 0; for (int i = 0; i < N; i++) { int start = hil..