MakerHyeon

동적 계획법 Dynamic Programming - 문제를 쪼개서 작은 문제의 답을 구하고, 그걸로 더 큰 문제의 답을 구하는 걸 반복 - 분할정복과 비슷한 느낌 DP 구현 2가지 ● Top-down : 구현은 재귀, 저장방식은 Memoization ● Bottom-up : 구현은 반복문, 저장방식은 Tabulation 한 번 구한 답들은 저장해두자 Memoization ● 부분 문제들의 답을 한 번 구했으면 또 구하지 않도록 (중복연산 방지) cache에 저장해두고 다음부턴 갖다 쓰자. ● 메모라이제이션이 아니다. 메모이제이션이다. ● 필요한 부분 문제들만 구한다 Lazy-Evaluation ● Top-down 방식에서 사용 쉽게 말하면, 1+1+1+1+1+1+1+1은 뭐냐고물어보고 아이는 7이라고 답..

https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 이중 for문은 N^2 이 되어 통과하지못함! 이분탐색을 이용해야 한다. SOLUTION CODE # PYTHON 풀이 1) 이분탐색 함수 이용 # 입력값 받기 N = int(input()) arr = list(map(int,input().split())) arr.sort() M = int(input()) user_input = list(map(int,input()...

https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 방법이 여러가지 떠올라 고민을 정말 많이 했다. 명료하게 구해야하는것에 집중하자. '배정된 예산들 중 최댓값인 정수를 출력' 해야 한다. 이분탐색을 이용해 정답을 좁혀나간다. 예산이 너무크면 줄이고,너무 작으면 늘린다. (파라메트릭 서치) 예산이 맞는지 확인하는 방법은 다음과 같다. 예산요청값vs예산값 비교 후, 예산요청값이 예산값보다 작으면 전자,크면 후자를 배정한 값을 모두 더한다. 이 ..

파라메트릭 서치 ● 최적화 문제를 결정 문제로 바꿔서 이진탐색으로 푸는 방법 ● 매개변수 Parameter가 주어지면 true or false가 결정되어야 한다. ● 가능한 해의 영역이 연속적이어야 한다. ● 범위를 반씩 줄여가면서 가운데 값이 true 인지 false 인지 구한다. ● 이진탐색과 똑같은 원리 최적화문제 Optimazation Problem - 문제 상황을 만족하는 변수의 최솟값, 최댓값을 구하는 문제 결정 문제 Decision Problem - Yes/No Problem Q(파라메트릭 서치 예시). 큔콴이 대학생들의 외모값과 커플/솔로 여부가 주어진다.커플들은 솔로들보다 외모값이 높다.(^^) 외모값이 최소 몇 이상일 때부터 커플인가?

이진탐색 Binary Search ● 탐색 전에 반드시 정렬되어 있어야 한다. ● 살펴보는 범위를 절반 씩 줄여가면서 답을 찾는다. ● 정렬 O(NlogN) + 이진탐색 O(logN) -> 결과적으로 O(NlogN) ● 미리 정렬되어 들어오면 이진탐색만 하면 되므로 O(logN) ● 한번만 탐색하는 경우,선형탐색 O(N) 이 더 빠를 수도 있다. C++ lower_bound,upper_bound ● lower_bound: 찾으려는 key 값보다 같거나 큰 숫자가(x

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net SOLUTION CODE # PYTHON from collections import deque dy = (0, 1, 0, -1) dx = (1, 0 ,-1, 0) N,M = map(int,input().split()) board = [input() for _ in range(N)] # String으로 받음 def is_valid_coord(y,x): return 0

길찾기문제 방향값을 미리 코드에 짜두고 for문으로 순회하는 기법을 꼭 익혀두자! 방문체크필요 , 각 칸이 노드, 상하좌우 4방향의 간선 # python from collections import deque dy = (0,1,0,-1) dx = (1,0,-1,0) chk = [[False] * 100 for _ in range(100)] N = int(input()) def is_valid_coord(y,x): return 0

https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net SOLUTION CODE # PYTHON import sys sys.setrecursionlimit(10**6) input = sys.stdin.readline # input많을시. N, M = map(int, input().split()) adj = [[0] * N for _ in range(N)] for _ in range(M): ..