알고리즘 정복하기! 64

백준 15720번 Python / Greedy 문제 링크 https://www.acmicpc.net/problem/15720 15720번: 카우버거 첫째 줄에는 주문한 버거의 개수 B, 사이드 메뉴의 개수 C, 음료의 개수 D가 공백을 사이에 두고 순서대로 주어진다. (1 ≤ B, C, D ≤ 1,000) 둘째 줄에는 각 버거의 가격이 공백을 사이에 두고 주어진 www.acmicpc.net 풀이 b,c,d = map(int, input().split()) burgers = sorted(list(map(int, input().split())), reverse=True) sidemenus = sorted(list(map(int, input().split())), reverse=True) drinks = sorted(list(map(int,input()... 알고리즘 정복하기!/백준 문제풀이 2022. 1. 30.
백준 11034번 Python / Greedy 문제 링크 https://www.acmicpc.net/problem/11034 11034번: 캥거루 세마리2 여러개의 테스트 케이스로 이루어져 있으며, 세 캥거루의 초기 위치 A, B, C가 주어진다. (0 < A < B < C < 100) www.acmicpc.net 풀이 while True: try: a,b,c = map(int, input().split()) print(max(b-a,c-b)-1) except: break - max() 함수를 사용하는 것이 핵심이다. 알고리즘 정복하기!/백준 문제풀이 2022. 1. 30.
백준 2810번 Python / Greedy 문제 링크 https://www.acmicpc.net/problem/2810 2810번: 컵홀더 첫째 줄에 좌석의 수 N이 주어진다. (1 ≤ N ≤ 50) 둘째 줄에는 좌석의 정보가 주어진다. www.acmicpc.net 풀이 입력한 값에서 'LL'의 수를 카운트해 1개 이하일 때는 모든 사람이 컵을 컵홀더에 놓을 수 있으며, 2개부터는 (전체 사람의 수 - LL 카운팅 수 + 1)만큼의 사람이 컵을 컵홀더에 놓을 수 있다. n = int(input()) SL = input() cnt = SL.count('LL') if cnt 알고리즘 정복하기!/백준 문제풀이 2022. 1. 30.
백준 1052번 Python / Greedy 문제링크 https://www.acmicpc.net/problem/1052 1052번: 물병 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번 www.acmicpc.net 풀이 처음에는 물병의 개수만큼 1의 원소의 배열로 채워서 문제를 해결하려고 했으나 풀지 못했습니다. 계속 생각하던 중에 물병을 합칠수록 1L, 2L, 4L, ... 꼴로 용량이 늘어나는 것을 보고 이진수와 관련이 있지 않을까 생각했습니다. 그 후에도 생각이 잘 떠오르지 않아 구글링을 통해 방법을 찾았습니다. 해결 방식은 다음과 같습니다. N:3 -> [1, 1, 1] -> [2, 1] = 2^.. 알고리즘 정복하기!/백준 문제풀이 2022. 1. 27.
백준 2178번 Python / BFS 너비 우선 탐색(BFS)이란? https://seokii.tistory.com/31 [알고리즘] 너비 우선 탐색 (BFS, Breadth-First Search)이란? 1. 너비 우선 탐색 (BFS, Breadth-First Search) - 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘 - 큐 자료구조를 이용함 장점 - 출발노드에서 목표노드까지의 최단 길이 경로를 보장한다. seokii.tistory.com 너비 우선 탐색 알고리즘 개념에 대한 내용입니다. 문제링크 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서.. 알고리즘 정복하기!/백준 문제풀이 2022. 1. 25.
백준 2667번 Python / DFS 깊이 우선 탐색(DFS)이란? https://seokii.tistory.com/30 [알고리즘] 깊이 우선 탐색 (DFS, Depth-First Search)이란? 깊이 우선 탐색(DFS, Depth-First Search) - 그래프 탐색에서 루트 노드에서 시작해 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 - 재귀 혹은 스택 자료구조를 이용함 장점 - 현 경로 seokii.tistory.com 깊이 우선 탐색 알고리즘 개념에 대한 내용입니다. 문제 링크 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 .. 알고리즘 정복하기!/백준 문제풀이 2022. 1. 25.
[알고리즘] 너비 우선 탐색 (BFS, Breadth-First Search)이란? 너비 우선 탐색 (BFS, Breadth-First Search) - 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘 - 큐 자료구조를 이용함 장점 - 출발노드에서 목표노드까지의 최단 길이 경로를 보장한다. 단점 - 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 하게 된다. - 해가 존재하지 않는다면 유한 그래프(finite graph)의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다. - 무한 그래프(infinite graph)의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못한다. 구현 예시(Python) from collections import deque # BFS 메서드 정의 def bfs(graph, start, visited): # 큐(Q.. 알고리즘 정복하기!/알고리즘 정리 2022. 1. 25.
[알고리즘] 깊이 우선 탐색 (DFS, Depth-First Search)이란? 깊이 우선 탐색(DFS, Depth-First Search) - 그래프 탐색에서 루트 노드에서 시작해 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 - 재귀 혹은 스택 자료구조를 이용함 장점 - 현 경로상의 노드들만 기억하면 되므로 저장공간의 수요가 비교적 적다. - 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다. 단점 - 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고 목표노드를 발견하지 못하면 다음의 경로를 따라 탐색하는 방법이 유용할 수 있다. - 얻어진 해가 최단 경로가 된다는 보장이 없다. 구현 예시(Python) # DFS 메서드 정의 def dfs(graph, v, visited): # 현재 노드를 방문 처리.. 알고리즘 정복하기!/알고리즘 정리 2022. 1. 25.

티스토리툴바