본문 바로가기

Algorithm202

BOJ 1644 - 소수의 연속합 문제 백준 온라인 저지 - 1644번 풀이 과정 N 이 주어질 때 연속된 소수의 합으로 N 을 만족시킬 수 있는 경우의 수를 찾는 문제입니다. 특정 수들의 합이 N 이 되기 위해서는 해당 수들이 N 보다 작아야 함은 자명합니다. 따라서 N 보다 작거나 같은 수들 중 모든 소수를 에라토스테네스의 체 를 이용해 먼저 구해놓은 다음 연속된 구간을 찾으면 됩니다. N 의 최대 값이 크기 때문에 O(N^2) 으로 모든 합의 경우의 수를 따지면 시간 초과가 발생합니다. 코드 N = int(input()) def eratos(n): sieve = [1] * (n + 1) for i in range(2, int(n ** 0.5) + 1): if sieve[i]: for j in range(i * 2, n + 1, i).. 2021. 3. 8.
BOJ 18242 - 네모네모 시력검사 문제 백준 온라인 저지 - 18242번 풀이 과정 네모네모 안과의 시력 검사를 통과할 수 있는 기능을 구현하는 문제입니다. 격자에는 단 하나의 직사각형이 존재한다는 보장이 있기 때문에 우리가 활용할 수 있는 첫번째 정보는 왼쪽 상단 모서리의 위치입니다. 이후 오른쪽 상단 모서리와 왼쪽 하단 모서리의 위치를 구해서 직사각형의 너비와 높이를 구하고 이를 활용해 직사각형의 각 변을 검사하면 됩니다. 코드 import sys N, M = list(map(int, sys.stdin.readline().split())) board = [list(sys.stdin.readline().strip()) for _ in range(N)] def get_pivot(board): pivot = None for x in ran.. 2021. 3. 8.
BOJ 9184 - 신나는 함수 실행 문제 백준 온라인 저지 - 9184번 풀이 과정 메모이제이션 으로 재귀 호출을 최적화하는 문제입니다. 문제에서 제시된 함수 구현을 동적 계획법 으로 구현하면 됩니다. 코드 import sys memo = [[[-1] * 51 for _ in range(51)] for _ in range(51)] def func(a, b, c): if a 20: return func(20, 20, 20) if memo[a][b][c] != -1: return memo[a][b][c] if a < b < c: memo[a][b][c] = func(a, b, c - 1) + func(a, b - 1, c - 1) - func(a, b - 1, c) else: memo[a][b][c] = func(a - 1, b, c) + f.. 2021. 3. 8.
BOJ 14226 - 이모티콘 문제 백준 온라인 저지 - 14226번 풀이 과정 수행할 수 있는 연산의 종류가 3가지 일 때, 이모티콘 1개에서 N 개로 만들기 위한 최소 연산의 횟수를 구하는 문제입니다. 현재 상태를 나타내는 변수는 화면에 존재하는 이모티콘의 수 와 클립보드에 있는 이모티콘의 수 이므로 이 두 변수를 상태공산의 매개변수로 정합니다. 주의할 점은 클립보드에 저장된 이모티콘을 화면에 붙여넣기 한다고 클립보드에서 삭제되지는 않는다는 것입니다. 코드 from collections import deque S = int(input()) def bfs(): q = deque() visit = [[0] * (2 * S + 1) for _ in range(2 * S + 1)] q.append([1, 0, 0]) visit[1][0].. 2021. 3. 8.
BOJ 2529 - 부등호 문제 백준 온라인 저지 - 2529번 풀이 과정 부등호 조건을 만족하는 최소 및 최대 수열을 찾는 문제입니다. 백트래킹 을 활용해서 조건을 만족하는 모든 수열을 생성한 다음 최대 및 최소 값을 비교해서 답을 구하면 됩니다. 코드 import sys K = int(input()) signs = list(sys.stdin.readline().split()) min_value = &#39;9999999999&#39; max_value = &#39;0&#39; def compare(pick): global min_value, max_value num = &#39;&#39;.join(map(str, pick)) min_value = min_value if int(min_value) < int(num) else n.. 2021. 3. 8.
BOJ 1802 - 종이 접기 문제 백준 온라인 저지 - 1802번 풀이 과정 규칙에 따라 종이를 접었다가 폈을 때 목표로 하는 상태가 될 수 있는지 판단하는 문제입니다. 종이 접기에 의해 생기는 꺾임 방향에는 규칙이 존재합니다. 우선 중심을 기준으로 반으로 접기 때문에 중심 위치의 꺾임 위치는 중요하지 않습니다. 다만 접히는 중심을 기준으로 좌, 우가 서로 대칭을 이루어야 합니다. 따라서 분할 정복 을 통해 대칭성을 판단해서 답을 구해주면 됩니다. 코드 import sys def check(paper, mid): for i in range(mid): if paper[i] == paper[mid * 2 - i]: return False return True def check_opposite(paper): if len(paper) ==.. 2021. 3. 8.

티스토리툴바