본문 바로가기

Algorithm Problems

 (212)
[백준/Python] 14620번: 꽃길 문제 https://www.acmicpc.net/problem/14620 14620번: 꽃길 2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다. 진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므 www.acmicpc.net 문제 요약 N × N 꽃 밭에 격자 모양의 꽃 3개를 심어야 한다. 꽃은 꽃술 1개와 꽃잎 2개로 이루어져 있다. 화단 밖으로 꽃잎이 나가거나, 서로 다른 꽃잎들이 닿게 될 경우, 꽃은 죽는다. 각 칸은 대여비가 존재하고, 하나의 꽃을 심을 때 5칸의 화단이 필요하다. 세 꽃을 심기 위한 최소 비용을 출력한다. 코드 # 화단 좌표 (x, y)에 꽃을 심을 수 있는지 파악하는 함수 def I..
[백준/Python] 1931번: 회의실 배정 문제 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 요약 N개의 회의 시작시간, 종료시간을 입력 받고, 한 개의 회의실에서 최대로 사용할 수 있는 회의의 최대 개수를 출력한다. + 회의 한번 시작하면 중간에 중단될 수 없다. + 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. + 회의의 시작시간과 끝나는 시간이 같을 수 있다. (시작하자마자 종료) 코드 N = int(input()) # 회의 수 arr = [] # 모든 회의 시간을 입력 받을 배열 cnt = 1 # 회의 개수 for _ in range(N): arr.append(list(m..
[백준/Python] 2468번: 안전 영역 문제 https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 문제 요약 지역의 높이 정보를 가진 크기가 N × N 배열을 입력 받는다. 비의 양에 때라 일정 높이 이하의 모든 지점은 물에 잠긴다. 첫째 줄에 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력한다. + 안전한 영역은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽, 왼쪽으로 인접해 있으며 그 크기가 최대인 영역이다. 코드 from collections import deque def bfs..
[백준/Python] 1260번: DFS와 BFS 문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 요약 N개의 정점과 정점을 잇는 M개의 간선으로 이루어진 그래프를 입력 받고, 그래프를 V번 정점부터 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력한다. + 정점 번호는 1번부터 N까지 존재한다. + 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문한다. 코드 from collections import deque de..
[백준/python] 13023번: ABCDE 문제 https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 문제 요약 N명의 캠프 인원 중 M가지 친구 관계를 입력 받는다. 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하면 1, 없으면 0을 출력한다. - A는 B와 친구다. - B는 C와 친구다. - C는 D와 친구다. - D는 E와 친구다. 코드 def dfs(num, depth): if depth == 5: print(1) exit() for n_num in graph[num]: if check[n_num] == 0: # 아직 탐색하지 않은 친구라면 check[n_num] = ..
[백준/python] 2644번: 촌수계산 문제 https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 문제 요약 n명의 부모 자식들 간 관계를 m개 입력 받고, 서로 다른 두 사람의 촌수를 출력한다. + 기본적으로 부모와 자식 사이를 1촌으로 정의한다. + 사람들은 1, 2, 3, ... 의 연속된 번호로 각각 표시된다. + 각 사람의 부모는 최대 한 명만 주어진다. 코드 from collections import deque def bfs(): queue = deque([..

티스토리툴바