시나브로

이 문제는 전형적인 DFS/BFS 완전탐색 문제이다. Solution 값을 입력 받는다. 여기서 값이 1인 인덱스를 벡터 stack에 입력한다. 벡터 stack이 빌때까지 while문을 돌면서 dfs 함수를 호출한다. 호출할 때는 새로운 단지를 발견한 것이기에 answer함수에 새로운 단지를 찾았다는 뜻으로 push_back으로 값을 넣어준다. dfs함수에서는 4방향을 보며 1일 경우, 재귀호출을 해준다. => 여기서 유의점은 범위체크이다. 인덱스가 배열을 범위를 넘어서면 무조건 오류가 나기때문에 귀찮더라도 범위체크를 해줘야한다. 재귀호출하면서 집의 갯수를 세야된다. 그렇기에 새로운 집에 방문할때마다 answer의 마지막 요소에 +1를 해준다. 여기서 왜 마지막 요소인가하면, 동시에 여러단지를 검색하지않..

Solution 총감독관은 필수적이기 때문에 배치한다 이에 따른 answer값과 space(고사장별 응시자 수를 저장하는 vector 변수)값을 연산해준다. 이후 남은 응시자수를 C로 나눈 몫이 부감독관의 수이기 때문에 연산을 해준다 단, 여기서 유의점은 몫이 나눠어 떨어지지 않을 경우, 부감독관이 한명 더 필요하다는 것이다. Key Point answer 변수형태를 long long으로 해야한다. 시험장 개수가 1000000개이며, 시험장별로 최대 응시자 수도 1000000이기에 long long 변수형태를 이용해야된다. 이를 사용하지 않을 경우, 바로 틀렸습니다가 뜬다 유의하길. 또한, 총감독관의 수를 뺀 이후 응시자의 값이 음수가 될 수 있음을 유의하라. #include #include #inclu..

나는 크루스칼 알고리즘으로 mst를 구현하였다. 하지만, 이 소스에서는 개선점이 있다. union-find 알고리즘을 사용해서 좀더 효율적으로 구현이 가능할 것 같다. #include #include using namespace std; #define MAX_NUM 100010 int input[MAX_NUM][3]; int num; int n = 0; int m = 0; void swap(int i ,int j) { int temp[3] = { input[i][0],input[i][1], input[i][2] }; input[i][0] = input[j][0]; input[i][1] = input[j][1]; input[i][2] = input[j][2]; input[j][0] = temp[0]; in..

정렬을 이용하여 단어를 정렬하는 문제였다. 정렬을 이용하는 가장 쉬운 문제였지만, 이 문제의 경우 퀵정렬을 사용할 경우 시간초과가 뜬다. 이에 유의해서 merge sort를 사용하였다. 시간은 딱맞았다. 하지만, merge sort의 경우, 배열을 2배를 사용했기에 공간효율이 좋지 못한 것 같다. -런타임에러 : 배열의 크기를 선언할 때, 0을 하나 누락했었다. - 시간초과 : 알고리즘을 수정하였다. quick -> merge sort로 #include #include using namespace std; string list[20001]; void swap(int i, int j) { string temp = list[i]; list[i] = list[j]; list[j] = temp; } int ch..