HTTP:! HTTP:!

특정 정점까지 가는데 최소 비용을 찾는 알고리즘이다. 실생활에서 네비게이션에서 빠른길 찾기의 개념과 유사하다. 시작점이 주어지고, 특정 정점까지 오는데 가중치를 최소비용으로 계산하면 된다. distances에 각 정점에 도착하는 최소비용을 저장, 나중에 특정 정점을 꺼내오면 된다. distances는 구현하기 나름이긴한데, 정점이 영문이면 dictionary를 사용하고 숫자면 list를 쓰면 된다. 물론 둘다 dictionary를 사용하기도 한다. 그리고 다익스트라는 힙을 사용해서 구현한다. (python에서는 heapq모듈을 사용하는데, 최소 비용으로 자동 정렬되기 때문이다. 처음에 distances(각 정점에 도달하는 비용)은 무한대로 잡아놓고, 출발점만 0으로 잡는다. 이렇게 하는 이유는 얼마가 최..

Bisect python에서 제공하는 패키지 이진 탐색을 쉽게 할 수 있도록 하는 함수 배열에서 특정 값을 찾는 방법은 1) for문을 앞에서부터 돌린다. 2) left, right를 둬서 이분 탐색을 한다. bisect는 2)번을 좀 더 쉽게 할 수 있도록 만들어 놓은 함수이다. 예를 들어서 점수에 따른 등급을 찾는다고 해보자 arr = [60, 70, 80, 90] val = ['F', 'D', 'C', 'B', 'A'] print(bisect.bisect_left(arr, 89),bisect.bisect_right(arr, 89), val[bisect.bisect_right(arr, 89)]) # 3 3 B print(bisect.bisect_left(arr, 79), bisect.bisect_ri..

조합과 collections을 이용하면 풀리는 문제, 처음에는 복잡하게 생각하다가...문제가 이렇게 복잡할수는 없다라고 생각하고 다시 풀어본 문제 python 풀이를 한 사람들은 대부분 combinations과 collections를 사용해서 풀었던것 같다. def solution_kakao_2(orders, course): answer = [] for k in course: candidates = collections.defaultdict(int) for menu_li in orders: for li in list(combinations(menu_li, k)): res = ''.join(sorted(li)) candidates[res] += 1 sorted_candidates = collections...

2021 카카오 코딩테스트 1번 문제 주어진 규칙대로 풀면 되는 문제 정규식 표현을 사용해서 풀어도 되는데, 정규식은 어려우므로 그냥 풀었음 def solution_kakao_1(new_id): answer = '' #허용되는 case - 문자, 숫자, '.', '_', '-' # 1번 규칙 id = new_id.lower() # 2번 규칙 id = "".join([ch for ch in id if ch.isalnum() or ch == '.' or ch == '-' or ch == '_']) # 3번 규칙 for i, value in enumerate(id): if i > 0 and id[i-1] == '.' and id[i] == '.': continue answer += value # 4번 규칙 i..

주어진 배열의 모든 부분 set을 출력하는 문제 dfs를 호출할 때, cur_lst + [num[i]]와 cur_lst.append(nums[i])가 무슨 차이가 있을까? cur_lst + [num[i]] -> 새로운 주소에 list가 만들어지고 cur_lst.append(nums[i]) -> 기존 주소에 nums[i]를 추가한다. 이해가 잘 되지 않아, 저자에게 질문을 했다. def subsets(self, nums: List[int]) -> List[List[int]]: results = [] def dfs(cur_lst, index): results.append(cur_lst) for i in range(index, len(nums)): dfs(cur_lst+[nums[i]], i+1) dfs([]..

재귀 호출 돌리면서 target 값이 되면 result에 저장하면 되는 문제 def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: results = [] def dfs(index, cur, path): if cur < 0: return if cur == 0: results.append(path) return for i in range(index, len(candidates)): dfs(i, cur-candidates[i], path + [candidates[i]]) dfs(0, target, []) return results

dfs-재귀를 이용한 문제, 전화 패드의 숫자를 돌려가면서 출력하는 문제 '2':"abc", '3':"def"가 있고 "23"이면 "ad", "ae", "af"...으로 모두 출력하는 문제 끝 조건에서 결과를 append해주면 된다. 맨처음 dfs의 조건을 어떻게 줘야하나 고민했다. 재귀를 돌리는데, 처음은 뺄수 없어서 0을 줬다. def letterCombinations(self, digits: str) -> List[str]: if not digits: return [] dic = {'2':['a','b','c'], '3':['d','e','f'], '4':['g','h','i'], '5':['j','k','l'], '6':['m','n','o'],'7':['p','q','r', 's'],'8':['..

DFS(재귀)를 이용한 문제 풀이 좌표를 찾아가다가 1을 만나면 연결된 1을 0으로 만들고 상,하,좌,우에 1이 없을때까지 반복 내부함수로 구현했지만, dfs를 함수로 빼도되지만, self와 grid를 넘기기 싫어서 이렇게 구현함 def numIslands(self, grid: List[List[str]]) -> int: def dfs(x:int, y:int)->int: if x = len(grid) or y = len(grid[0]) or grid[x][y] != '1': return 0 grid[x][y] = 0 dfs(x+1, y) dfs(x-1, y) dfs(x, y+1) dfs(x, y-1) return 1 count = 0 for i in range(len(..