B/Coding Test (20) 썸네일형 리스트형 BFS/DFS def BFS(graph, start_node): from collections import deque visited = {} queue = deque([]) queue.append(start_node) while queue: node = queue.popleft() visited[node] = True queue.extend(graph[node]) return list(visited.keys()) graph가 list형태로 주어지고 BFS알고리즘으로 방문노드를 뽑아낸다. 특히 방문노드는 딕셔너리나 SET으로 추가해주는 것과, list의 pop(0)보다 deque를 이용하여 popleft를 이용하는것이 시간복잡도 측면에서 이득을 볼 수 있다. visited = [False] * 10 graph = [[].. [프로그래머스] 힙(Heap) 관련 문제 정리 (python 구현) [힙은 곧 우선순위큐다] 힙은 이진트리 기반의 알고리즘으로 특히, 우선순위큐를 구현하는데 힙을 이용하면 쉽게 구현할 수 있다. 현재 많은 기업이 진행하는 코딩테스트에서 우선순위 큐를 구현하는 문제는 출제빈도가 굉장히 높다. 파이썬에서는 heapq, 자바에서도 자주 쓰이던 PriorityQueue를 모듈로 제공해서 이를 이용하면 최소 힙을 간단하게 구현해낼 수 있다. Lv.2 더 맵게 [문제 설명] 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다. 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 .. [프로그래머스] 스킬트리 문제 설명 선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다. 예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다. 위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다. 선행 스킬 순서 skill과 유저들이 만든 스킬트리1를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return 하는 solution 함수를 작성해주세요. 제한 조건 .. [이코테 2021] 그리디 & 구현 알고리즘 문제는 결국 문제해결능력을 물어보는 것이다. 무작정 코딩하려 하지 말고, 주어진 문제의 "상황"을 이해하고, 그 문제를 어떻게 컴퓨터 언어를 통해서 풀어낼 것인가를 곰곰히 생각해보는 것이 중요하다. 이때, 당연히 알고리즘 종류에 대해서 정확히 이해해서 어떻게 적용시킬수 있을까를 생각하는 것과, 적절한 자료구조를 이용해서 풀어내는 것이 중요할 것. 창의적인 풀이도 좋지만 어느정도 정석적인 풀이로 접근하는 것이 좋아보인다 ( 이것이 꼭 코테가 천재들만 할 수 있는 영역이 아닌 이유) [그리디 문제 풀이] 처음에는 아래와 같이 풀었다. def solution(li): key = list(Counter(li).keys()) value = list(Counter(li).values()) cnt = 0 d.. [프로그래머스] 큐/스택 - 프린터 전형적인 큐를 활용하는 문제. 콜렉션에서 deque를 굳이 활용해서 써봤다.. ㅎㅎ def solution(priorities, location): from collections import deque q = deque(priorities) name = deque([i for i in range(len(priorities))]) sheet = [] while len(q)!=0: if q[0] < max(q): q.append(q[0]) q.popleft() name.append(name[0]) name.popleft() else: q.popleft() sheet.append(name[0]) name.popleft() for num, loca in enumerate(sheet): if loca==locat.. [프로그래머스] 큐/스택 - 기능개발 [프로그래머스] 큐/스택 - 주식가격 그리 어려워보이지 않은 문제. 핵심만 파악하면 금방 풀 수 있는 문제인거 같다. 내 풀이는 아래와 같고 . . . range의 첫인자를 안주면 0부터 시작하고, 주면 준 자연수부터 시작한다. 그리고 두번째인자는 보통 포함되지 않고, (두번째인자-첫번째인자) 횟수만큼 반복문이 돈다고 보면 됨. append를 썼으니 last in을 이용했다고 생각함 ! 다른 사람은 이렇게 풀었는데, 나랑 푸는 방법은 거의 같은 풀이다. 미리 answer에 0을 채운 리스트를 만들어주고, 자리마다 카운트를 해주어서 값을 넣는 것이 조금 달랐다. def solution(prices): answer = [0] * len(prices) for i in range(len(prices)): for j in range(i+1, len(.. [프로그래머스] 해시 - 베스트앨범 문제를 풀지 못해서 앓다가 찾아본 풀이 . . . 1시간을 더 줘도 못풀었을것 같다. 가장 첫빠따로 있는 풀이를 공부해보았다. 1. 딕셔너리를 만드는 가장 기초적인 방법 d = {e:[] for e in set(genres)} 딕셔너리를 다음과 같이 만들 수 있었다. set으로 장르를 묶었기 때문에 중복되는 원소가 없는 집합으로 for문이 돌아가면서 key값이 만들어질것이다. 그리고 value는 빈 리스트가 들어가겠고 2. sorted의 parameter인 key를 이용하자. sorted(d, key= lambda x: sum( map(lambda y: y[0],d[x])), reverse = True) 전형적으로 sorted는 알파벳순, 가나다순 정도로 생각했는데, 역시 내장된 파라미터를 통해서 어떻게.. [프로그래머스] 해시 - 위장 문제는 다음과 같고.. 직전 해시관련 문제에서 배운 collection 모듈의 counter 함수를 이용해서 문제를 풀어보았다. 성능과 효율성 모두에서 통과는 받았으나 . . . 저렇게 딕셔너리로 바꾸고 리스트로 바꾸고 밸류값을 자꾸 얻어내는 과정이 약간 비효율적인것 같아 역시 다른 사람들의 풀이를 참고해보았다. 전체적인 플로우는 나와 비슷한것 같지만, functools에 reduce함수를 이용해서 따로 해시개념(dictionary)를 적용하지 않고 바로 리스트 안에서 람다함수를 돌리는 것이 인상적이었다. (이게 훨씬 복잡도도 줄것 같다 ) 또 Counter를 쓸때 저렇게 안에 for문의 인자를 둘로 받아 자유자재로 원하는 변수를 꺼내서 쓰는 것도 . . . 배우자 ! 이전 1 2 3 다음
