본인 sql 빼고 3솔
1번
1만 * 1만 배열에서 아래/윗 삼각행렬만 살피면 됨 => for i in range(n)
for j in range(i+1,n)
행렬 서칭 중 가장 최대값 높은 열을 뽑으면, 그게 꼭지점이 됨. 만약 1~10까지의 점중에 최대값을 가지는 점이 1,5 라면, 이 선분의 양 끝점은 1과 5임.
그렇게 꼭지점을 찾으면 루프 종료. 이제 꼭지점을 기준으로 점들 줄세우고, reversed로 하나 더 추가한담에 사전순으로 정렬
2번
완탐으로 ?에 'a,b,c다 넣어보기 -> 3^9
다 넣었을 때, a와 b와 c로 bfs 돌려서 연결되어있는 문자의 개수 합함 -> 개수가 n*m 보다 작으면 패스, n*m이면 answer +=1
3번
bfs 로 도착지점까지 탐색. 가중치가 k가 일때 도착지가 b인경우, k 미만일때 도착지가 b인경우의 경로를 dic에 저장.
dic의 key값을 list로 받고, len(keys)를 return하면 끗
ㄱㅅㄱㅅㄱㅅㄱㅅ
1번 좀만 설명 가능할까...? "꼭지점을 찾으면 루프 종료" 까지는 이해했는데 "꼭지점을 기준으로 점들 줄세우고, reversed로 하나 더 추가한담에 사전순으로 정렬" 이 부분이 이해가 안돼..
꼭지점이 열 인덱스인 리스트를 보면 각 점까지의 거리들이 나열되어있음. 그럼 현재 인덱스인 점이 끝점이니깐, 거리를 오름차순으로 정렬하면 그 순서가 점들이 나열된 순서임. 예를들면 0,1,2,3의 점 중에서 1번점의 배열이 1 0 4 5이고 이게 최대값 행렬이라면 1번점을 왼쪽/오른쪽 끝에 놓았을 때, 거리순으로 점들이 선분위에서 정렬됨.
즉 1 0 2 3 이거나 3 2 0 1 이거나 두가지 경우밖에 없음. 이걸 answer 에 사전순으로 추가하면 됨.
와 아니 어떻게 이런 생각을 함? 진짜 천재인가;
행렬에서 가장 최대값찾으면 되는거구나... 나는 0번째 행을 기준으로 정렬해서 0 양쪽으로 가능한 모든 수 백트래킹해서 풀었는데 생각해보니 O(2^n)라 나가리였을듯... 이런 생각하는 팁이있음? 이제 코테 2달차인데 자괴감드네 진짜..
코테 많이풀어보면 익숙해져서 난이도 낮은건 금방금방 알고리즘 떠오름. 많이 풀어보셈
1번 1만 * 1만? TLE ㅅㄱ