알고리즘
-
알고리즘: 백준 1012번 유기농 배추 (feat. python)알고리즘/백준(BaekJoon) 2021. 1. 7. 18:47
1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net import sys read = sys.stdin.readline case = int(read()) def sol(): global count count = 0 m, n, bae = list(map(int, read().split())) box = [[0 for _ in range(m)] for _ in range(n)] for _ in range(bae): x, y = list(map(int, read().split())) box[y][x] = 1 for i in rang..
-
알고리즘: 백준 1260번 DFS와 BFS (feat.python)알고리즘/백준(BaekJoon) 2021. 1. 7. 17:44
1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net import sys from collections import deque read = sys.stdin.readline n, m, v = list(map(int, read().split())) graph ={} for i in range(n): graph[i+1] = deque() for i in range(m): x, y = deque(map(int, read().split())) graph[x].append(y) grap..
-
알고리즘: 백준 7576번 토마토 (feat.python)알고리즘/백준(BaekJoon) 2021. 1. 6. 11:43
7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net import sys from collections import deque read = sys.stdin.readline x, y = list(map(int, read().split())) box = [] q_y = deque() q_x = deque() for i in range(y): tmp = list(map(int, read().split())) box.append(tmp) count_1 = 0 for i in range(len(box)):..
-
알고리즘: 백준 2606번 바이러스 (feat.python)알고리즘/백준(BaekJoon) 2021. 1. 4. 23:28
2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net import sys read = sys.stdin.readline def bfs(start, dic): queue = [start] while(queue): pop = queue.pop(0) for i in dic[pop]: if i not in visited: visited.append(i) queue.append(i) def dfs(start, dic): for i in dic[start]: if i not in visited: visited.append(i) d..
-
알고리즘: 백준 1015번 수열 정렬 (feat.python)알고리즘/백준(BaekJoon) 2020. 12. 30. 19:35
1015번: 수열 정렬 P[0], P[1], ...., P[N-1]은 0부터 N-1까지(포함)의 수를 한 번씩 포함하고 있는 수열이다. 수열 P를 길이가 N인 배열 A에 적용하면 길이가 N인 배열 B가 된다. 적용하는 방법은 B[P[i]] = A[i]이다. 배열 A가 주 www.acmicpc.net import sys input = sys.stdin.readline n = int(input()) getA = list(map(int, input().split())) listA = list() for i in range(n): listA.append([i, getA[i]]) listA = sorted(listA, key=lambda x:x[1]) for i in range(n): listA[i][1] = i..
-
알고리즘: 백준 1002번 터렛 (feat. python)알고리즘/백준(BaekJoon) 2020. 12. 30. 18:20
1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net import sys input = sys.stdin.readline n = int(input()) for i in range(n): x1, y1, a, x2, y2, b = (map(int, input().split())) dis = ((x1-x2)**2 + (y1-y2)**2)**(1/2) r1 = a if a>b else b r2 = a if a
-
알고리즘: 최적알고리즘(분기한정법)으로 외판원문제(TSP)를 풀 수 있을까?알고리즘 2020. 11. 16. 10:22
이전의 포스팅에서는 동적계획법을 이용하여 20개의 도시에 대한 외판원문제(TSP)를 풀었다. 하지만 40개의 도시에 대한 문제로 확장했을 때, 문제를 푸는데 6년이상 걸리므로 해밀토니안 회로 문제를 푸는 되추적 알고리즘을 이용하여 그저 아무경로나 취하는걸로 만족하게 되었다. 하지만 이 알고리즘은 경로를 효율적으로 찾기는 하겠지만 최적의 여행경로와는 거리가 멀 수 있다. 그래서 이번 포스팅에서는 최적의 값을 찾는데 특화된 분기 한정법을 이용하여 40개의 도시에 대한 최적 여행 경로를 구할 수 있는지 알아본다. 다음은 이 포스팅을 읽기전에 참고하면 좋은 것들이다. 알고리즘: TSP 외판원문제 알고리즘 공부하기(동적 프로그래밍)(feat. c++, 의사코드) < TSP(The Travling Salespers..
-
알고리즘: 분기한정법(Branch-and-bound)을 이용한 0-1 배낭채우기문제 (0-1 knapsack problem) 공부하기!알고리즘 2020. 11. 15. 21:31
이번 포스팅은 분기한정법(branch-and-bound)을 이용한 0-1 배낭채우기 문제에 대해서 알아본다. 이전의 포스팅에서는 동적계획법(Dynamic programming)과 되추적(Backtracking)을 이용한 0-1 배낭채우기에 대해서 알아봤었다. 알고리즘: 배낭채우기(knapsack problem) 공부하기!(0-1 knapsack problem) 탐욕 알고리즘과 동적계획법은 최적화 문제를 푸는 두가지 방법이다. 둘 중 어떤 방법을 사용해도 문제를 풀 수 있다. 단일 출발점 최단경로 문제에서는 동적계획법은 모든 마디를 출발점으로 seungjuitmemo.tistory.com 알고리즘: 되추적(BackTracking)을 이용한 0 - 1 배낭채우기 문제(0- 1 knapsack problem)..