합니다, 개발공부📝 합니다, 개발공부📝

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 문제의 유형은 그래프 탐색을 이용하여 연결된 부분을 탐색하는 우선탐색의 문제이다. 문제의 조건은 다음과 같다. 1) 상하좌우로 인접한 두 나라의 인구차가 L보다 크거나 같고 R보다 작거나 같으면 국경선이 열린다. 2) 조건에 해당하여 국경선이 열린 모든 나라를 연합이라고 한다. 3) 국경선이 열리면 인구이동에 의해 연합 각국의 인구수는 연합국의 인구수 총합 // 연합국의 수 가 된다..

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제는 조건에 맞는 모든 경우의 수를 확인하고 최적의 값을 찾아내는 완전탐색 및 백트래킹 문제이다. 문제의 조건은 다음과 같다. 1) 가게(r1, c1)와 집(r2, c2)과의 거리는 |r1-r2| + |c1-c2|이다. 2) 최대 m개의 치킨 가게를 둘 수 있다. 3) 각각의 집에서 치킨 가게의 거리의 합이 가장 작을 때의 값을 구하라. 최대 m개의 치킨 가게를 둘 수 있을..

https://www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 문제의 조건에 따라 구현하는 시뮬레이션 문제이다. 조건을 확인하면 다음과 같다. 1) 행의 갯수가 열의 갯수보다 많거나 같으면 R연산을 시행하고 그렇지 않으면 C연산을 실행한다. 2) 연산은 행 및 열의 원소와 원소의 갯수를 나타내고 가장 긴 행이나 열보다 작으면 0으로 채워주는 것을 말한다. 3) 만약 행이나 열이 100보다 크면 100 이상의 열이나 행은 자른다. 4) 한번의 연산..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 무게가 제한된 가방에 넣을 수 있는 물건들의 최대 가치를 찾는 문제이다. 냅색(Knapsack) 알고리즘으로 유명한 문제다. global n, k, product, isUsed n, k = map(int, input().split()) product = [] dp = [0] * (k+1) for _ in range(n): w, v ..

https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 가장 긴 바이토닉 수열이란 a1 reversed_numbers[j]: dp2[i] = max(dp2[i], dp2[j]+1) result = [(dp1[i]+dp2[n-1-i]-1) for i in range(n)] print(max(result)) ( 풀이에 참고한 사이트 ) https://seohyun0120.tistory.com/entry/%EB%B0%B1%EC%A4%80-11054-%EA%B0%80%EC%9E..

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 최단경로를 구하는 다익스트라 알고리즘의 기본 문제 이다. 첫번째로 우선순위 큐를 이용해서 문제를 해결했다. 여기서 주의할 점은 파이썬의 경우 sys를 이용한 입력이 아닌 경우에 시간초과가 발생했다. from queue import PriorityQueue import sys inf = 100000000 v, e = map(int, sys.stdin.readli..

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 이전에 푼 토마토 문제에서 방향만 z방향으로 더 추가된 문제이다. https://dodop-blog.tistory.com/364 백준 7576) 토마토 (골드.5) https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제의 조건을 확인하면 다음과 같다. 썩은 토마토부터 시작해서 전체를 다 탐색할 때까지 걸리는 시간을 구하는 BFS문제다. 1) 썩은 토마토는 1, 썩지 않은 토마토는 0, 토마토가 없는 곳은 -1로 주어진다. 3) 썩은 토마토는 하루가 지나면 인접해있는 앞뒤왼오의 네 방향의 토마토도 썩게 만든다. 2) 토마토가 모두 썩을 수 없으면 -1을 반환 3) 토마토가 모두 썩을 때까지 걸..