SUEATY 발은 개발

The Floyd-Warshall Algorithm 모든 정점 쌍에 대해 둘 사이의 최단 거리를 구하는 알고리즘 Dijkstra/Bellman-Ford 를 반복해서 구할 수도 있음 경유점 : 두 정점 u와 v를 잇는 어떤 경로가 있다고 가정할 때, u와 v 사이에 있는 다른 정점 1. 경유점 k를 제외한 S - {k} 노드 중 서로 다른 노드 U, V 선택 (S = 정점 집합일 때 k, U, V ∈ S) 2. U → k → V의 비용 확인 후 최단거리 갱신 직접 해보기 다음과 같은 그래프가 주어졌다고 해보자. Floyd-Warshall 알고리즘은 Dijkstra와 다르게 모든 그래프의 모든 정점 쌍의 최단 거리를 저장해야하므로 2차원 배열이 필요하다 초기화 할 때에는 if from == to, then ..

(뭐 대충 중요하다는 내용ㅎ) 최단 경로 문제를 풀 때 가장 많이 언급되고 활용되는 삼대장이 있죠? 다익스트라 벨만포드 플로이드 상황에 맞게 위 알고리즘을 적용해서 문제를 해결하면 될텐데 언제, 무엇을 선택할 지 모르겠다면 3가지를 떠올려봅시다. 문제를 그래프화 하는 것에 성공하셨다면 이제 이 3가지 흐름을 생각해 봅시다. 가중치가 있는가? : 가중치가 없다면 BFS로 해결 가능 음수간선이 있는가? : weight에 음수 값이 있다면 벨만포드 단일 시작점을 갖는가? : 단일 시작점이 주어진다면 다익스트라, 모든 정점들의 쌍에 대한 경로 값을 알고 싶다면 플로이드 어떤 알고리즘을 쓰면 되는지 선택하셨다면 각 알고리즘들의 개념을 짚어보도록 하겠습니다. 오늘은 Dijkstra Algorithm에 대해 먼저 살..

이 글에서는 프로그래머스의 Level 1 문제 중 꼭 한 번은 다루고 넘어갔으면 좋겠는 문제들에 대해 살펴보도록 하겠습니다. 문제 풀이는 C++로 이루어져 있고 함께 들어가 있는 개념들도 간단히 정리 해보는 형식으로 작성되었으므로 오타등의 오류가 있을 수 있습니다. 오류 발견시 댓글로 꼭 말씀해주세요! 시작해볼까요? 일단 시작하기 전, 프로그래머스 Level 1 문제에는 [2019 카카오 개발자 겨울 인턴십 : 크레인 인형뽑기 게임] [2018 카카오 블라인드 채용 1차 : 비밀지도, 다트게임] [2019 카카오 블라인드 채용 1차 : 실패율] [2018 summer/winter coding : 예산]이 포함되어 있습니다. 이 문제들은 선택적으로 풀어보는 것이 아닌 반드시 풀어보아야 할 문제일테니 따로 ..

[6190] : 정곤이의 단조 증가하는 수 입력 : N개의 정수 → 가능한 곱셈 조합을 알아보니까 계속 된 인덱싱이 필요하므로 벡터보다는 배열이 더 적합 출력 : 단조증가 수 중 가장 큰 곱셈조합 (없으면 -1) 전략 단조 증가하는 수 판별 법 : 10으로 나누어보았을 때 직전 나머지가 현재 나머지보다 커야 함 10보다 작은 수는 단조 증가로 판단하므로 do-while 사용 #include using namespace std; bool isItIncreasingNum(int); int main(void){ int testCase; cin >> testCase; for(int tc = 1; tc > N; int *numArr = new int[..

[6730] : 장애물 경주 난이도 입력 : 블록의 높이들 → 고정된 값이고, 삽입 삭제가 일어나지 않을 예정이므로 배열(: blocks)을 사용 출력 : 1) 올라갈 때 가장 심한 높이 변화 2) 내려갈 떄 가장 심한 높이 변화 전략 blocks[i - 1]과 blocks[i]를 비교해서 up인지 down인지 판별 방금 비교한 up / down이 maxUp / maxDown 보다 큰지 판별해서 업데이트 #include using namespace std; int main(void){ int testCase; cin >> testCase; for(int t = 0; t > blockCount; // blo..

[1970] : 쉬운 거스름돈 #include using namespace std; void getChange(int); int main(void){ int testCase; cin >> testCase; for(int test = 0; test > changeM; getChange(changeM); } return 0; } void getChange(int money){ int mType[8]{0,}; int static trial = 1; while(money > 9){ if(money >= 50000){ mType[0] += 1; money -= 50000; } else if(money >= 10000){ mType[1] += 1..

[1859] : 백만 장자 프로젝트 #include using namespace std; int main(void) { int testCase; int day; cin >> testCase; long * ans = new long[testCase]; for (int i = 0; i > day; long * price = new long[day]; long total = 0; for (int j = 0; j > price[j]; long max = price[day - 1]; for (int j = day - 2; j > -1; j--) if (price[j] < max) total += (max - price[j]); else ma..

[1986] : 지그재그 숫자 #include #include #include using namespace std; vector answer; void printAnswer(int); int main(void){ int testCase; cin >> testCase; for(int test = 0; test > num; for(int n = 1; n < num + 1; n++){ if(n % 2 == 0) sum -= n; else sum += n; } answer.push_back(sum); } printAnswer(testCase); return 0; } void printAnswer(int testCase){ for(in..

[1545] : 거꾸로 출력해 보아요 #include using namespace std; int main(void){ int N; cin >> N; for(int i = N; i > -1; i--){ cout N; cout

[2046] : 스탬프 찍기 #include using namespace std; int main(void){ int N; cin >> N; for(int i = 0; i input; int i = 0, c; while((c = input[i])){ putchar(toupper(c)); i++; } } [2050] : 알파벳을 숫자로 변한 #include #include using namespace std; int main(void){ string input; cin >> input; int size = input.length(); for(int i = 0; i < size; i++) cout N; string dates[N], ans[N]; for(int i = 0; i ..