Algorithm

https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 1. Preview 시간 복잡도 1) Trie 자료구조 : O(N * L) - N : 전화번호 개수 - L : 전화번호 길이 2) 문자열 비교 : O(N) 공간 복잡도 : O(N) 2. 초기 접근 방법 https://wch-0625.tistory.com/102 자바 Trie 자료구조 구현 3. 생각 자바로 문제를 풀고, 주로 사용하는 파이썬으로도 Trie 자료구조를 구현 연..

[초기 접근 방법]1. 완전탐색     N * (N-1) * (N-2) / 3! = 200억 2. 이분탐색     2개를 임의로 선정하여 sum, sum과 가까운 k 값 찾기     N * (N-1) * logN = 3억 두 방법 모두 시간초과가 난다.   [생각]투포인터 유형이라고 생각을 했는데, 어떻게 접근하고 구현해야 될 지 몰라 풀이를 참고했다.  1) 용액을 오름차순으로 정렬 2) for i in range(N)     i : 한 개의 점을 고정     i + 1 : 시작점(s)     N : 끝점(e) 3) (i + s + e) 가 최소가 되는 값을 찾기 위해     s와 e를 계속 이분탐색 한다.  최근에 들었던 생각이 알고리즘 자체가무언가 다익스트라와 같은 최단경로 알고리즘도 그러하고, 수..

[초기 접근 방법] 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()..