동환아 공부해야지

난이도: 골드4분류: 그래프 이론, 그래프 탐색, 트리, 깊이 우선 탐색 key pointleaf node - leaf node는 불가능. leaf가 하나인 경우도 존재하고, parent - child의 거리가 더 먼 경우도 충분히 존재한다트리의 지름 안에 모든 다른 점들이 위치해있다. 따라서 어떤 점에서 탐색하든 상관없이 가장 멀리있는 정점을 고른다면, 그 점은 트리 지름 노드 중 하나이다그리고 트리 지름 노드에서 가장 먼 정점은, 또 다른 트리 지름 노드가 된다 fst approach (x)우선순위 큐를 사용cost가 높은 순서대로 차례대로 꺼냈을 때, 가장 먼저 나오는 두 개의 leaf node를 연결한 비용이 트리의 지름이다>>> fail, cost가 가장 높더라도 정답이 아닌 경우가 충분히 존재..

난이도: 실버2분류: 구현, 문자열 key point  - 비슷한 단어일 조건은, '한 단어를 바꿨을 때 같은 구성인 경우'와 '한 단어만을 추가하거나 제거했을 때 같은 구성인 경우' 이다  - 두 문자열을 비교했을 때, 한쪽 구성에서 없는 문자의 수를 diff라고 정의 한다면, 양 쪽 둘 다 diff 인 경우다   fst approach (o)- list에서 in이나 remove를 사용하면 시간이 오래 걸릴까봐 dict를 사용- 코드 길어짐from collections import defaultdictfrom sys import stdininput = stdin.readlinedef check(w: str): d = defaultdict(int) for s in w: d[s] +..

'''Goals- 다음 달에 선물을 가장 많이 받을 친구가 받을 선물의 수Conditions- A,B 중 다음달 누가 선물을 받는가? - 선물 주고받은 수가 다른 경우 - 둘 중, 덜 받은 사람이 다음달에 하나를 받음 - 선물 주고받은 수가 같거나 없는 경우 * 선물지수: (이번달까지) 선물 보낸 수 - 선물 받은 수 - 선물 지수가 더 큰 사람이 선물을 받음 - 선물 지수가 같다면 서로 주고받지 않음Approach- 구현- 필요 - A,B 선물을 '준' 횟수를 기록한 dict - 선물 지수 계산 - 다음달 받을 선물 개수 계산'''from collections import defaultdictdef calc_give_count..

- 처음부터 greedy나 dfs로 접근했으면 더 쉬웠을 것 같은 문제 - bfs로 접근하려면, 항상 최단거리로 이동한다는 가정을 가지고 적절하게 return과 break를 걸어줘야 TLE가 발생하지 않는다 ''' condition - TL : ? - 2

Condition TL : 2s 1 max_idx: nl, nh = pillar_list[i-1] if standard >= nh: area += (cl-nl) *standard else: area += (cl-nl) *standard standard = nh i -=1 cl = pillar_list[i][0] # 가장 높은 기둥 더하기 area += pillar_list[max_idx][1] # 정답 return return area print(solution(*input_data()))

알고리즘 분류 : 연결 리스트, 스택 시간복잡도 : O(N) 시간복잡도 NlogN까지 가능 단순 구현을 하면 insert, del에서 O(N)이 쓰이기 때문에 TLE가 발생한다 insert, del에서 시간복잡도를 줄이기 위해 deque의 popleft, appendleft를 사용한다 또한 popleft와 appendleft를 사용하기 위해서, cursor를 기준으로 String을 좌측과 우측으로 분리한다 실패 1. 구현 - TLE, insert와 del을 처리할 방법이 필요 2. 구현 - insert와 del이 O(1)인 deque를 사용 - TLE, deque는 이중 연결리스트로, 중간값에 대해서는 접근이 느리기 때문에 항상 O(1)이 아님성공 3. 구현 - reference : https://vel..

알고리즘 분류 : 스택 시간복잡도 : O(N) 접근 계산이 끝난 경우(덧셈하는 경우)와 계속하는 경우(곱하는 경우)로 나누어서 접근해야한다 예시) 입력값 : ( ( ) [ [ ] ] ) ( [ ] ) 원래 계산 : (2+3*3)*2 + (2*3) 바꾼 계산 : (2*2) + (2*3*3) + (2*3) 열린 괄호 (,[ 에서 실제 계산이 이루어지고, 닫힌 괄호 ),] 에서 올바른 경우의 판단을 진행한다 올바른 경우의 판단은, stack[-1]이 아니라 string[cur_index-1]로 판단해야한다 stack[-1]로 판단하면 계산이 중복된다 from sys import stdin input = stdin.readline def solution(string): result = 0 cur_calc = 1..

알고리즘 분류 : 구현, 자료 구조, 문자열, 스택 시간 복잡도 : ... Try_1) Success ''' Condition - TL : 1s (약 2000만번 연산) - ML : 512mb (약 128 * 100만개의 데이터) - 1' 만나면 '>' 대입하고 태그 끝냄 #공백인 경우 elif s == ' ': result += reversed(temp) result.append(' ') temp=[] else: temp.append(s) idx +=1 if temp: result += reversed(temp) return ''.join(result) # type: ignore #input&set data string=list(input().strip()) #main() print(solution(s..

알고리즘 분류 : 정렬, 투포인터 시간 복잡도 : 정렬 - O(NlogN), 투포인터 - . Try_1) Success 정렬 함수를 사용하여 접근했다 Try_2) Success 투 포인터를 사용하여 접근했다 ''' Condition - TL : 1.5s (약 3000만) - ML : 256mb (약 64*10만) - 1

알고리즘 분류 : 투포인터, 누적합, 슬라이딩윈도우 시간 복잡도 : O(N-K) Try_1) Fail sum 함수를 사용하여 temp_sum을 구현 sum은 O(N)이라서 TLE 발생 Try_2) Success temp_sum을 list indexing으로 접근 list indexing은 O(1)이라서 통과 """ Condition - TL : 1s (대략 2000만) - ML : 128mb (대략 32*10만) - 2 N=70만,K=30만일때 > 40만 * 30만 = TLE 발생 2. temp_sum = temp_sum - temperatur[p1-1] + temperature[p2]라 하면 for문 = O(N-K) temp_sum = O(1) >>> O(N-K) >>> N=70만,K=30만일때 > 4..