목록개발/알고리즘 (53)

코딩관계론

[프로그래머스] 메뉴리뉴얼(python)

풀이 각 메뉴들을 조합하여 리스트에 저장하고, 각 course 개수의 best like를 구해주면 된다. 코드 from collections import Counter from collections import defaultdict import itertools def solution(orders, course): answer = [] cand_comb_menu = [] for num in course: for order in orders: comb_menues = list(itertools.combinations(order, num)) #AC, AD, AE for comb_menu in comb_menues: comb_menu = sorted(comb_menu) cand_comb_menu.append(..
개발/알고리즘 2022. 10. 9. 19:42
[프로그래머스] 신규 아이디 추천(python)

풀이 연속된 문자열의 깔끔한 처리 코드 "연속된 문자를 복잡하게 처리하는 코드" def get_rule2(id): new_id = "" for i in range(len(id)): if not id[i].isalpha() and not id[i].isdigit(): if not id[i] in ['.', '-', '_']: continue new_id += id[i] return new_id def get_rule3(id): new_id = "" end = -1 for i in range(len(id)): if not id[i].isalpha(): if id[i] == '.': end = i for j in range(i + 1, len(id)): if id[j] != '.': break end = j ..
개발/알고리즘 2022. 10. 3. 18:14
[프로그래머스] 파괴되지 않는 건물(python)

풀이 누적합을 이용해 skill을 O(n2)으로 줄여야 한다. 오랜 시간 동안 고민했던 것은 2차원 배열에서 누적 합을 어떻게 풀어야 할지 고민을 했다. 2차원 누적 합의 공식은 각 row를 먼저 다 누적해서 더한 후 col을 누적해서 더해주면 된다. 초기 배열 -2 0 2 0 0 0 map[2][3]) 2 0 -2 map[3][3] 누적합 배열 -2 -2 (psum[1][2]) 0 (psum[1][3]) -2 -2 (psum[2][2]) 0 ( psum[2][3]) 0 0 0 잘 생각하면 psum[2][3] 을 계산하면 map[2][3] + psum[1][3] + psum[2][2] -psum [1][2]의 경우는 변화량이 한번 제거된다.하지만 map[3][3]의 경우에는 변화량이 두 번 제거가 됨으로..
개발/알고리즘 2022. 10. 3. 01:58
[백준] 태상이의 훈련소 생활

변수 설명 N[] = 모래의 초기 상태 a, b deg = a이상 b이하 deg만큼 모래를 채워라(빼라) 풀이 a~b까지 deg를 누적해서 더해주고 b + 1에서 deg를 소멸시켜주자 누적해서 더해주는 것은 각 인덱스에 무엇을 얼만큼 더해야 하는지 알려주기 때문에 누적하는 것이 굉장히 중요하다. 여기서 문제점은 a ~ b까지 deg를 누적해서 더했다면 n[b + 1] = [b] + b[n + 1]이 된다. n[b + 1]에서는 deg값을 인덱스마다 누적 할 필요가 없는데 어떻게 하면 소멸할 수 있을까를 고민하면 된다. b[n + 1]에 -deg 값을 넣음으로써 해당하는 누적 값을 없앨 수 있다. 풀이 def make_psum(arr): psum = [] psum.append(arr[0]) for i in..
개발/알고리즘 2022. 10. 2. 17:14
[프로그래머스] 양과 늑대 풀이(python)

풀이 "당신은 중간에 양이 늑대에게 잡아먹히지 않도록 하면서..." 가장 중요한 점은 방문 순서가 상관이 없다는 점이다. 왜냐하면 방문한 노드의 양과 늑대를 다 더하고 늑대가 많다면 탐색을 잔행 하지 못하기 때문이다. 다시 루트 노드로 돌아오려 합니다." 노드의 재방문을 고민해보면 양방향 간선을 통해서 해결할 수 있다. 이 부분 때문에 2차원 배열의 메모제이션이 필요하다. dp는 cache[node][방문한 노드들] = 양의 최대 수 코드 from collections import defaultdict nodes = [] edges = [] cache = [] def dfs(node, visited): global nodes, edges sheep = 0 wolf = 0 if cache[node][vis..
개발/알고리즘 2022. 10. 1. 15:28
이전 Prev 1 2 3 4 5 Next 다음