어제의 나보다 성장한 오늘의 나

백준 1197번 문제는 MST( Minimum - Spanning -Tree )를 구하는 문제이다. 알고리듬으로 Union - Find 를 이용하여 구하면 간단하게 구할 수 있다. 문제 알고리듬 ① 입력 Edge들을 먼저 가중치 기준으로 오름차순 정렬 한다. - 정수 A,B,C 를 tuple 사용하여 묶어서 vector에 저장 - algorithm stl의 sort 함수 사용 (가중치 기준 정렬이므로 cmp 함수 추가) ② 정렬된 Edge들을 하나씩 꺼내며 싸이클이 생기는 지 확인 (Tree 이기 때문에 싸이클이 생기면 안됨) - 정렬된 edge들을 하나씩 꺼내며 정수 A,B의 find 값이 같은 지 확인 - 같다면 Union(A,B) 해주고 다르다면 무시 - 같을 때 Union 해주면서 그 edge의 ..

알고리듬 문제를 풀 때 시간이 굉장히 중요한데요 당연 시간 복잡도가 적게 드는 알고리듬을 선택하는 것이 관건이지요. 하지만 그 외에도 실행 시간을 줄여주는 꿀팁들이 있습니다. 이것 들을 습관화 해서 더 좋은 코드들로 발전 시켜 봅시다. ※ 참고 : C++에서의 팁입니다. 1) endl 대신 \n 사용 cout 을 해줄 때 다들 endl을 많이들 사용하시는데요. endl은 개행 문자 출력 + 버퍼 비우기 를 시행하기 때문에 시간이 더 많이 걸립니다. cout

우리는 가끔 엄청 큰 값 , 엄청 작은 값으로 특정 변수를 초기화 해야 할 때가 있다. 특히 알고리듬 공부를 할 때, Graph 나 Tree에서도 사용이 된다. C 언어로 , C++로 어떻게 해야 하는 지 각각 알아보자. 1) C언어 헤더 파일 #include Code int min = INT_MIN; // min int max = INT_MAX; // max 예제 #include #include int main(void){ int min = INT_MIN; int max = INT_MAX; printf("Min : %d\n", min); printf("Max : %d" , max); } 결과 2) C++ 헤더 파일 #include Code int min = std::numeric_limits::min(..

BFS 문제 중 기본 문제이다. BFS , DFS 문제를 찾고 있다면 이 문제를 풀어보는 것을 추천한다. 풀이 ◎ BFS 방식으로 해결 한다. (queue STL을 사용한다.) ◎ 한번 움직일 때마다 현재 몇번 왔는지를 기록한다. (map에 기록해 두었다.) ◎ 경계를 넘지 않고 , 1이면 이동한다. BFS 방식으로 상하좌우 모두 이동 가능한지 확인 해보고 가능 하다면 queue에 저장. queue에 담긴 좌표를 하나씩 꺼내보면서 탐색. queue에서 모두 꺼내고, 비게 되었다면 탐색을 마친다. 반드시 도착 경로가 있기 때문에 , 탐색을 마쳤을 때 이동 횟수가 map[N][M]에 저장 되어 있다. Coding #include #include #include using namespace std; int m..

이런 오류는 처음이었다... 매우 당황 스러웠지만 천천히 나의 코드를 살펴 보았다. 아니나다를까 cout

풀이 : 알고리즘만 잘 세우면 손 쉽게 해결할 수 있는 문제이다. 먼저 입력 받은 문자열을 자릿수에 따라 나누어서 map에 저장해둔다. 만약 AECDF 를 입력 받았다면 map에 (A,10000) , (E,1000) , (C,100) (D,10) (F,1) 저장해둔다. 그렇게 모든 문자열들을 저장한다. 만약 중복된 값이 나왔다면 더해서 저장한다. AAC 이런 문자열이 나왔다면 (A, 100) 을저장한 뒤 (A, 10)을 더해서 저장한다. 즉, (A,110)을 저장한다. 모든 입력이 끝나고 각 문자마다 second(map의 second 값) 값이 잘 정리되어 있다. (각각의 second 값) * (1~9 사이 값 지정) 들의 전체 합 이 가장 큰 수가 되야 하므로, second값을 따로 vector에 저장..

오늘은 c++에서 변수의 타입을 변경해야 할 때 사용하는 함수 및 방법을 정리해봤다. Ps에서 정말 많이 사용 되기 때문에 반드시 알고 있어야 한다. 1) int -> char 변환 ◎ '0' or 48을 더해준다. int before = 3; char after = before + '0'; // int -> char 변환. char after = before + 48; // 이렇게 써도 결과가 같다. 2) char -> int 변환 ◎ '0' 이나 48을 빼준다. char before = '3'; int after = before - '0'; // char -> int int after = before - 48; // 대체 가능 1) 2) 가 가능한 이유 '0' 이 아스키 코드 48 이다. 그리고 '1..

풀이 : 30의 배수이려면 3의 배수이면서 동시에 10의 배수이면 된다. 3의 배수는 각 자리 숫자의 합이 3의 배수이면 된다. 예를 들어 126 같은 경우 각 자리 숫자의 합은 1+2+6 = 9 이다. 9는 3의 배수이다. 그러면 126은 3의 배수이다. 10의 배수는 마지막에 0이 붙으면 된다. 이 두가지 조건을 만족하면 30의 배수라고 할 수 있다. 각 자리의 숫자의 합이 3의 배수인지 , 숫자열 속 0이 존재하는 지를 확인 한 뒤 두 조건을 모두 충족한다면 내림 차순 정렬 후 출력해주면 된다. Coding #include #include #include using namespace std; int main(int args , char** argv){ vector nums; // 각 자리 숫자 저장..