자료구조/SW Expert Academy (9) 썸네일형 리스트형 1263. 사람 네트워크2 All-pair shortest path에 대한 문제이다. 풀이방법에는 1. Dijkstra 알고리즘을 모든 시작 정점 n-1에 대해서 시현하는 것 2. Floyd Warshall Algorithm을 적용하는 것 둘의 시간복잡도는 O(n^3)으로 같지만 실행시간은 차이가 있다 Dijkstra가 압도적으로 빠르다 => 기존에 가지고 있던 Data를 가지고 start->해당 정점까지의 거리로 갱신된다, Dijkstra는 update가 필요한 노드의 최단거리만 확인하거나 Heap을 이용해서 앞쪽에서 갱신된 최단거리가 더 작으면 cutting이 되는 case가 많다. 더 빠르게 할 수 있는 방법: BFS 극한의 빠르게 할 수 있는 방법: Best First Search!!! => 나중에 풀어보고 성능을 비교해보.. 1251. 하나로 Kruscal 최적 성능을 위해 연결리스트로 표현하는 이유가 뭘까? #include #define INFINITI 987654321987654321 const int MAX_NUM = 1001; using namespace std; struct pos { int x; int y; }; pos iArr[MAX_NUM]{ 0, }; long long getDistance(pos a, pos b) { return (((long long)a.x - b.x) * ((long long)a.x - b.x) + ((long long)a.y - b.y) * ((long long)a.y - b.y)); } // // // // Heap 구현 // // struct edge { int from; int to; long lo.. 1249. 보급로 다익스트라 알고리즘을 적용할 수 있을까를 생각해보자 거리 테이블이 2차원이다. => Matrix의 각 칸을 노드라고 생각하면 역시 그래프이다. 따라서 다익스트라의 거리테이블 1차원이지만 Matrix에서 거리테이블을 2차원으로 구축해도 괜찮다. #include #define INFINITI 987654321 using namespace std; int const MAX_LEN = 101; bool U[MAX_LEN][MAX_LEN]{ false, }; // 업데이트 필요여부를 확인하기 위한 배열 int D[MAX_LEN][MAX_LEN]{ 0, }; struct pos { int x; int y; }; pos extractMin(int N) { pos minPos{ 0 }; int minVal = INFI.. 1267 - 작업순서 Topology sort를 생각을 해야한다. DAG(direct acyclic graph) 의 작업순서를 출력해야하기 때문이다. 만약 위상 정렬ㄹ이 생각이 안나면 어떻게 해야할까? ' => 진입차수가 0인거 부터 시작해서 BFS를 해도 된다. 전형적인 BFS와 동일한 알고리즘이지만 처음에 BFS시작전에 Queue에 초기에 진입 차수가 0인 노드들을 모두 넣고 시작하면 된다. 하지만 진입차수가 2이상인 놈을 처리하기 위해서 복잡한 작업이 필요한데 더이상 진행하지 않고 해당 노드의 진입차수를 1감소시키고 나온다. =>하지만 이런 개념을 간소화 시킨게 topology sort이다. 해당 정점의 진입 차수만 생각을 해서 1. Queue를 이용해서 위상 정렬을 할 수 있다. 2. 진입차수 배열의 값을 -1 로 만.. 2948. 문자열 교집합 해시 테이블에서 고려해야할 것 중 하나는 중복된 데이터가 들어올 수도 있다는 것을 고려해야한다. 나는 중복된 데이터가 많이 들어오는 경우를 고려하지 못했다. 다른 방법 두 집합에 입력된 모든 문자열을 사전순으로 나열하고 Stack처럼 비교하면서 Counting한다. #include #define TABLE_SIZE 1000000 #define STR_SIZE 51 using namespace std; int hashFunc(char* str) { int ret = 0; while (*str) { ret = (ret+ ((*str) - 'a')) %TABLE_SIZE; ret = (ret *10) %TABLE_SIZE; str++; } return (ret % TABLE_SIZE); } char t1[TA.. 1232 - 사칙연산 단, 조항을 잘읽어야하는 문제이다. 중간 과정에서 연산을 실수연산으로 하고 최종결과값만 정수부를 출력해야한다. 테스트 케이스 중에 1 / 0.5 같은 연산도 존재하기 때문에 이 예외를 처리하지 않으면 Divided by Zero 런타임 에러가 발생할 수 있다. 그리고 입력이 굉장히 까다로웠다. cin으로 사용하기 위해서는 getline함수이나 그냥 cin을 이용해서 한줄을 모두 받아들이는 방법이 좋고, 나는 printf와 getchar를 이용해서 적절하게 버퍼에 데이터를 순차적으로 읽어들였다. 그리고 Stack을 활용했을 때 굉장히 주의해야할 점을 무시해서 스택 top index가 계속 -1보다 작은 경우가 발생하는 에러를 핸들링하지 못해서 고생했다. Class는 다양한 대입연산, 복사생성자등 많은 연산.. [SW Expert Academy]1257 - K번째 문자열 부분문자열을 모두 찾아서 사전 순서로 정렬하는 방법으로 접근하면 풀 수 없다. 게다가 예시로 주어진 "food" 만 해도 o가 두번 나와서 중복을 제거해야한다. -> LCP배열이 필요하다. 접미어들을 정렬하고 접두어들을 뽑아내면 사전순으로 정렬된 상태로 나온다. food -> f fo foo food ood -> o oo ood (LCP[3] = 1) od -> o od d -> d 정렬 결과: d o od oo ood f fo foo food #include #define MAX_LEN 400 #define ASCII_NUM 256 using namespace std; int cmpStr(char*str1, int len1, char* str2, int len2) { int iter1 = 0, iter.. SW acadeny 1265 달란트2 //공백을 포함한 문자열을 입력받아 각 단어로 분리하여 문자열 배열에 저장한 후 입력순서의 반대 순서로 출력하는 프로그램을 작성하시오. //문자열의 길이는 100자 이하이다. #include using namespace std; int max_sum; void group(int gCount, int left, int* group_box, int gsize) { if (left == 0) { //for (int i = 1; i TC; long long res[20]{ 0, }; for (int t = 0; t > N >> P; long long* group_box; group_box = new long long[P+1]; long long .. 이전 1 2 다음
