알고리즘 (33) 썸네일형 리스트형 [Python] 프로그래머스 - 징검다리 건너기 문제https://school.programmers.co.kr/learn/courses/30/lessons/64062 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이풀이 1 (Sliding Window)def solution(stones, k): import heapq answer = 1e9 l = len(stones) # max heap heap = [] for i in range(k-1): heapq.heappush(heap, (-stones[i],i)) for i in range(k-1,l): heapq.heappush(heap, (.. [Python] 프로그래머스 - 경주로 건설 문제https://school.programmers.co.kr/learn/courses/30/lessons/67259 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이풀이 1BFS 알고리즘을 기반으로 작성하되, 코너와 직선 도로의 경우를 구분하기 위해 방향에 대한 정보(d)를 queue에 추가적으로 넣어 구분.이미 지난 길이라도, 더 적은 비용으로 갱신할 수 있는 경우에 갱신하도록 코드를 구현하였다.def solution(board): from collections import deque d = '' n = len(board) answer = [] q = deque([(0,0.. [Python] 프로그래머스 - 호텔 방 배정 문제https://school.programmers.co.kr/learn/courses/30/lessons/64063 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이나의 풀이(정확도 Max / 효율성 Low)def solution(k, room_number): answer = [] booked = dict() for num in room_number: room = num if booked.get(num,0): # 원하는 방이 있는 경우 room = booked[num] while booked.get(room,0): .. [Python] 프로그래머스 - 섬 연결하기 문제https://school.programmers.co.kr/learn/courses/30/lessons/42861 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이최소 신장 트리 자료구조와 그래프 알고리즘과 관련된 문제이다. 신장 트리(Spanning Tree)란 주어진 그래프에서 최소한의 간선을 사용해 전체 노드를 포함하는 트리를 의미하며,다음과 같은 특징을 갖는다.V개의 노드와 E개의 엣지를 갖는 그래프 G가 주어질 때, 신장 트리는 V-1개의 엣지만을 사용한다사이클이 존재하지 않아야 한다.최소한의 간선을 사용해야 하므로, 사이클이 발생하면 신장 트리가 아니게 된다.주어진 전체 연결 그래프 G에.. [Python] 프로그래머스 - 줄 서는 방법 문제https://school.programmers.co.kr/learn/courses/30/lessons/12936 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이제한 사항으로 인해, 단순히 전체 경우의 수를 모두 구한 뒤에, 그 중에서 k번째 경우를 출력하는 것은 불가능하다. 줄 세우는 방법에 대해 구할 수 있는 방법을 생각해보면, Permutation(순열)을 떠올릴 수 있다.그리고 문제에서 줄을 세우는 방식은 주어진 예시와 같이, 가장 낮은 번호부터 시작해 가능한 경우의 수를 모두 세우고, 그 다음 번호로 넘어가는 방식이다.예시1주어진 예시인 n=3인 경우에가장 먼저 1로부터 시작해 줄을 세우.. [Python] 프로그래머스 - 보석 쇼핑 문제https://school.programmers.co.kr/learn/courses/30/lessons/67258 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr문제에서 요구하는대로 알고리즘을 구현하는 것 자체는 어렵지 않은 문제이지만, 제한 사항(시간/메모리)를 고려해알고리즘을 구현하는 것이 까다로운 유형의 문제이다. 주어진 `gems`의 최대 길이가 100,000이기 때문에 이중 for 문을 사용해 전체 `gems`를 탐색하게 된다면 $O(e^{10})$의 복잡도가 요구되어 시간 초과가 발생할 것이 자명하므로, 탐색 수를 최소화하면서 문제에서 요구하는 바를 수행하는 것이 중요하다풀이풀이 1 (나의.. [Python] 프로그래머스 - 하노이의 탑 문제https://school.programmers.co.kr/learn/courses/30/lessons/12946 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이나의 풀이def solution(n): answer = [] def func(n): # n층의 결과값 만드는 함수 # n-1층 h = len(floor[n-1])//2 # n-1층의 절반 h1 = floor[n-1][:h] h1 = [h1[0][::-1]]+h1[1:] # 첫번째 원소 반전 .. [Python] 프로그래머스 - 불량 사용자 문제https://school.programmers.co.kr/learn/courses/30/lessons/64064# 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이itertools의 permutations를 사용해 banned_id의 개수만큼의 모든 경우의 수를 만들어낸다.(user_id의 길이 제한이 8까지 밖에 안되기 때문에 가능함)생성된 조합에 대해 각 원소가 banned_id의 조건과 일치하는지 여부를 따지고, 모두 해당될 경우에 가능한 경우의 수로 추가한다.combinations가 아닌 permutations를 사용했기 때문에 동일한 결과가 .. 이전 1 2 3 4 5 다음