본문 바로가기

👨‍💻📱✍️🎢314

BOJ 10819 - 차이를 최대로 문제 백준 온라인 저지 - 10819번 풀이 과정 수열 을 생성해서 모든 가능한 경우의 수들을 만들어보는 완전 탐색 문제입니다. 이후에 문제에서 제시된 수식을 이용해서 값을 계산하고 이 중 최대값을 답으로 반환하면 됩니다. 코드 import sys from itertools import permutations def solution(): max_value = 0 for perm in permutations(numbers): acc = 0 for i in range(N - 1): acc += abs(perm[i] - perm[i + 1]) max_value = max(max_value, acc) return max_value if __name__ == '__main__': N = int(in.. 2021. 3. 18.
BOJ 15240 - Paint bucket 문제 백준 온라인 저지 - 15240번 풀이 과정 pixels 라는 이차원 배열을 생성한 다음, 시작 지점에서 BFS 를 통해 방문을 수행합니다. 이때 방문처리 하기 전에 이전 위치의 픽셀 값을 저장해서 비교하는 것에 유의합니다. 코드 import sys from collections import deque dr = [0, 0, 1, -1] dc = [1, -1, 0, 0] def bfs(r, c, color, pixels): q = deque() visit = [[0] * C for _ in range(R)] q.append([r, c]) visit[r][c] = color while q: r, c = q.popleft() before = pixels[r][c] pixels[r][c] = color f.. 2021. 3. 18.
BOJ 1449 - 수리공 항승 문제 백준 온라인 저지 - 1449번 풀이 과정 테이프를 겹치는 것이 가능하므로 탐욕 알고리즘 을 사용해서 최소 테이프 개수를 구할 수 있습니다. 항상 최대 길이의 테이프를 사용하기 때문에 물이 새는 구간을 오름차순 정렬하면 맨 앞부터 테이프를 붙이면 되는 것입니다. 이때 문제 조건에 입력 값이 정렬되어있다는 언급이 없으므로 따로 정렬시켜주도록 합니다. 코드 import sys N, L = list(map(int, sys.stdin.readline().split())) pipe = list(map(int, sys.stdin.readline().split())) def solution(): fixed = [0] * N ans = 0 # 물 새는 곳 정렬 pipe.sort() for spot in range.. 2021. 3. 18.
BOJ 2805 - 나무 자르기 문제 백준 온라인 저지 - 2805번 풀이 과정 나무꾼이 원하는 벌목량을 만족하는 최적의 톱날 위치를 탐색하는 문제입니다. 단순히 높이를 1씩 증가시킨다면 값의 범위가 매우 넓기 때문에 시간안에 탐색이 불가능합니다. 따라서 이분 탐색을 통해 톱날 위치를 찾아주도록 합니다. 톱날의 위치를 높일 수록 벌목하는 양이 줄어든다는 점을 이용해서 탐색을 수행하면 됩니다. 코드 import sys N, M = list(map(int, sys.stdin.readline().split())) trees = list(map(int, sys.stdin.readline().split())) def possible(saw): temp = 0 for tree in trees: if tree > saw: temp += (tree .. 2021. 3. 18.
BOJ 1654 - 랜선 자르기 문제 백준 온라인 저지 - 1654번 풀이 과정 랜선들을 일정한 크기로 잘랐을 때 원하는 개수를 만족하는 최대 길이를 찾는 문제입니다. 랜선 길이의 상한과 하한을 결정한 뒤 이분 탐색 을 통해 알맞은 길이를 찾을 수 있습니다. 랜선 길이의 상한은 가지고 있는 랜선 중 가장 긴 값이고 하한은 1로 설정해서 문제를 해결하였습니다. 코드 import sys K, N = list(map(int, sys.stdin.readline().split())) lines = [] for _ in range(K): lines.append(int(input())) def enough(cut): ret = 0 for line in lines: ret += line // cut return True if ret >= N else.. 2021. 3. 18.
BOJ 3184 - 양 문제 백준 온라인 저지 - 3184번 풀이 과정 BFS 탐색을 통해 모든 영역을 탐색해준 뒤 늑대의 수와 양의 수를 파악하는 문제입니다. 저는 늑대의 위치에서부터 BFS 탐색을 수행했지만 그냥 아직 방문하지 않은 빈칸에서부터 BFS 탐색을 시작해도 상관없을 것 같습니다. 코드 import sys from collections import deque R, C = list(map(int, sys.stdin.readline().split())) board = [] wolves = [] sheep = [] for r in range(R): line = list(sys.stdin.readline()[:-1]) board.append(line) for c in range(C): if line[c] == 'v.. 2021. 3. 18.

티스토리툴바