동환아 공부해야지

1. 첫 번째 풀이(success): HashMap 사용import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.HashMap;import java.util.Map;/** * condition * - 성의 첫 글자가 같은 선수 5명을 선발 * * answer * - 가능한 성의 첫 글자를 사전순으로 공백없이 출력 * - 5명보다 적다면 PREDAJA 출력 * * approach * - HashMap 사용 * - 입력받은 이름의 첫 번째 값의 value 증가 * - 모든 입력이 끝난 후 cnt가 5 이상인 값들을 sb에 추가 후 출..

1. 첫 번째 풀이(success): 슬라이딩 윈도우(아님ㅋㅋ;)'''슬라이딩 윈도우로 한번 탐색 때리면 될듯!- 가장 첫 번째 지점부터 탐색하기 위해 물 세는 곳을 정렬- end = stt + l, (lst[-1]+0.5 in visited == True) 가 될 때까지 탐색- 방문할 곳이 연속적이라는 보장이 없으므로 visited는 set으로 처리- (다음 누수지점-0.5, 다음 누수지점, 다음 누수지점+0.5)를 분기처리해서 탐색'''# 입력def input_data(): n,l = map(int,input().split()) lst = list(map(int,input().split())) return n,l,lst# maindef solution(n:int, l:int ,lst:..

1. 첫 번째 풀이(success): DFS'''Condition- A-B-C-D-E 가 되는 node가 있는가?Answer- 존재하면 1, 없으면 0 출력Approach- 모든 node를 root삼아 한번씩 dfs 돌려보면 될 것 같음 - 이때 depth가 5가 된다면 끝'''from sys import stdininput = stdin.readline# 입력n,m = map(int,input().split())graph = [[] for _ in range(n)]for _ in range(m): a,b = map(int,input().split()) graph[a].append(b) graph[b].append(a)# dfsvisited = [False] * ndef dfs(no..

1. 첫 번째 풀이(success): 백트래킹'''Condition- n개중 m개 고름- 중복해서 뽑을 수 있음- 오름차순Answer- 중복값 출력x>>>> 백트래킹으로 풀자'''def dfs(cnt, seq:list, before, lst:list): global visited, answer # 조건 확인 if cnt == m and tuple(seq) not in visited: answer.append(seq[:]) visited.add(tuple(seq)) return # 탐색 for i in range(before, n): num = lst[i] seq.append(num) dfs(cnt+1, ..

1. 첫 번째 풀이(fail): 백트래킹'''이건 백트래킹으로 풀면 될 듯!더 이상 움직일 있는 칸이 없다면 끝인걸로'''def move(i,cr,cc): if i == 0: nr,nc = cr-2, cc+1 elif i == 1: nr,nc = cr-1, cc+2 elif i == 2: nr,nc = cr+1, cc+2 else: nr,nc = cr+2, cc+1 return nr,ncdef dfs(cr,cc,cnt,visited,used): global maxCnt # 탐색 for i in range(4): nr,nc = move(i,cr,cc) if not(0 4: fo..

'''- 부등호를 만족하는 최대, 최소를 출력- 사용되는 숫자는 유니크해야함- 백트래킹으로하자'''def compare(before, cur, sign): return beforecurdef dfs(depth, s): global max_v, min_v, visited # 제일 처음 depth가 k+1이 되었을 때 -> 0부터 오름차순이므로 min이 됨 # 제일 마지막으로 depth가 k+1이 되었을 때 -> max가 됨 if depth == k+1: if len(min_v) == 0: min_v = s else: max_v = s return # 0부터 오름차순으로 탐색 for i in r..

난이도: 골드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