분류 전체보기 (380) 썸네일형 리스트형 백준(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문제의 특징은 이미 이전의 값은 구해졌다고 가정하고 시작한다. 그 구해진 값을 통해서 이번값을 어떻게 구하는지만 해결하면 된.. [백준] 9251번 : LCS(Longest Common Subsequence) https://cryosleep.tistory.com/17 LCS란? Longest Common Subsequence=최장 공통 부분순서 그냥 댕쉬움. 문제 풀면서 인지한 동적 프로그래밍, Tabulation의 테이블 작성의 공통점. 정답을 구하기 위해 당장에는 무의미한것까지 맨땅부터 차근차근 다 해보는 것이다(당장에는 무의미하지만 그 무의미한게 답을 구하게 해줌). 두개의 문자열을 비교하는 것이므로 2차원 배열임. x축=문자열A, y축=문자열B 배열은 문자열 각각의 길이에서의 LCS의 길이로 구성됨. 비교되는 2개의 문자열의 타겟 문자가 같으면 dp[i][j]=1+dp[i-1][j-1] 비교되는 2개의 문자열의 타겟 문자가 다르면 dp[i][j]=max(dp[i-1][j], dp[i][j-1] from.. S-algo08 탐욕적(Greedy) 알고리즘 보호되어 있는 글입니다. 이전 1 ··· 42 43 44 45 46 47 48 다음
