백준 문제풀이 코드저장소 (87) 썸네일형 리스트형 Baekjoon 2482. 색상환 / Python 알고리즘 설명문제 설명주어진 n개의 색상환에서 서로 인접하지 않는 색을 k개 선택해야 한다.코드 설명dp를 2차원 배열로 만든다.dp[i][j] 는 i개의 색상에서 j개의 색을 선택하는 경우의 수를 뜻한다.다음으로 넘어가는 경우 색을 선택하지 않은 경우 dp[i-1][j], 선택한 경우 dp[i-2][j-1]을 이용할 수 있다.dp[i][0] : 0개의 색을 선택하는 경우는 항상 1이고,dp[i][1] : i개의 색에서 1개의 색을 선택하는 경우는 항상 i이다.시간복잡도 : O(n * k)MOD = 1000000003n, k = int(input()), int(input())# k > n // 2인 경우 결과는 항상 0if k > n // 2: print(0) exit(0)# DP 테이블 초기.. Baekjoon 16724. 피리 부는 사나이 / Python 알고리즘 설명문제 설명어느 곳에 있어도, 방향을 따라 이동하면 SAFE ZONE으로 이동할 수 있는 SAFE ZONE의 최소 갯수를 찾는 문제처음엔 모든 지점을 dp로 활용하려고 했으나, union-find 알고리즘을 이용하면 손쉽게 풀린다는 것을 깨달았다.알고리즘 설명모든 칸을 순회하는 방식은 dp풀이와 같지만, 같은 지점으로 모이는 좌표들을 union find 알고리즘을 이용하여 하나의 집합으로 묶는다는 점에서 다르다.dp와 bfs를 이용하여 풀이한다면, 시간복잡도는 O(n * m)으로 같지만, 탐색의 과정에서 bfs는 O(4), union-find는 O(1)로 4배 정도 차이가 난다.from collections import dequedirection = { 'D': [0, 1], # 아래 .. Baekjoon 16236. 아기 상어 / Python 알고리즘 설명문제 설명주어진 크기의 바다에서 아기 상어가 먹을수 있는 물고기를 찾고, 그 과정을 반복하여 최대한 오랜 시간동안 먹이를 먹게 해야한다.자신보다 작은 물고기만 먹을 수 있고, 자신과 크기가 같은 물고기는 지나갈 수 있다.먹을 수 있는 물고기가 있으면 먹으러가고, 그 수가 두 마리 이상이라면, 가장 가까운 물고기, 위쪽의 물고기, 왼쪽의 물고기 순으로 물고기를 선택한다.코드 설명가능한 먹이를 찾는다.먹을 수 있는 물고기들을 거리, 위쪽, 왼쪽 기준으로 정렬해서 목표를 찾는다.먹이를 먹으면 상어의 크기를 증가시키고 또한 시간을 누적한다.bfs 호출 시마다 모든 물고기를 확인하므로 시간 복잡도는 O(time * n ^ 2)이고, 공간복잡도는 O(3 * n ^ 2)이다.from collections.. Baekjoon 1005. ACM Craft / Python https://www.acmicpc.net/problem/1005알고리즘 설명문제 설명건물의 개수가 주어지고, 어느 건물이 지어지기 전에 지어져야 하는 건물들의 정보가 주어진다.이를 활용해서 최단 시간 내 목표 건물을 지어야 한다.코드 설명현재 건설할 수 있는 건물 ( 선행건물이 없거나, 이미 지어진 건물)을 큐에 추가한다.큐에서 하나씩 꺼내어 건물을 짓는 과정을 수행한다.이 때, 그 건물이 선행 조건에 해당하는 건물인 경우 목록에서 제거하고, 시간을 최신화 해준다.트리의 노드들을 순서대로 나열하는 위상 정렬방식을 사용하여 간선의 순서가 항상 올바르게 작동할 수 있도록 한다.큐에서의 각 노드 처리, 간선 리스트를 처리하므로 시간 복잡도와 공간복잡도는 모두 O(n + k)가 된다.from collectio.. Baekjoon 1167. 트리의 지름 / Python 두 번의 DFS를 통해 문제를 해결했다.임의의 노드를 정해서 가장 먼 노드로 움직인 후, 그 노드에서 다시 가장 먼 노드를 찾는다.이 길이가 트리의 지름이 된다.import sysinput = sys.stdin.readline# 트리의 정점의 개수v = int(input())tree = [[] for _ in range(v + 1)]# 간선의 정보를 입력받아 트리 구성for _ in range(v): i, *arr = map(int, input().split()) if len(arr) == 1: continue # 간선 정보를 트리에 추가 for j in range(len(arr) // 2): tree[i].append((arr[2 * j], arr[2 * .. Baekjoon 11444. 피보나치 수 6 / Python 일반적인 재귀함수를 통한 피보나치 수열의 구현과는 다른 문제이다. (문제에선 n이 10 ^ 18 이하의 자연수이다.)우선 수학적으로 피보나치 수열을 구현하는 방식을 알고 있어야 한다.F(n + 1) = F(n) + F(n - 1)F(n) = F(n)을 행렬화 하면즉,의 식이 완성된다.이 식을 구하는 과정은 Linear Algebra의 Diagonalization을 찾아보시길 바랍니다.이런 공식을 이분 탐색 알고리즘을 위한 식으로 만들 수 있다.본 풀이는 이 방법을 사용해서 기존 피보나치 재귀함수의 시간복잡도 (O(2 ^ ㅜ))을 O(n)으로 줄이고, 이분 탐색을 통해 이를 다시 O(log n) 으로 줄였다.N = int(input())matrix = [[1, 1], [1, 0]]def mul_matrix.. Baekjoon 12100. 2048 (Easy) / Python https://www.acmicpc.net/problem/12100알고리즘 설명2048 게임의 진행 방식을 최대 5번 시행해서 나오는 수의 최댓값을 찾아낸다.상하좌우의 모든 방향에 대해 움직일 때, 블록의 이동과 블록이 합쳐지는 함수를 만들어내서, 5회 실행한다.함수 실행횟수가 4 ** 5 로 약 1000번 밖에 안된다. 시행횟수가 많아진다면 다른 함수를 고안해야 할 듯..import sysfrom copy import deepcopyinput = sys.stdin.readline# 보드 크기 n n = int(input())# 보드 초기 상태game = [list(map(int, input().split())) for _ in range(n)]res = 0 # 결과값# n이 1인 경우, 유일한 블록 .. Baekjoon 12015. 가장 긴 증가하는 부분 수열 2 / Python https://www.acmicpc.net/problem/12015LIS (Longest Increasing Subsequence) 문제를 이분 탐색을 활용하여 O(n log n) 의 시간복잡도로 구현하는 문제import sysinput = sys.stdin.readlinedef sol(arr, num): l, r = 0, len(arr) - 1 while l = num: r = m - 1 else: l = m + 1 return ldef longest_increasing_subsequence(n, arr): res = [] for i in arr: pos = sol(res, i) if pos == l.. Baekjoon 1525. 퍼즐 / Python 현재의 문자열을 딕셔너리에 저장한다 : {문자열 : 이동횟수}이동횟수가 적은 순으로 bfs문자열이 123456780이 되는 경우 종료from collections import deque# 초기 상태question = ''for _ in range(3): question += ''.join(input().split())# 목표 상태goal = '123456780'# 상태 거리 저장 딕셔너리와 BFS 큐 초기화dic = {question: 0}q = deque([question])# BFS 탐색while q: now = q.popleft() # 목표 상태에 도달한 경우 if now == goal: print(dic[now]) exit(0) #.. Baekjoon 17387. 선분 교차 2 / Python CW (Counter ClockWise) 정의CCW를 사용하여 세 점의 방향성을 다음과 같이 정의할 수 있습니다:점이 시계 방향으로 돌면 음수 값을 가집니다.점이 반시계 방향으로 돌면 양수 값을 가집니다.세 점이 일직선 상에 있으면 0을 가집니다.CCW를 계산하는 수식은 다음과 같습니다: ccw(a,b,c)=(b.x−a.x)⋅(c.y−a.y)−(b.y−a.y)⋅(c.x−a.x)\text{ccw}(a, b, c) = (b.x - a.x) \cdot (c.y - a.y) - (b.y - a.y) \cdot (c.x - a.x)ccw(a,b,c)=(b.x−a.x)⋅(c.y−a.y)−(b.y−a.y)⋅(c.x−a.x)선분 교차 판정두 선분이 교차하는지 판정하는 방법은 다음과 같습니다:선분 (a1, a2)와 (b.. 이전 1 ··· 4 5 6 7 8 9 다음
