본문 바로가기

백준 문제풀이 코드저장소

 (99)
Baekjoon 2473. 세 용액 / Python 알고리즘 설명문제 설명서로 다른 세 개의 용액의 값의 합이 0에 가장 가까운 경우를 찾는다.코드 설명용액들을 정렬한다.중간 포인터를 모든 인덱스를 순회하면서, 첫 번째 인덱스와 마지막 인덱스를 이동시키면서 투 포인터 방식으로 값을 찾는다.시간복잡도 : 정렬 O(n log n) + 투포인터 O(n ^ 2)import sysinput = sys.stdin.readlinen = int(input())arr = sorted(list(map(int, input().split())))# 초기값을 무한대로 설정min_sum = float('inf')result = []# i는 첫 번째 용액을 선택하는 인덱스for i in range(n - 2): s, e = i + 1, n - 1 while s ..
Baekjoon 2533. 사회망 서비스 (SNS) / Python 알고리즘 설명문제 설명모든 사람은 얼리 어답터이거나 얼이 어답터와 연결되어 있어야 한다.이 때, 얼리 어답터의 최소 수를 구하는 문제코드 설명dp배열을 활용한다2차원 배열을 사용하며 dp[a][0]은 노드 a 가 얼리어답터가 아닐 때의 얼리 어답터 수, dp[a][1]은 노드 a 가 얼리어답터일 때의 얼리 어답터 수를 나타낸다.시간 복잡도 : O(n ^ 2)from collections import deque as dqimport sysinput = sys.stdin.readlinen = int(input())edges = [tuple(map(int, input().split())) for _ in range(n - 1)]# 인접 리스트 초기화arr = [[] for _ in range(n + 1)]fo..
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..

티스토리툴바