이름 못 정한 블로그

가장 먼 노드를 찾기 위해서 BFS를 적용할 수도 있었는데 나는 다익스트라 알고리즘을 적용해서 풀었다. 다익스트라는 한 노드에서 각 노드에 대해 가장 짧은 경로를 찾아준다. 따라서 다익스트라 결과에서 가장 큰 값을 찾고 같은 값이 몇개인지만 찾으면 된다. #include #include #include #define INF 1000000 using namespace std; int map[20001][20001]; int dist[20001]; bool visit[20001]; void Dijkstra(int start, int n){ int cur, min, min_idx; for(int i = 1; i

한문제만 풀기 섭섭해서 한 문제 더 풀었다. 원래는 DP에 있는 N으로 표현 문제를 풀다가 너무 어려워서 이 문제로 도망쳤는데 오히려 아까 푼 문제보다 더 빨리 푼 듯하다. 푸는데 5분 정도 걸린거 같다. 레벨3 치고는 너무 쉽거나 내가 DP를 겁나 못하거나 둘 중 하나겠지. 처음엔 union-find로 풀까 하다가 단순히 DFS만 돌려도 될 것 같길래 이렇게 풀었다. 어느 한 노드에서 DFS를 시작해서 끝났는데도 아직 방문하지 않은 노드는 다른 네트워크다. 따라서 모든 노드를 방문할 때까지 DFS를 돌리면 그 횟수가 네트워크의 개수가 된다. #include #include using namespace std; int visit[201] = { 0, }; void DFS(int cur, int n, ve..

백준만 풀기 섭섭해서 프로그래머스도 한문제 풀어봤다. 날먹하려고 가장 만만한 브루트포스로 풀었다. 근데 벡터 사용이 어색해서 좀 버벅였다...ㅋ 문제 자체는 아주 쉬웠다. #include #include using namespace std; vector solution(vector answers) { vector answer; int score[3] = {0, }; int idx[3] = {0, }; const int giver1[5] = {1, 2, 3, 4, 5}; const int giver2[8] = {2, 1, 2, 3, 2, 4, 2, 5}; const int giver3[10] = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5}; for(int i = 0; i < answers.siz..

https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net TSP 문제는 학교에서 배웠지만 실제로는 처음 풀어본다. hueristic 알고리즘으로 NN(Nearest Neighbor)도 배웠던 기억이 있다. 시작점에 대해서 고민해봤는데 어차피 circuit이 생기니까 어디서 시작하는지는 중요하지 않았다...ㅋ 입력을 보니 Floyd가 생각나서 이걸 쓸 수 있을까도 생각해봤지만 이 문제랑 관련은 1도 없었다. 고민해보다..

https://www.acmicpc.net/problem/2342 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net 재귀함수와 DP를 이용하는 문제 왼발이랑 오른발이 따로 움직여서 처음엔 뭔가 싶었다. i번째에 왼발 오른발이 어디에 있는지 저장해서 풀 수 있었다. 그때 들이는 가장 적은 힘을 배열에 저장해뒀다. #define _CRT_SECURE_NO_WARNINGS #include int i; int order[100001]; int power[100001][5][5]; in..