모영이의 블로그

11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 그리디 알고리즘, 다이나믹 프로그래밍 1) dp[i]는 atm[0]부터 atm[i]까지의 합을 저장한다. 2) dp[0]에 atm[0]을 넣어주고 for문을 시작한다. 3) dp의 합을 출력한다. 전체 코드 import sys input = sys.stdin.readline N = int(input()) atm = [0]*N atm = list(map(int, input().split())) atm.sort() dp = [0]*N dp[0] = atm[0] for i in range(1, N)..

11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 그리디 알고리즘 1) 큰 동전부터 사용하기에 동전 배열을 뒤집어준다. 2) K에서 동전을 나눈 몫을 카운트 한다. 3) K에 동전을 나눈 나머지 값을 넣어준다. 전체 코드 N, K = map(int, input().split()) dongjun = [] for _ in range(N): dongjun.append(int(input())) dongjun = reversed(dongjun) count =..

10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 스택은 파이썬의 배열로 구현이 가능하다. 1) 0이면 스택 팝 2) 0이 아니면 스택에 넣기 3) 스택의 합 출력 전체 코드 import sys input = sys.stdin.readline K = int(input()) stack = [] for _ in range(K): a = int(input()) if a == 0: stack.pop() else: stack.append(a) print(sum(stack))

2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 데크를 사용해서 popleft()로 먼저 넣은 값을 빼주는 큐를 구현한다. 1) 큐에 1부터 N까지 순서대로 넣는다. 2) 제일 왼쪽 값을 버리고, 그 다음 값을 뒤에 넣는다. 3) 큐에 값이 1개 남을 때까지 반복한다. 전체코드 import sys import collections input = sys.stdin.readline N = int(input()) queue = collections.deque() for i in range(1, N + 1): que..

2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net DFS, BFS 둘중 아무거나 사용해도 상관 없을 것 같다. 1) 단지 배열 전체 탐색 후 1 발견시 DFS탐색 시작 2) DFS탐색 스택에서 꺼낸 인덱스 값들을 단지 배열에 넣고 조건문 시작 3) 단지 배열이 1이면 0으로 바꿔주고, 카운트, 상하좌우 인덱스 값 배열을 스택에 추가 4) 카운트 값을 result에 저장하고 단지 배열 전체 탐색 끝난 후 정렬 전체 코드 import sys input = sys.stdin.readline N = int(input()..

1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 1) 배추 배열 전체 탐색 후 1을 발견할 시 BFS 탐색 시작 2) BFS 탐색 큐에서 꺼낸 인덱스 값들을 배추 배열에 넣고 조건문 시작 3) 배추 배열이 1이면 큐에 인덱스 값 배열 삽입 전체 코드 import sys import collections input = sys.stdin.readline def bfs(graph: list, root: list): queue = collections.deque([root]) while queue: node = queue.pop..

백준 1753번 def dijkstra(start): distance[start] = 0 heapq.heappush(heap, (0, start)) while heap: print(heap) current_distance, current_node = heapq.heappop(heap) if distance[current_node] < current_distance: continue for d, n in graph[current_node]: next_distance = d + current_distance if next_distance < distance[n]: distance[n] = next_distance heapq.heappush(heap, (next_distance, n))

백준 1260문제 BFS 데크 활용, 양쪽으로 가능 데크 : root에서 출발 -> 제일 왼쪽거 꺼냄(n) -> n이 첫 방문이면 추가(visited) -> n연결된 노드 추가(queue) 데크: [3]에서 출발 -> 3꺼냄 -> 3추가 -> 데크에 [1, 4] 추가 데크: [1, 4] 출발 -> 1꺼냄 -> 1추가 -> 데크에 [2, 3] 추가 데크: [4, 2, 3] 출발 -> 4꺼냄 -> 4추가 -> 데크에 [3, 5] 추가 데크: [2, 3, 3, 5] 출발 -> 2꺼냄 -> 2추가 -> 데크에 [1, 5] 추가 데크: [3, 3, 5, 1, 5] 출발 -> 3꺼냄 -> 3안추가(visited에 있음) -> 아무것도 안함 데크: [3, 5, 1, 5] 출발 -> 3꺼냄 -> 3안추가(visited..