📁문제 풀이

[Python] 백준 18405 경쟁적 전염 | BFS

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 문제 해결 포인트 - 특정 위치를 중심으로 상하좌우 뻗어가므로 BFS가 적절 - 숫자가 작은 바이러스가 우선되어야 하므로 리스트로 받아 정렬 후 큐로 전환한다! - 큐에 값이 없어질 때까지 꺼내 상하좌우의 각 값이 다시 큐에 넣는 조건에 부합하는지 확인한다. - 큐에서 꺼낸 값의 시간이 S와 같다면 종료 - X-1 행 ..

[Python] 백준 14502 연구소 | BFS

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 해결 포인트 - 0인 값의 모든 위치를 리스트 (blank)에 넣어서 cominations 모듈을 사용해 3개 위치 랜덤 추출(nCr) - 베이스가 되는 기존 정보에 해당 하는 3개의 위치를 1로 설정하고 check 함수 호출 - check 함수 ~ BFS를 위한 큐를 선언하여 값이 2인 위치를 넣는다. ~ 큐에 값을 하나씩 꺼내 해당 하는 위치에서 위, ..

[Python] 프로그래머스 문자열 압축 | 2020 KAKAO BLIND RECRUITMENT

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://school.programmers.co.kr/learn/courses/30/lessons/60057 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 포인트 [Python] 2, 4, 7, 17, 18, 20 실패 해결 방안 다른 분의 풀이를 보고 참고하여 공유합니다 본인은 반복 발생이 1이라도 전부 문자열에 포함하여 이후 '1'을 제거하는 방식으로 진행했습니다. 이는 2자리 이상의 카운드가 발생하면 문제가 됩니다. '10' -> '0' '11' -> '' '12' -> '2' ... ..

[Python] 프로그래머스 무지의 먹방 라이브 | Heap(힙) | 2019 KAKAO BLIND RECRUITMENT

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://school.programmers.co.kr/learn/courses/30/lessons/42891 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 포인트 - 가장 작은 시간이 걸리는 음식 부터 처리한다. (heapq 사용) - 만약 모든 음식의 개수 보다 k가 크다면 모든 음식을 먹고도 시간이 남는 것이므로 -1 반환 - 한번의 로테이션을 위해 필요한 음식 개수는, 0이 아닌 음식의 수이다.(length) - (다음 최소 음식 개수) - (이전에 처리한 음식 개수) = 현재 처리해야..

[Python] 백준 4485 녹색 옷 입은 애가 젤다지? | 다익스트라

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 문제 해결 포인트 - 다익스트라를 이용하여 각 위치별 (0, 0)에서 최소 비용을 계산 - dr, dc : 각 위치에서 아래, 위, 오른쪽, 왼쪽 위치를 방문 하기 위한 방향키 - graph : 각 위치 방문을 위해 필요한 비용 - distance : 각 위치에서 (0, 0)까지 가기위한 최소 비용, 초기는 무한수 작성 코드 imp..

[Python] 백준 1504 특정한 최단 경로 | 다익스트라

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 문제 해결 포인트 - v1 -> v2 순서 또는 v2 -> v1 순서 각각의 거리를 구하여 작은 값을 출력한다. (2번의 다익스트라) - 경로가 없는 경우(결과 값이 INF보다 크거나 같은 경우) -1을 출력 자세한 내용은 코드 주석 참고 작성 코드 import sys import heapq input =..

[Python] 백준 13549 숨바꼭질 3 | 다익스트라

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 작성 코드 import heapq INF = int(1e9) N, K = map(int, input().split()) # 시작 위치, 도착 위치 distance = [INF]*100001 # 100001개의 떨어진 거리 def dijkstra(start): # 다익스트라 distance[start] = 0 # 시작..

[Python] 백준 1916 최소비용 구하기 | 다익스트라 | 시간초과

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 문제 해결 포인트 - 받을 입력이 많으므로 sys.stdin.realine 을 사용한다. (시간 초과 해결) - 전형적인 다익스트라 문제 유형이다 - 우선순위 큐(최소힙)를 사용하여 최소 거리 노드를 선택 - distance : start 노드로부터 각 노드의 거리를 저장 (INF 로 초기화) - graph : 각 ..

[Python] 프로그래머스 가장 먼 노드 | BFS | 다익스트라

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://school.programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 포인트 - BFS와 다익스트라 알고리즘 두 가지 풀이 방식으로 해결 (DFS도 가능하나 python은 DFS 효율이 좋지 못 함) 자세한 설명은 주석 참고 작성 코드 BFS 풀이 from collections import deque def solution(n, edge): que = deque() # BFS를 위한 큐 graph = [[]..