📌문제 출처 백준 단계별 문제풀이 : 최단경로 https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net ❓ 문제 ✍알고리즘 공부 최단 경로 문제는 다음과 같이 주어진 상황에 맞는 알고리즘을 사용한다. - 다익스트라 : 시작점으로 부터 나머지 정점까지 최단거리를 구할 때 - 플로이드 워셜 : 각 정점간 최단경로를 모두 구할 때 - 벨만 포드 : (다익스트라와 같은 경우에서) 음의 가중치가 존재할..
📌문제 출처 백준 단계별 문제풀이 : 최단경로 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net ❓ 문제 📗 풀이 코드 한 노드에서 다른 모든 노드까지의 최단 경로를 구하는 문제이기에 다익스트라 알고리즘으로 해결한다. - 다익스트라 : 시작점으로 부터 나머지 정점까지 최단거리를 구할 때 - 플로이드 워셜 : 각 정점간 최단경로를 구할 때 - 벨만 포드 : (다익스트라와 같은 경우에서) 음수 순환이 존재할 때 ..
📌문제 출처 백준 단계별 문제풀이 : 이분 탐색 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net ❓ 문제 📗 풀이 코드 ''' 각 랜선의 원래 길이를 l, 자를 길이를 c라고 한다면 랜선 개수는 l//c이다. 이들의 합이 n개 이상이 되는 최대의 c를 구해야하므로 1부터 랜선 원래 길이 중 최대값까지를 이분 탐색해가며 c를 찾아내자 ''' input = open(0).readline def solution(): le..
📌문제 출처 백준 단계별 문제풀이 : 스택, 큐, 덱 단계 https://www.acmicpc.net/problem/24511 24511번: queuestack 첫째 줄에 queuestack을 구성하는 자료구조의 개수 $N$이 주어진다. ($1 \leq N \leq 100\,000$) 둘째 줄에 길이 $N$의 수열 $A$가 주어진다. $i$번 자료구조가 큐라면 $A_i = 0$, 스택이라면 $A_i = 1$이다. 셋째 줄 www.acmicpc.net ❓ 문제 📗 풀이 코드 ''' queue는 선입선출, 후입후출이고 / stack은 선입후출, 후입선출이다. queue는 원래있던 숫자가 빠지고 / stack은 삽입된 숫자가 빠진다. 이를 이용해 queue일때는 원래 원소와 삽입한 원소를 바꿔주고, stack..
📌문제 출처 백준 단계별 문제풀이 : 스택, 큐, 덱 단계 https://www.acmicpc.net/problem/2346 2346번: 풍선 터뜨리기 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선 www.acmicpc.net ❓ 문제 📗 풀이 코드 ''' 숫자들을 deque 함수로 stack을 만들어서 rotate 메서드로 회전을 시킨 후 pop을 진행 deque의 rotate는 양수면 반시계방향회전이므로 문제 조건에 따라서는 -를 붙여줘야 양수일 때 인덱스가 커지는 쪽으로 이동한다. 풍선의 종이가 양수라면 : 풍선이 터진 순간 회전할 방향으..
📌문제 출처 백준 단계별 문제풀이 : 스택, 큐, 덱 단계 https://www.acmicpc.net/problem/28279 28279번: 덱 2 첫째 줄에 명령의 수 N이 주어진다. (1 ≤ N ≤ 1,000,000) 둘째 줄부터 N개 줄에 명령이 하나씩 주어진다. 출력을 요구하는 명령은 하나 이상 주어진다. www.acmicpc.net ❓ 문제 📗 풀이 코드 ''' deque를 쓰지 않고 list에서 pop, insert 사용시 시간초과 ''' from collections import deque input = open(0).readline if __name__ == '__main__': stack = deque() for _ in range(int(input())): ord = list(map(i..
📌문제 출처 백준 단계별 문제풀이 : 스택, 큐, 덱 단계 https://www.acmicpc.net/problem/12789 12789번: 도키도키 간식드리미 인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두 www.acmicpc.net ❓ 문제 📗 풀이 코드 ''' 현재 줄을 stack라고 하자. while 문 range(1, 마지막 학생번호) 진행 nums[0]이 i와 같다면 다음 while문 진행 i와 다르고 i==wait_stack[-1] 이라면 wait_stack.pop()하고 다음 while문 진행 둘 다 아니라면 stack.pop(0)값을 대기열 wait_s..
📌문제 출처 백준 단계별 문제풀이 : 스택, 큐, 덱 단계 https://www.acmicpc.net/problem/28278 28278번: 스택 2 첫째 줄에 명령의 수 N이 주어진다. (1 ≤ N ≤ 1,000,000) 둘째 줄부터 N개 줄에 명령이 하나씩 주어진다. 출력을 요구하는 명령은 하나 이상 주어진다. www.acmicpc.net ❓ 문제 📗 풀이 코드 input = open(0).readline if __name__ == '__main__': n = int(input()) stack = [] for _ in range(n): ord = list(map(int,input().split())) if ord[0] == 1: stack.append(ord[1]) elif ord[0] == 2: p..