컴공생의 다이어리

백준 2178번 : 미로 탐색 (문제 바로가기) 내 코드 import sys from collections import deque, defaultdict input = sys.stdin.readline def bfs(graph, start, n, m): # graph : 미로 정보 # start : 시작 좌표 d = [(0, 1), (0, -1), (1, 0), (-1, 0)] # 상하좌우 방향 visited = defaultdict(int) # 좌표별 최소 이동 거리 저장 용 queue = deque([start]) visited[start] = 1 while queue: x, y = queue.popleft() # 현재 좌표 if graph[x][y] == 1: # 이동할 수 있는 칸인가? for x..

너비 우선 탐색(BFS, Breadth First Search) BFS는 가까운 노드부터 우선적으로 탐색하는 방식이며 레벨(level) 순서대로 접근한다. BFS는 최단 경로를 찾아준다는 점에서 최단 길이를 보장해야 할 때 많이 사용된다. 큐를 활용해서 구현한다. 장점 노드 수가 적고 깊이가 얕은 해가 존재 할 때 유리 너비를 우선으로 탐색하기 때문에 답이 되는 경로가 여러 개인 경우에도 최단 경로임을 보장 최단 경로가 존재한다면, 어느 한 경로가 무한히 깊어진다 해도 최단 경로를 반드시 찾을 수 있음 단순 검색 속도가 DFS보다 빠름 단점 재귀호출을 사용하는 DFS와 달리 큐를 이용해 다음에 탐색 할 노드들을 저장하기 때문에 노드의 수가 많을 수록 필요없는 노드들까지 저장해야 하기 때문에 더 큰 저장공..

깊이 우선 탐색(DFS, Depth First Search) DFS는 그래프에서 깊은 부분(자식들)을 우선적으로 탐색하는 방식이다. DFS는 스택이나 재귀 함수를 사용해서 구현할 수 있다. 탐색 과정이 한없이 진행되는 것을 막고 싶다면 깊이 제한(depth bound)를 사용해서 한업이 진행되는 탐색을 막을 수 있다. 장점 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적음 최선의 경우, 가장 빠른 알고리즘. 운 좋게 항상 해에 도달하는 올바른 경로를 선택한다면, 깊이 우선 탐색이 최소 실행시간에 해를 찾음 찾으려는 노드가 깊은 단계에 있다면 BFS보다 빠르게 찾을 수 있음 단점 찾은 해가 최단 경로가 된다는 보장이 없음 최악의 경우, 가능한 모든 경로를 탐험하고서야 해를 찾으므로, 해..

[프로그래머스] 주식가격 - 파이썬(Python) from collections import deque def solution(prices): queue = deque(prices) answer = [] while queue: price = queue.popleft() sec = 0 for q in queue: sec += 1 if price > q: break answer.append(sec) return answer https://programmers.co.kr/learn/courses/30/lessons/42584 코딩테스트 연습 - 주식가격 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수..

[프로그래머스] 다리를 지나는 트럭 - 파이썬(Python) def solution(bridge_length, weight, truck_weights): on_bridge = [0] * bridge_length answer = 0 while on_bridge: answer += 1 on_bridge.pop(0) if truck_weights: if sum(on_bridge) + truck_weights[0]

[프로그래머스] 프린터 - 파이썬(Python) def solution(priorities, location): priorities = [(v, idx) for idx, v in enumerate(priorities)] count = 0 while True: if priorities[0][0] == max(priorities)[0]: count += 1 if priorities[0][1] == location: break priorities.pop(0) else: priorities.append(priorities.pop(0)) return count https://programmers.co.kr/learn/courses/30/lessons/42587 코딩테스트 연습 - 프린터 일반적인 프린터는 인쇄 요..

[프로그래머스] 기능개발 - 파이썬(Python) import math def solution(progresses, speeds): answer = [] progress_day = [math.ceil((100 - x) / y) for x, y in zip(progresses, speeds)] count = 0 for i in progress_day: if i > count: answer.append(1) count = i else: answer[-1] += 1 return answer https://programmers.co.kr/learn/courses/30/lessons/42586 코딩테스트 연습 - 기능개발 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비..

[프로그래머스] 베스트앨범 - 파이썬(Python) from collections import defaultdict def solution(genres, plays): answer = [] G = defaultdict(int) detail = defaultdict(list) for idx, [g, p] in enumerate(zip(genres, plays)): G[g] += p detail[g].append((p, idx)) for g, _ in sorted(G.items(), key=lambda x: -x[1]): for _, i in sorted(detail[g], key=lambda x: -x[0])[:2]: answer.append(i) return answer 혹은 from collection..

[프로그래머스] 위장 - 파이썬(Python) from collections import defaultdict def solution(clothes): d = defaultdict(int) for n, t in clothes: d[t] += 1 answer = 1 for i in d.values(): answer *= (i + 1) return answer - 1 특정 종류의 옷을 안입는 경우를 +1로 추가해주고 난 뒤, 맨 마지막에 모두 안입은 경우를 빼줌 https://programmers.co.kr/learn/courses/30/lessons/42578 코딩테스트 연습 - 위장 programmers.co.kr

[프로그래머스] 전화번호 목록 - 파이썬(Python) def solution(phone_book): phone_book.sort() for p1, p2 in zip(phone_book, phone_book[1:]): if p2.startswith(p1): return False return True https://programmers.co.kr/learn/courses/30/lessons/42577 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조 programmers.co.kr