시나위

https://programmers.co.kr/learn/courses/30/lessons/68936?language=python3 코딩테스트 연습 - 쿼드압축 후 개수 세기 [[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]] [4,9] [[1,1,1,1,1,1,1,1],[0,1,1,1,1,1,1,1],[0,0,0,0,1,1,1,1],[0,1,0,0,1,1,1,1],[0,0,0,0,0,0,1,1],[0,0,0,0,0,0,0,1],[0,0,0,0,1,0,0,1],[0,0,0,0,1,1,1,1]] [10,15] programmers.co.kr def solution(arr): # 분할 정복 answer = devideAndConquer(0,0,arr,len(arr)) return an..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net import sys; input = sys.stdin.readline from heapq import heappop, heappush inf = 100000000 # 최대값 (max(N)-1) * max(w) N = int(input()) # 1000 M = int(input()) # 100000 link_list = [list() for _ in range(N ..

https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net import sys; input=sys.stdin.readline N, M = map(int, input().split()) r, c, d = map(int, input().split()) room = [list(map(int, input().split())) for _ in range(N)] clean = [[0 for _ in range(M)] for _ in range(N)] directi..

https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net import sys; input = sys.stdin.readline N = int(input()) # counting sort count = [0] * 8001 total = 0 for i in range(N): num = int(input()) count[num + 4000] += 1 total += num index = 0 mid = 0 mid_chk = False min_val = 0 min_chk = ..

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net import sys from collections import deque def bfs(r, c): visit[r][c] = 1 q = deque() q.append((r, c)) ret = [(r,c)] while q: y, x = q.popleft() for i in range(4): yy = y + dy[i] xx = x + dx[i] # 주어진 나라의 크기를 넘는 경우 if ..

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net import sys; sys.stdin.readline from itertools import combinations N, M = map(int, input().split()) _map = [] house = [] restaurant = [] for i in range(N): tmp = list(map(int, input().split())) _map.append(tmp) f..

https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net N = int(input()) A = list(map(int, input().split())) dp_asc = [0 for _ in range(N)] dp_desc = [0 for _ in range(N)] for i in range(1, N): for j in range(0, i): if A[j] < A[i]: dp_asc[i] = max(dp_asc[i], dp_asc[j] + 1) for i in range(N..

https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. www.acmicpc.net import sys input = sys.stdin.readline def devide(r, c, size): global m1, z, p1 if check(r, c, size): if paper[r][c] == -1: m1 += 1 elif paper[r][c] == 0: z += 1 else: p1 += 1 return # 분할 for i in range(r, r + size, si..

https://programmers.co.kr/learn/courses/30/lessons/17683 코딩테스트 연습 - [3차] 방금그곡 방금그곡 라디오를 자주 듣는 네오는 라디오에서 방금 나왔던 음악이 무슨 음악인지 궁금해질 때가 많다. 그럴 때 네오는 다음 포털의 '방금그곡' 서비스를 이용하곤 한다. 방금그곡에서는 TV, programmers.co.kr def solution(m, musicinfos): answer = '' answer_playtime = 0 for info in musicinfos: # 문자열 파싱 s, e, title, melody = info.split(',') sh, sm = map(int, s.split(':')) sm_total = sh * 60 + sm eh, em =..

https://programmers.co.kr/learn/courses/30/lessons/17684 코딩테스트 연습 - [3차] 압축 TOBEORNOTTOBEORTOBEORNOT [20, 15, 2, 5, 15, 18, 14, 15, 20, 27, 29, 31, 36, 30, 32, 34] programmers.co.kr def solution(msg): answer = [] # 1 사전 초기화 dic = dict(zip(map(chr, range(ord('A'), ord('Z') + 1)), range(1, 27))) msg_index, dic_index = 0, 27 while msg_index < len(msg): # 2 가장 긴 문자열 검색 tmp_ind = 1 while msg_index + ..