본문 바로가기

분류 전체보기

 (147)
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..
알고리즘 유형공부 - 선분교차 알고리즘 외적의 이해외적 (Cross Product) : 두 벡터의 곱을 의미하는 수학적 용어벡터의 곱에 해당하는 외적이라는 개념은 선분교차 알고리즘을 이해하는 데에 필요하다.외적은 두 벡터의 크기와 사잇각의 코사인값을 곱한 값으로 구해진다.특히, 선분교차 알고리즘에서 중요한 값, 또는 나중에 개발을 하게 되는 경우에 중요한 값은 결국 코사인값이다.코사인 값은 -90도에서 90도 사이에서만 양수이다. 즉 어떤 한 벡터가 바라보는 방향을 기준으로 왼쪽 오른쪽에 해당하는 부분 안쪽의 값만 양수가 나온다.다음 그림에서 붉은 색의 벡터와 파란색의 벡터가 기준이 되는 검은 색의 벡터와의 외적을 구한다면 양수와 음수 라는 매우 중요한 차이점을 알 수 있다.세 점의 방향 판단그렇다면 이 성질을 이용하여 세 점이 어떤 방향성을..
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..

티스토리툴바