Scribbling

2019 카카오 코딩 테스트 기출 문제라고 한다. 단순 구현문제다. from collections import defaultdict def solution(record): results = [] record_dict = defaultdict(list) nickname_dict = {} for rec in record: rec = rec.split(' ') if rec[0] == 'Enter': user_id, nickname = rec[1], rec[2] results.append(nickname + "님이 들어왔습니다.") record_dict[user_id].append(len(results) - 1) if user_id not in nickname_dict: nickname_dict[user_id]..

난이도가 꽤 높은 그래프 문제이다. 방이 만들어지는 조건을 따져야 한다. * 방이 만들어지는 조건 - 재방문한 점이다. - 타고온 edge는 첫 방문이다. 여기까지는 생각하기 쉬운데, 문제는 아래와 같은 케이스다. 현재 알고리즘은 위의 그림에 대해 방을 1개로 파악한다. 이는 가운데 교차점을 정점으로 생각하지 않기 때문이다. 이 문제를 해결할 방법은 여러가지인데, 가장 간단한 방법은 하나의 화살표에 대해 이동을 2번 반복하는 것이다. def solution(arrows): answer = 0 dx = (0, 1, 1, 1, 0, -1, -1, -1) dy = (-1, -1, 0, 1, 1, 1, 0, -1) vertex = set() vertex.add((0, 0)) edge = set() cur = [..

다익스트라 알고리즘을 사용한다. 참고: https://focalpoint.tistory.com/6 최단 거리 알고리즘 최단 거리 알고리즘을 정리해보자. 1. 다익스트라 알고리즘 - 하나의 node로부터 다른 모든 node까지의 최단거리를 계산 가능 - 음의 간선이 없는 경우에만 유효 - O(VlogV) import heapq def dijkstra(start): pq focalpoint.tistory.com import heapq def solution(n, edge): answer = 0 max_dist = 0 graph = [[] * (n+1) for _ in range(n+1)] for e in edge: u, v = e graph[u].append(v) graph[v].append(u) dista..

개인적으론 매우 어려웠던 문제이다. Binary Search를 이용하라는 힌트가 있음에도 풀지 못하였다. 처음 떠올렸던 방식은 O(N**2)이었는데 N이 너무 커서 안될것 같았다. 이래저래 Binary Search를 적용할 방안을 떠올려보았지만, 끝까지 생각이 나지 않아 구글링을 해따... 아이디어는 매우 간단하다. --> 돌 사이의 간격에 대해 binary search를 하면된다. 효율성은 O(log(D)*N)이므로 최선의 알고리즘이다. def solution(distance, rocks, n): answer = -1 rocks.sort() rocks.append(distance) l, r = 0, distance while l = mid: prev = rock else: num_removed += 1..

Binary Search를 이용한다. 숫자가 클 때는 Binary Search를 의심해봐야한다. def solution(n, times): answer = int(1e20) max_time = n * max(times) l, r = 0, max_time while l = n: answer = min(answer, mid) r = mid - 1 else: l = mid + 1 return answer

그냥...DFS로 푼다... from collections import defaultdict import copy def solution(tickets): tickets.sort() # dictionary["ICN"] = ["ATL", "SFO"] dictionary = defaultdict(list) for ticket in tickets: dictionary[ticket[0]].append(ticket[1]) def dfs(cur, dictionary, edges, path): if not edges: return path for v in dictionary[cur]: next_dictionary = copy.deepcopy(dictionary) next_dictionary[cur].remove(v)..

이와 유사한 문제를 이미 풀어보았다. * for문 안에서 삭제할때는 항상 주의하자. https://focalpoint.tistory.com/101 LeetCode: 126. Word Ladder II - 시바견의 끄적임 개인적으로 어려웠던 문제... A. 내가 푼 방법 일단 내가 푼 방법은 아래와 같다. 1) 모든 word에 대해 graph를 그린다. (word간 글자가 1개만 차이나는 경우 연결) 2) 다익스트라 알고리즘으로 최단 경 focalpoint.tistory.com from collections import deque def solution(begin, target, words): if target not in words: return 0 words = set(words) words.disca..

그래프의 서로소 판별 문제이다. 아래 알고리즘을 그대로 사용한다. https://focalpoint.tistory.com/12 서로소 집합 알고리즘 v, e = map(int, input().split()) edges = [] for _ in range(e): edges.append(list(map(int, input().split()))) parent = [0] * (v+1) for i in range(v+1): parent[i] = i def find_parent(parent, a): if pa.. focalpoint.tistory.com def solution(n, computers): edges = [] for i in range(n): for j in range(i+1, n): if comput..

완전탐색이다. 어떻게 구현하냐가 핵심인데, 모든 숫자를 다 사용한다는 점을 이용하면, O(2**N)으로 풀 수 있다. answer = 0 def solution(numbers, target): global answer dfs(numbers, target) return answer def dfs(numbers, target): if not numbers: if target == 0: global answer answer += 1 return number = numbers[0] dfs(numbers[1:], target-number) dfs(numbers[1:], target+number)

연이은 값을 선택할 수 없는 문제는 전형적인 DP 문제로 많이 접해보았을 것이다. 다만 이 문제는 첫 번째 값과 마지막 값을 동시에 선택할 수 없다는 조건이 추가되어있다. 이에 따라, 첫 번째 값을 선택가능한 case와 마지막 값을 선택 가능한 case로 나누어 그 중 최댓값을 return한다. 1) 0th idx ~ (n-1)th idx 2) 1th idx ~ (n)th idx def solution(money): dp1 = [0] * (len(money) - 1) dp1[0] = money[0] dp1[1] = max(money[0], money[1]) for i in range(2, len(money)-1): dp1[i] = max(dp1[i-2]+money[i], dp1[i-1]) dp2 = [0..