간타타 공부장 간타타 공부장

https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 알고리즘 분류 1. 이분탐색 아이디어 1. 최장길이 증가수열을 이분탐색으로 만듬 2. 최장길이 증가수열을 만드는 방법 - 리스트는 점점 증가하는 수로 앞부터 작은 수로부터 정렬하여 채움 - 가장 큰 수보다 더 큰수가 있으면 리스트 뒤에 추가 - 추가하는 수가 리스트의 가장 큰수보다 작으면 리스트에서 적절한 위치에 수를 위치해서 넣어줌 (맨 끝수가 더 작은수로 업데이트를 하는 것이 포인트라고 생각 ..

https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 아이디어 1. list가 크기 때문에 전형적인 이분탐색 문제 2. 포인트는 "가장 인접한 두 공유기 사이의 거리" 이고 이를 코드에서는 mid 변수로 판단한다. (mid기준으로 공유기 설치가 C보다 많으면 이도 정답 후보군이 될 수 있음.) 3. 최댓값을 구하는 것을 지켜야 함 4. 공유기를 sorting 한 다음 탐색을 진행, 가장 첫번째 집에..

https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 아이디어 1. python find 사용시 시간초과 2. 이분탐색으로 시간복잡도 줄여야 통과 if __name__ == '__main__': N = int(input()) cards = list(map(int, input().split(" "))) M = int(input()) find = list(map(int, input().split(" "))) res = []..

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 아이디어 1. M의 숫자가 크기 때문에 O(n)으로 찾으면 시간 오류 2. 이분탐색으로 구현 N, M = list(map(int, str(input()).split(" "))) tree_list = list(map(int, str(input()).split(" "))) low = 0 hight = max(tree_list) answer = 0 def get_..

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,0 www.acmicpc.net 아이디어 1. N, M 숫자가 매우 큼 => 단순히 for문을 돌면 시간 초과 2. 시간 복잡도를 줄여야 하고 O(n)에서 O(logn)으로 줄이기 위해 이분 탐색 알고리즘 사용 N = int(input()) cards = list(map(int, input().split(" "))) M = int(input()) targets = list(map(int, in..

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 visited = [[False for i in range(101)] for j in range(101)] res = 0 def get_dist(point1, point2): return abs(point1[0] - point2[0]) + abs(point1[1] - point2[1]) def dfs(r, c, dist, count): global res if res < dist: return if len(points) == count: re..

- MST(Minimun Spanning Tree)구현 시 사용되는 알고리즘 - 크루스탈 알고리즘 간선을 정렬하여 작은 간선부터 추가 해 주는 방식으로 부분적인 트리를 완성하면서 나중에 하나의 트리로 만드는 과정이라면 프림 알고리즘은 하나의 노드를 시작으로 트리를 형성하는 구조 - 조사가 끝난 노드에 대하여는 조사를 더 하지 않음으로 싸이클이 발생하는 경우는 존재하지 않음 *문제상황 Step1 임의의 한 노드에 대하여 조사를 진행한다.(3번 노드를 선택한다고 가정하였다.) Step2 선택된 간선으로 갈 수 있는 노드에 대하여 그 노드로도 뻗을 수 있는 간선을 고려하여 1) 간선의 가중치가 가장 작고 2) 조사를 하지 않는 노드를 선택하여 계속 조사를 진행한다. -우선순위 큐를 이용하여 구현 - 시간복잡도..

- 다이나믹 프로그래밍을 활용한 최단경로 탐색 알고리즘 - 인공위성 GPS 소프트웨어 등에서 많이 사용이 됨 - 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 찾아줌 - 무방향, 유방향 그래프 두 종류 다 작동을 함 *문제상황 4번 노드에서 6번 노드로 가는 최단 경로를 찾아보자 - 출발 노드를 시작으로 노드를 하나씩 조사를 해 나아가는데 그 기준은 1) 조사를 아직 하지 않은 노드 중에서 2) 가장 최단거리로 갈 수 있는 노드를 조사하게 된다. - 우선순위 큐를 이용하여 조사하는 노드들 중에서(조사하지 않은 노드 중) 현재 가장 최단거리로 갈 수 있는 노드를 조사 Step1 출발점에서 해당 노드까지 갈 수 있는 최단 경로의 가중치를 저장하는 일차원 배열을 생성한다. (result배열) -..