목록분류 전체보기 (199)
포도가게의 개발일지
python 백준 1987 알파벳
https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 백준 1987 알파벳 - 첫 풀이(시간초과) import sys r, c = map(int,sys.stdin.readline().split()) matrix = [] for i in range(r): arr=[] temp = sys.stdin.readline().rstrip() for j in temp: arr.append(j) matrix.append(arr) def dfs(start,v..
위상정렬 & 백준 2252 줄세우기
https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 1. 위상정렬 - 정해진 순서에 위반되지 않는 경우의 수를 정렬 - DAG(directed acyclic graph) 형태에서만 사용 가능하다(순환되면 안된다.) - 선행된 조건이 이루어지지 않으면 발생할 수 없음 - 자동차를 만들기 위해 a,b부품이 필요할때 a 부품을 만들려면 또 다른 순서를 이행하여 조립하여야 한다. 때문에 자동차를 만들기 위해서는 ..
python 백준 7569번 토마토
목표 : 이미 익은 숫자 '1'인 토마토가 아직 익지 않은 숫자'0'인 토마토를 모두 익히는데 까지 걸리는 최소시간을 구하시오 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net import sys ## bfs queue 방식을 이용하기 위해 pop(0)보다 빠른 deque -> popleft를 사용 from collections import deque ## 가로 세로 높이 3차원 배열 크기 ## m,n,h = map(int..
1. 저번주에 했던 Z그리기를 응용하여 비교적 간단하게 작성할 수 있었다 - 재귀를 하는 경우 arr를 계속 새로 만들다 보면 메모리 초과나는 경우가 있어 검색 범위를 나누는 쪽으로 접근했다 import sys def recurs(n,w_start,w_end,h_start,h_end): if n < 2: return global zero_count, one_count zero_check = 0 one_check = 0 for i in range(h_start,h_end): for j in range(w_start,w_end): if arr[i][j] == 0: zero_check += 1 if arr[i][j] == 1: one_check += 1 if zero_check == 0 and one_chec..
1. 공유기 설치와 마찬가지로 선형탐색 조건을 먼저 생각해본 후 -> 이진탐색으로 접근 - 특이했던게 양쪽을 좁혀와 경우의 수를 버림으로써 이진탐색이 구현된다는게 신기했음 import sys num = int(input()) arr = [] result = [0,0] min_max = 2000000000 for x in map(int,sys.stdin.readline().split()): arr.append(x) arr.sort() left = 0 right = len(arr)-1 target = 0 while right - left >0: if abs(arr[right] + arr[left]) == target: result[0] = arr[left] result[1] = arr[right] break..
1. 처음에 접근 방식은 공유기를 설치하여 더 넓은쪽으로 이진탐색하여 설치하는 방향으로 했었는데 반례가 무조건 생기며 잘못된 접근이라고 판단하는게 늦어졌다. import sys home_num, wifi = map(int,sys.stdin.readline().split()) home_loca = [] for x in range(home_num): location = int(input()) home_loca.append(location) home_loca.sort() start = home_loca[0] left = 1 end = home_loca[-1]-home_loca[0] maximam = 0 result = 0 while leftmid: answer += (x-mid) if answer >= tar..
1. 이진탐색을 처음에 재귀로 구현하여 풀었는데 어디선가 무한루프에 빠져 while문을 이용하여 이진탐색 import sys def binary(start,end,target): global namu while(end>=start): mid = (start+end)//2 answer = 0 for x in namu_arr: if x>mid: answer += (x-mid) if answer >= target: start = mid + 1 else: end = mid -1 print(end) namu,target = map(int,sys.stdin.readline().split()) namu_arr = list(map(int,sys.stdin.readline().split())) start_h = max(..