본문 바로가기
  • 살짝 구운 김 유나

Algorithm64

Baekjoon_16235_나무재테크 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 시간초과 코드 from collections import deque def grow(year, tree): if year == K: cnt = 0 for x, y, old in tree: if old > 0: cnt += 1 print(cnt) return else: tree.sort(key=lambda x : x[2]) dead = [] # 봄 for idx in range(len(tree)): x, y, old = tree[idx] # 나무가 .. 2022. 10. 18.
Baekjoon_1595_북쪽나라의도로 Baekjoon_1595_북쪽나라의도로 1595번: 북쪽나라의 도로 입력은 여러줄에 걸쳐 주어진다. 입력의 각 줄은 세 개의 양의 정수로 구성되어있는데, 각각은 차례대로 서로 다른 두 도시의 번호와 두 도시를 연결하는 도로의 길이를 의미한다. 모든 도로는 www.acmicpc.net 문제 두 도시 사이에 도로를 만드는 일은 매우 비싸다. 때문에 북쪽나라는 특정 도시를 두 번 이상 지나가지 않고서 임의의 두 도시간을 이동하는 경로가 유일하도록 도로가 설계되어 있다. 또한 북쪽나라의 모든 도시는 다른 모든 도시로 이동할 수 있다고 한다. 이때, 거리가 가장 먼 두 도시 사이의 거리를 출력하는 것이 당신의 임무이다. 북쪽나라에는 최대 10,000개의 도시가 있을 수 있고, 도시는 1 부터 숫자로 이름이 매겨져.. 2022. 10. 9.
Baekjoon_16234_인구이동 Baekjoon_16234_인구이동 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 해결방법 인구 이동은 동시에 진행된다 ! -> 인구 이동의 가능성을 확인했지만 인구 이동이 일어나지 않은 경우에는 visited 값을 2로 해주어야 같은날 또 다시 방문하지 않고 다음 날 탐색 해 줄 수 있다. 코드 from collections import deque def bfs(i, j): dq = deque() dq.append((i, j)) visited[i][j] = 1 # 모든 연합 국가를 담을 배열 .. 2022. 10. 8.
서로소 집합(Disjoint-sets) 서로소 집합? : 서로 중복 원소가 없는 집합들. 다시 말해서 교집합이 없는 집합 집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분한다. 상호 배타 집합 표현 - Tree 하나의 집합을 하나의 트리로 표현한다 자식 노드가 부모 노드를 가리키며 루트 노드가 대표자가 된다. 상호 배타 집합에 대한 연산 Make_Set(x) : 유일한 멤버 z를 포함하는 새로운 집합을 생성하는 연산 Find_Set(x) : x를 포함하는 집합을 찾는 연산 Union(x, y) : x, y를 포함하는 두 집합을 통합하는 연산 구현 def make_set(x): p[x] = x def find_set_r(x): # 재귀로 푸는 경우 if x == p[x]: return x return find_set(p[x]) def fi.. 2022. 9. 29.
최단 경로 - Dijkstra 최단 경로 정의 : 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로 하나의 시작 정점에서 끝 정점까지의 최단 경로 1) 다익스트라(dijkstra) 알고리즘 - 음의 가중치를 허용하지 않음 2) 벨만-포드(Bellman-Ford) 알고리즘 - 음의 가중치 허용 모든 정점들에 대한 최단 경로 1) 플로이드-워샬(Floyd-Warshall) 알고리즘 Dijkstra 알고리즘 : 시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식 시작 정점에서 끝 정점까지의 최단 경로에 정점 x가 존재한다. 이때, 최단 경로는 s에서 x까지의 최단 경로와 x에서 t까지의 최단경로로 구성된다 탐욕 기법을 사용한 알고리즘으로 MST의 Prim 알고리즘과 유사.. 2022. 9. 28.
최소 비용 신장트리(MST) - Prim 그래프에서 최소 비용 문제? 1) 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리 2) 두 정점 사이의 최소 비용의 경로 찾기 신장 트리 : n개의 정점으로 무방향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리 -> 사이클 x, 하지만 모든 정점이 연결된 최소 신장 트리 : 무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리 MST를 표현하는 방법 ''' 6 11 0 1 32 0 2 31 0 5 60 0 6 51 1 2 21 2 4 46 2 6 25 3 4 34 3 5 18 4 5 40 4 6 51 ''' # V : 노드의 개수, E : 간선의 개수 V, E = map(int, input().split()) # 인접 행렬 adjM = [[0].. 2022. 9. 28.
이진 검색 Binary Search : 자료의 가운데 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법 -> 키를 찾을 때까지 검색 범위를 반으로 줄여나가면서 순환하므로 보다 빠르게 검색 가능 단, 이진 검색을 하기 위해서는 자료가 정렬되어 있어야 함 검색 과정 1. 자료의 중앙에 있는 원소를 고른다. 2. 중앙 원소의 값과 키 값이 같은 지 비교한다. 3. 키 값이 중앙 원소보다 작으면 자료의 왼쪽 반에 대해서 새롭게 검색을 수행하고, 크다면 오른쪽 반에서 수행한다. 4. 1~3의 과정을 값을 찾을 때까지 반복한다. 구현 1. 반복 구조로 # 반복구조 def binarySearch(S, key): low = 0 high = len(S)-1 while low key: high =.. 2022. 9. 27.
퀵 정렬 퀵 정렬 : 주어진 배열을 두 개로 분할하고, 각각을 정렬한다 병합 정렬과의 차이점 1. 퀵 정렬은 분할 시에 pivot item을 중심으로, 이보다 작은 것은 왼편, 큰 것은 오른편에 위치시킨다. 2. 각 부분 정렬이 끝난 후, 병합 정렬은 병합하는 과정이 필요하나 퀵 정렬은 후처리가 필요하지 않다. 아이디어 - pivot보다 큰 값은 오른쪽, 작은 값들은 왼쪽 집합에 위치하도록 한다. - 피봇을 두 집합의 가운데에 위치시킨다. 구현 def partition(l, r): # 피봇을 A[l]로 설정 pivot = A[l] i, j = l, r # i, j가 교차하면 i, j는 피봇을 기준으로 작은 값과 큰 값들의 경계에 위치 while i 2022. 9. 26.
병합 정렬 병합 정렬 : 여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방식 * 분할 정복 알고리즘 사용 - 자료를 최소 단위의 문제까지 나눈 후에 차례대로 정렬하여 최종 결과를 얻어냄 - top-down 시간 복잡도 >> O(nlogn) 구현 arr = [69, 10, 30, 2, 16, 8, 31, 22] # 병합하는 과정 def merge(llst, rlst): result = [] lp = rp = 0 # 오른쪽, 왼쪽 리스트의 원소를 차례대로 비교하면서 작은 순으로 새로운 배열에 담기 while lp < len(llst) and rp < len(rlst): if llst[lp] < rlst[rp]: result.append(llst[lp]) lp += 1 else: result... 2022. 9. 26.
SWEA_1267_작업순서 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 코드 import sys sys.stdin = open('1267_input.txt', 'r') def bfs(v): Q = [] Q.append(v) visited[v] = 1 res.append(v) while Q : v = Q.pop(0) for t in G[v]: check = 1 for p in P[t]: if not visited[p]: check = 0 break # 앞선 작업을 다 수행한 상황이면 다음 노드로 if check and visited[t] == 0: Q.append(t) visited[t] = 1 res.append(t) for test.. 2022. 9. 25.

티스토리툴바