성준이의 개발블로그 성준이의 개발블로그

문제 링크https://www.acmicpc.net/problem/1920아이디어이번 문제는 시간복잡도를 줄이며 두번째 숫자 모음에 있는 숫자들이 첫번 째 숫자 모음에 있는지 탐색하는 문제라는 생각이 들었습니다. 어떻게 시간복잡도를 줄일지 생각하다가, 처음에는 이진 탐색이 생각 났습니다. 그런데 이것은 정렬이 선행되어야 했고, 정렬의 평균적 시간 복잡도는 O(nlogn)이기 때문에 좀 더 빠른 방법이 없을지 고민해 봤습니다. 그러다가 배열을 set함수를 사용해 집합으로 바꿔 평균 O(n)시간복잡도로 중복을 제거하고, 평균 O(1) 시간복잡도로 탐색하면 더 빠를 거 같아 set함수를 이용한 탐색을 사용하기로 결정했습니다. 문제 해결의 아이디어는1. 두번째 줄의 숫자들을 arr배열에 저장해둡니다.2. 중복을..

문제 링크https://www.acmicpc.net/problem/21736아이디어1. 처음에 도연이의 위치를 이중반복문을 통해 찾아내서 x,y에 저장해두고2. 도연이의 위치로 dfs를 시작해서3. 만날 수 있는 사람의 수를 res에 저장하고4. res가 0이라면 "TT"를 출력하고 아니라면 res 그대로 출력 소스코드"""1. 아이디어 - 도연이의 위치를 찾는다 - 도연이 위치에서부터 dfs 시작한다. - 방문하면서 P를 찾으면 결과에 1을 더하고 - 마지막에 출력할 때 0이면 TT 출력하고 아니면 그 숫자 출력2. 시간복잡도 - 위치 찾기 = h(600) * w(600) = 36000 - O(V + E) = O(V + 4V) = O(5V) = 36000*5 = 180000 3. 자료구조..