[초기 접근 방법] 1. 랜덤 지점에서, 랜덤 지점까지 갈 수 있는지를 체크해야 한다. 2. 플로이드 알고리즘으로 minDis[][] = '최소거리', 모든 노드에서의 최소 거리를 구한다. 3. minDis[s][e] 를 출력한다. [생각] 문제는 단방향 길을 양방향으로 고치는 것이다. 따라서 존재하는 길을 '0', 단방향이면서 존재하지 않는 길을 '1'로 설정해 최단경로를 찾으면 된다. 추가로 minDis를 초기화 할 때, 주어지지 않은 길은 FIX 값으로 초기화하고 해당 길은 탐색하지 않도록 하자 [코드] # 풀이 시간 : 47분 # 시간복잡도 : O(N^3) # 공간복잡도 : O(N^2) # 참고 : - import sys input = sys.stdin.readline FIX = 10000 # ..

[초기 접근 방법] 당시 잘못된 접근법 → dp[i][j] : i번째 앱까지 중 j byte를 얻는데 소모되는 최소 cost 그러나 i의 범위는 100, j의 범위는 1천만이었기에 dp[][] 를 계산하게 되면 시간∙공간 복잡도가 매우 높다. 따라서, "비용"을 배낭의 크기로 생각하고 접근하는 것이 효율적이다. [생각] - dp 배열 정의 → dp[i][j] : i번째 앱까지 중 j 비용으로 얻을 수 있는 최대 byte 수 - 점화식 → dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - cost[i]] + memory[i]) 현재 앱을 계속 활성화 시켰을 때의 byte vs cost를 소모하면서 비활성화 시켰을 때의 byte 비교 Knapsack 풀이와 똑같았다. 4달 전쯤 풀..

[초기 접근 방법] 검사 문자열 inspect에 대해 집합 S 문자의 접두사가 맞는지 체크 → 시간복잡도가 O(MN * len(inspect[i])) = O(1억 * a) 으로 시간초과가 된다. [생각] 문제 유형을 보니 "Trie"라는 처음 보는 자료구조여서 블로그를 참조해 먼저 공부했다. Trie : 문자열을 저장하고 효율적으로 탐색하기 위한 '트리' 형태의 자료구조 → 자동완성, 사전 검색 등 문자열 탐색 기능 - insert() // 생성 시간 복잡도 : O(N*L) void insert(String word) { TrieNode node = this.rootNode; // 문자열의 각 단어의 자식노드를 찾아 return 하거나, 자식노드 새로 생성 // Map에서 현재 문자를 key로 Value..

[초기 접근 방법] - 맨 처음에 제시한 사람은 무조건 "진실"만을 들어야 한다. - 각 사람마다 일관되게 "과장된 이야기 or 진실"을 들어야 한다. - 해당 파티에서는 무조건 "과장된 이야기 or 진실"을 이야기해야 한다. 1. 제시한 사람이 있는 파티는 일단 전부 진실을 말한다. 2. 위 파티에 있는 사람들 모두 "진실파티" 에 넣는다. 3. 각 파티를 탐색하면서 파티 참석 인원 중 "진실파티"에 있는 사람이 있다면 참가한 사람들을 "진실파티"에 추가를 하고, 파티를 처음부터 다시 탐색해야 한다. "진실파티"에 있는 사람이 없다면 해당 루프에서 종료한다. [생각] 1. input.split() 내에서의 슬라이싱 set(map(int, input().split()[1:])) 2. set.union()..

[초기 접근 방법] 1. N! 을 구하자 2. 0의 개수를 세자 [생각] 위와 같이 심플한 방법으로 접근하면 문제에서 N의 범위가 500까지이기 때문에 'OverflowError'가 발생한다. 따라서 OverFlow를 방지하기 위해 N!을 하는 과정에서 수의 크기를 관리해주어야 한다. 이 때, N!의 1의 자리만 보존해도 되기 때문에 다음과 같이 코드를 작성한다. # 10으로 나눠질 경우 if fact % 10 == 0: while True: # 1의 자리만 남기도록 한다. if fact % 10 != 0: fact %= 10 break fact /= 10 zeroCount += 1 [코드] # 풀이 시간 : 10 + 25분 # 시간복잡도 : O(N) # 공간복잡도 : O(1) # 참고 : - # 왜 ..

[초기 접근 방법] 1) 상위 15%, 하위 15% 절사 - 이 때, 소수점은 반올림 계산 2) 계산된 평균 반올림 계산 [생각] 1) 수식을 작성할 때, "0 / x" 와 같은 ZeroDivision 주의 2) 파이썬의 반올림은 ".5"와 같이 올림, 내림했을 때 동일하게 차이가 나는 경우에는 짝수 값으로 반올림 합니다. → 따라서 파이썬으로 풀 경우, epsilon. 즉 굉장히 작은 값을 더해 우리가 일반적으로 생각하는 반올림이 될 수 있게끔 해야 한다. [코드] # 풀이 시간 : 20분 # 시간복잡도 : O(NlogN) # 공간복잡도 : O(N) # 참고 : python round() 관련 자료 # https://blockdmask.tistory.com/418 import sys input = sy..