본문 바로가기

CodingTest

[Python][백준 1261 번] 알고스팟 # https://www.acmicpc.net/problem/1261 import sys import heapq from collections import Counter , deque sys.setrecursionlimit(100000) dx = [-1,1,0,0] dy = [0,0,-1,1] M,N = map(int,input().split()) mirrors = [list(map(int,input())) for _ in range(N)] dist = [[-1] * M for _ in range(N)] q = deque() dist[0][0] = 0 q.append((0,0,0)) ans = int(1e9) while q : x,y,d = q.popleft() if x == N-1 and y == M .. 더보기
[Python][백준 12869 번] 뮤탈리스크 # https://www.acmicpc.net/problem/12869 ''' 3차원 dynamic 문제 풀이 d[i][j][k] : scv의 체력이 i,j,k 일때 모두 파괴하는 최소 공격횟수 -- 공격할 수 있는 횟수 : 3팩토리얼 = 6가지 ex) d[i][j][k] = d[i-9][j-3][k-1] + 1 [i-9][j-3][k-1] 같은 경우 음수가 되면 모두 0으로 처리해주면서 진행 -- 사실 dp 를 구현할 수 있는 방법은 총 2가지 이다. 1) top - down 2) bottom - up bottom - up 같은 경우 idx 에 직접 접근하는 형식을 띤다 하지만, 여기서는 idx가 중간에 음수가 되는 경우가 매우 많다 예외처리를 해주어야 한다는 것이다 ex) 하나의 idx : i 에 대.. 더보기
[Python][백준 15565 번] 강의실 배정 # https://www.acmicpc.net/problem/15565 # 슬라이딩 윈도우 ''' 라이언 인형이 딱 K개가 되는 구간만 확인해주면 된다 "항상 K개가 되는 것을 확인해야 하므로, 슬라이딩 윈도우를 활용할 수 있는 것이다" 라이언들의 idx들을 구해놓는다 0 4 6 9 K가 3이라면 0 4 6 4 6 9 라는 2개의 set가 존재하게 되며 처음 idx - 마지막 idx + 1 을 해주면 인형이 포함된 전체 인형의 개수가 된다 윈도우의 크기를 K로 유지하면 한칸씩 뒤로 밀어가며 계속 비교해가면 된 ''' N ,K = map(int,input().split()) dolls = list(map(int, sys.stdin.readline().split())) lion = [] # 라이언 위치 저장.. 더보기
[Python][백준 11000번] 강의실 배정 # https://www.acmicpc.net/problem/11000 import itertools from copy import deepcopy import heapq import sys from collections import deque, defaultdict, Counter sys.stdin = open("input.txt", "rt") sys.setrecursionlimit(100000) N = int(input()) classes = [] for _ in range(N): st, ed = map(int, input().split()) classes.append((st, ed)) # 시작 시간 기준 정렬 classes = sorted(classes, key=lambda x: x[0]) # 강의.. 더보기
[Python][백준 21608번] 상어초등학교 # https://www.acmicpc.net/problem/21608 from copy import deepcopy import sys from collections import deque, defaultdict, Counter sys.stdin = open("input.txt", "rt") sys.setrecursionlimit(100000) dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] N = int(input()) sits = [[0]*N for _ in range(N)] def chMostLoves(sits, loves): res = [] maxN = 0 for r in range(N): for c in range(N): if sits[r][c] != 0: continue .. 더보기
[Python][백준 17086번] 아기상어 2 # https://www.acmicpc.net/problem/17086 # 첫번째 혼자 풀이 ---- ''' 모든 아기 상어를 조사 - 각 아기상어 에서의 거리를 조사하면 되는 것이 아닌가 ?? - 각 아기상어에서 bfs를 매번 새롭게 실시하면 되는 것이 아닌가 ?? ''' import sys import heapq import math from collections import deque sys.stdin = open("input.txt", "rt") sys.setrecursionlimit(1001*1001) # 8 방향 dx = [-1, 1, 0, 0, -1, -1, 1, 1] dy = [0, 0, 1, -1, -1, 1, -1, 1] n, m = map(int, input().split()) # n.. 더보기
[Python][백준 17140번] 이차원배열과 연산 # https://www.acmicpc.net/problem/17140 import sys from collections import defaultdict n = 3 m = 3 a = [[0] * 100 for _ in range(100)] r, c, k = map(int, input().split()) r -= 1 c -= 1 for i in range(n): temp = list(map(int, input().split())) for j in range(m): a[i][j] = temp[j] if a[r][c] == k: print(0) sys.exit(0) for t in range(1, 101): if n >= m: mm = m for i in range(n): d = defaultdict(int.. 더보기
[Python][백준 2688번] 줄어들지 않아 # https://www.acmicpc.net/problem/2688 # dfs 버전 ------------------------------------ import sys import heapq import math import copy from collections import deque, defaultdict sys.stdin = open("input.txt", "rt") sys.setrecursionlimit(100000) def go(L, idx, tmp): global res # brute force로 하게 되면, 10^64 가 되버린다 if L == n: res += 1 ans.append(''.join(map(str, tmp))) return else: for i in range(idx, 1.. 더보기

티스토리툴바