알고리즘 (60) 썸네일형 리스트형 School algo09 탐욕적(Greedy) 알고리즘2. # 크루스칼 #union-find 서로소인 집합을 찾는 집합 자료구조 알고리즘 A. 가중치 무방향 그래프에서 최소신장트리 구하기 Sol1) 우선순위 큐를 이용한 Prim 알고리즘(인접리스트 이용) //원본!!!!!! 좀 더 실용적인 코드는 아래에! //인접 행렬=방향, 밀집, (무방향도 인접행렬로 표현하는 것이 빈번) //인접 리스트=무방향, 희소 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.Comparator; import java.util.List; import java.util.PriorityQueue; .. 백준(BOJ) 9095 : 1, 2, 3 더하기 (countSum과 같은 문제) https://www.acmicpc.net/problem/9095 countSum문제: https://judge.koreatech.ac.kr/problem.php?id=1207 countSum과 같은 문제로 동전1, 동전2 문제와 역시 비교해서 알아두자! ( 동전1 https://flexyduck.tistory.com/92 https://www.acmicpc.net/problem/2293 동전2 https://flexyduck.tistory.com/116 https://www.acmicpc.net/problem/2294 ) 1,2,3 더하기 문제 =countSum 과 유사한 문제이다. 구성이 같고 순서가 다른 것을 다른 것으로 취급한다. for coin in coins: for i in range(coi.. 백준(BOJ) 1260 : DFS와 BFS (그래프 탐색 쌩기초) https://www.acmicpc.net/problem/1260 기본적으로 dfs, bfs를 구현할 수 있는 지 문제이다. 상징성 있는 문제로 구실을 갖추기 위해 넣어 놓는다. from sys import stdin from collections import defaultdict from collections import deque def dfs(graph, visited, start): if(start not in visited): visited.add(start) print(start, end=' ') for v in range(len(graph)): if(graph[start][v]==1): dfs(graph, visited, v) def bfs(graph, start): que=deque([st.. 백준(BOJ) 1654번 랜선자르기, 2805번 나무자르기(다시해야함) https://www.acmicpc.net/problem/1654 처음에는 최소값을 주워진 k개의 랜선중 가장 짧은 랜선을 최솟값으로 해야 겠다고 생각함 ==>> 가장 짧은 랜선을 반드시 포함시키지 않아도 됨. n개만 만들수 있으면 되므로. ==>> 초기값을 가장짧은 1과 가장 길이가 긴 랜선의 중간값으로 두어보자! from sys import stdin def solution(arr, n): mini=1 maxi=max(arr) while(mini=n): mini=evr+1 else: maxi=evr-1 return maxi def main(): k, n=map(int,stdin.readline().split()) arr=list() for _ in range(k): arr.append(int(stdi.. 백준(BOJ) 16918번 봄버맨 처음에 문제를 이해하고 가장 걱정스러웠던게 매 초를 어떻게 표현해 주는냐 였다. ==>> 의외로 간단했다. 그냥 반복문을 한번돌면 그것을 1초라고 여기면 되는 것이었다. 실제로 연산에 걸리는 시간이 얼마건 그냥 이렇게 표현해 주면 되는 것이다. 문제에 오류가 있는 거 같다. '1초가 지난 후에 3초 전에 설치된 폭탄이 모두 폭발한다.' 를 '1초가 지난 후에 2초 전에 설치한 폭탄이 모두 폭발한다' 로 바꾸어야 할것같다. https://www.acmicpc.net/problem/16918 16918번: 봄버맨 첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다. www.acmicpc.. School algo10 동적프로그래밍(1) 보호되어 있는 글입니다. [백준] 2293 동전1 https://www.acmicpc.net/problem/2293 아래 내용 이해한다면 모두 이해한 것임. 구성이 같더라도 순서가 다른것을 모두 다르게 취급하는 경우 (countSum문제) ==>>dp for문에서 아이템의 항목들을 내부반복문으로 사용 구성이 같더라도 순서가 다른것을 모두 같게 취급하는 경우(일반적이지 않은 경우로 직관적으로 이해되진 않음) (동전1 문제) ==>>dp for문에서 아이템의 항목들을 외부반복문으로 사용(아이템의 항목들이 외부반복문으로 사용되므로 2차원 테이블로는 만들수 없음. 다만 이해를 돕기 위해 2차원 테이블을 그림) dp[j]+=dp[j-i] 의 의미: dp[j] => 새로운 수를 사용하지 않은 이전의 수만 사용한 기존의 경우. dp[j-i] =>새로운수와 기존의 수.. [백준] 11066번: 파일 합치기 https://www.acmicpc.net/problem/11066 영상강의: https://fastcampus.co.kr/courses/210773/clips/ 영상보다 쉬운 해설: https://guy-who-writes-sourcecode.tistory.com/43 "dp를 어떻게 정의하는가가 상당히 어렵고 이런 문제를 처음접한다면 dp를 절대 구할 수 없습니다. 왜냐하면 이것은 유형이기 때문입니다." ==>>그동안 내가 공부했던 점화식을 구하는데 사용했던 최적의 원리를 적용하기 너무 어렵다(최적해의 부분해가 또다시 그것의 부분문제의 최적해가 된다는 것을 적용하기 힘듬). dp문제의 특징은 이미 이전의 값은 구해졌다고 가정하고 시작한다. 그 구해진 값을 통해서 이번값을 어떻게 구하는지만 해결하면 된.. 이전 1 ··· 3 4 5 6 7 8 다음
