포도가게의 개발일지

https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 1. 문제 - 외부 공기와 2개이상 맞닿은 치즈는 녹는다 - 내부 공기와 맞닿은 치즈는 카운트하지 않는다 - 내부 공기와 외부 공기가 이어지면 그건 외부공기로 친다 2. 접근법 - 처음에는 외부 공기와 내부 공기를 구별을 어떻게 해줄 것인가 모든 영역을 bfs탐색을 해야하나 고민함 - 하지만 0,0은 무조건 외부공기인데 같이 탐색되지 않으면 걔네들은 내부 공기다 - 외부공기를 -1로 ..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 1. 문제 : 아기상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다. 2.접근법 - 너비 우선 탐색하여 먹이 좌표까지의 최소시간을 찾는다 - 어려웠던점 일반적인 너비우선탐색을 하면 먹이가 동시에 먹어짐 - 개선방향 먹을 수 있는 먹이의 위치를 일단 전부 찾고 그중에서 가장 가까운 거리에있는 먹이만 먹는다 - 같은거리일시 맨좌측 맨우측쪽인 먹이가 우선순위 ..

https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 1. 문제 : 영역이 표시되지 않은 직사각형의 개수와 넓이 파악 2.접근법 - 배열의 개수가 곧 넓이 - 재귀 리밋 error로 100*100 = 10000을 설정해주었다 3. Dfs를 이용한 영역 확인 및 넓이 체크 import sys sys.stdin = open('inputs.text') sys.setrecursionlimit(10000) m,n,c = map(int,sy..

https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 문제 : 가수들의 음악 방송 순서 정하기 접근법 1. 피디들의 각자 방송 순서를 정해서 온다 2. 피디들의 방송 순서에 위반되지 않게 방송 순서를 정해야 한다 -> 위상 정렬 3. 위상정렬은 DAG형태일 때 가능하며 순환되는지 체크해줘야 된다. -> 방문 체크나 사라지지 않은 간선(edge)의 개수를 파악하여 확인 4. Dfs(stack) 와 Queue(in_degree)를 이..

https://www.acmicpc.net/problem/2617 2617번: 구슬 찾기 모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 www.acmicpc.net 중점 : 구슬을 무게 순으로 뒀을때 절대 가운데로 올 수 없는 구슬의 개수를 찾는 문제다 접근법 1. 구슬이 5개일때 자신보다 3개이상의 구슬이 본인보다 무겁거나 가볍다면 그 구슬을 절대 가운데에 올 수 없다. 2. bfs나 dfs를 이용하여 본인의 자식노드 or 손자노드가 3개이상이면 절대 중간에 올 수 없다. 3. 구슬을 무거운 순으로 한번 정렬하고 가벼운 순으로 한번 정렬한..

https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 1. DFS를 이용한 빙산 개수찾기 import sys sys.stdin = open('inputs.text') sys.setrecursionlimit(10000) y,x = map(int,sys.stdin.readline().split()) matrix = [] visit_check = [[0] * x for _ in range(y)] for _ in range(y): matrix.appe..

https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 1. 이것을 이제 python으로 bfs를 이용하여 구현하면 이렇다 from collections import deque import sys #sys.stdin = open('inputs.text') n, target = map(int, sys.stdin.readline().split()) check_list = [0 for _ in range(target+1)] #..

https://www.acmicpc.net/problem/2637 2637번: 장난감 조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net import sys from collections import deque ## 문제입력을 조금이라도 편하게 받기 위해 배움 동일폴더가 아니면 경로설정이 필요하다 ## #sys.stdin = open('inputs.text') num = int(sys.stdin.readline()) index = int(sys.stdin.readline()) ## vertex 의 몇개의 ..