dfs로 사용할 경우 n^2의 시간복잡도를 가지기 때문에 1억이다. 하지만 dfs로 일단 억지로 풀어보겠다. dfs에서 int형으로 만들어서 쿠키를 하나씩 주워가는 형식을 만들었다. 이 형식을 이용해서 max를 뽑고 max값과 동일한 vertex의 번호를 출력한다. using namespace std; int n, m, a,... Tag: 코딩 테스트

이 문제는 n의 크기가 100만이다. 그럼 무식하게 풀었을 경우 100만 X 100만의 크기를 짐작할 수 있으니 이 방법은 사용하면 안된다. 그리고 짝을 맞추는건 stack을 사용해야한다. using namespace std; int n, a[1000004], ret[1000004]; stack<int> s; int main() { cin >>... Tag: 코딩 테스트

계산해보면 시간복잡도가 400만 정도되니 무식하게 풀어도 될것이다. 벽을 세우고 바이러스를 퍼뜨려서 갈 수 있는 곳을 미리 차단한다. 그리고 순회를 돌면서 visited와 a의 공간안에 0이 있으면 카운트를 해주면 된다. using namespace std; int a[10][10], visited[10][10], n, m, r... Tag: 코딩 테스트

머리를 엄청 굴려야 되는 문제였다. 하지만 코드는 짧다 우선 r은 right로 오른쪽 기준을 뜻하고 그럼 l은 당연히 왼쪽 기준을 말한다 그래서 l을 기준으로 잡고 l+m-1을 하면 오른쪽이 나온다. 다른 문제에서 비슷한 유형이 많이 나올 것 같으니 외워놓자. using namespace std; int n, m,... Tag: 코딩 테스트

이 문제는 커스텀 오퍼레이터가 생각나야한다. 커스텀 오퍼레이터는 sort를 했을때 뒤에 커스터마이징 하는 함수를 붙여주는 것이다. 아래에는 cmp로 만들었는데, return이 상식적으로 말이 안된다. pair일때는 두번째 second 값을 정렬하게 하고 싶다면 아래 블로그처럼 해... Tag: 코딩 테스트

일단 ture와 false로 이루어지기 때문에 조건에 성립하지 않다면 flag를 1로 만들어버린다. 그리고 조건을 하나하나 처리해가면서 풀어준다. 그리고 prev의 사용은 [i] == [i-1]과 동일하다. using namespace std; string s; int lcnt, vcnt; bool isVowel(int idx) { return ... Tag: 코딩 테스트

이 문제의 핵심은 알파벳과 숫자를 나누는 것이다. 그 방법은 아스키코드를 활용해서 65 미만으로 잡을 경우 알파벳은 들어오지 않게 만든다. 그리고 string 은 sort를 할 경우 맨 앞자리만 비교하므로 아래와 같이 cmp를 만들어줘서 sort에 활용한다. using namespace std; int n; string ... Tag: 코딩 테스트

이 부분은 간단하게 문제대로만 풀면 풀리는 문제이다. 첫번 째 무식하게 풀었던 코드이다. using namespace std; int n, m, cnt; bool met = false; string s; char a[101][101]; int ret[101][101]; int main() { cin >> n >> m; for (int i = 0; i < n; i++... Tag: 코딩 테스트

이 문제는 n 팩토리얼의 오른쪽 끝에 있는 0의 갯수를 찾는 것이다. 10은 2와 5의 조합이다 그러므로 n을 2제곱으로 나눈 수와 5제곱으로 나눈 수를 구해서 둘중에 작은 수를 출력하면 답이다. using namespace std; int n, a; int main() { ios_base::sync_with_stdio(false); c... Tag: 코딩 테스트

이번 문제는 전부다 초로 환산해서 사용하면 편하다. 그리고 현재 시간을 prev에 넣어두고 다음에 시간이 들어오면 그 시간과 차를 더해서 구한다. using namespace std; #define prev aaaa int n, o, A, B, asum, bsum; string s, prev; string print(int a) { string d =... Tag: 코딩 테스트

이 문제는 n이 1000만 정도 되니 무식하게 풀 수 있는 문제이다. for문으로 무한루프를 돌면서 더해주며 풀었다. using namespace std; int n; int main() { cin >> n; int i = 666; for (;; i++) { if (to_string(i).find("666") != string::npos) { ... Tag: 코딩 테스트

짝 맞추는 문제는 무조건 stack을 생각해야된다. 처음에 (와 )의 갯수를 카운팅하는 방식을 택했는데 생각해보니 )이게 먼저 들어오면 답이 없었다. stack으로 pop해주는 방식을 사용한다. using namespace std; string s; int n; bool check(string s) { stack<int> stk; for (... Tag: 코딩 테스트

짝맞추기이니 stack을 사용해야 한다. 그런데 [와 (가 두개 등장한다. 이러면 [ ( ] ) 이런 상황이 생길 수 있으므로 두번 체크를 해줘야한다. using namespace std; string s; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); while ... Tag: 코딩 테스트

인접 행렬은 정점 사이에 간선이 있다면 1 없다면 0으로 나타내는 행렬 그래프이다. 0번부터 방문안한 노드를 찾고 해당 노드부터 방문하며 방문해서 출력하는 재귀함수를 만들고, 방문했던 정점은 다시 방문하지 않는 프로그램을 짠다면. using namespace std; const int V = 10; bool a[V]... Tag: C++

인접 행렬을 했으면 이것을 리스트로 만드는 것이다. 하지만 vector를 사용해도 무관하다. 우선 공간복잡도를 알아보자면 인접해열 : O(V^2) 인접리스트 : O(V+E) 다음 시간 복잡도(간선 한개 찾기)는 인접행렬 : O(1) 인접리스트 : O(V) 시간 복잡도(... Tag: 코딩 테스트