ebson

아래 내용은 Udemy 알고리즘 코딩 테스트 입문부터 합격까지 (Feat. 컴공선배 알고리즘캠프) 강의 섹션 7: PART 2. 알고리즘 유형 분석 - 동적계획법 Dynamic Programming 43강 ~ 50강 내용 요약입니다. Chapter 6. 동적 계획법 문제를 쪼개서 작은 문제의 답을 구하고, 그걸로 더 큰 문제의 답을 구하는 것을 반복함 분할 정복과 비슷한 느낌임 # DP 구현 2가지 Top-down : 구현-재귀 저장방식-메모이제이션(Memoization) Bottom-up : 구현-반복문 저장방식-타뷸레이션(Tabulation) # Memoization - 한 번 구한 답들은 저장해두자 부분 문제들의 답을 한 번 구했으면 또 구하지 않도록(중복연산 방지) Cache에 저장해두고 다음부턴..

아래 내용은 Udemy 알고리즘 코딩 테스트 입문부터 합격까지 (Feat. 컴공선배 알고리즘캠프) 강의 섹션 7: PART 2. 알고리즘 유형 분석 - 이분탐색 Binary Search 37강 ~ 42강 내용 요약입니다. 1. 이진 탐색 Binary Search 1.1. 탐색 전에 반드시 정렬되어 있어야 한다. 1.2. 살펴보는 범위를 절반 씩 줄여가면서 답을 찾는다. 1.3. 정렬 O(NlogN) + 이진탐색 O(logN) => 결과적으로 O(NlogN) 1.4. 미리 정렬되어 들어오면 이진탐색만 하면 되므로 O(logN) 1.5.일차원 배열에서 탐색행위가 1회일때는 선형탐색이 유리하지만(O(N) O(NlogN)) 2. b..

아래 내용은 Udemy 알고리즘 코딩 테스트 입문부터 합격까지 (Feat. 컴공선배 알고리즘캠프) 강의 섹션 6: PART 2. 알고리즘 유형 분석 - DFS, BFS, 백트래킹, 32강 ~ 36강 내용 요약입니다. # 예제문제(1) 길찾기 문제 # 보통 위, 아래, 왼, 오 4방향이 많다. # 체스 등 응용 문제도 있다. # 방향값을 미리 코드로 짜두고 for문으로 순회하는 기법을 익혀두자 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

아래 내용은 Udemy 알고리즘 코딩 테스트 입문부터 합격까지 (Feat. 컴공선배 알고리즘캠프) 강의 섹션 6: PART 2. 알고리즘 유형 분석 - DFS, BFS, 백트래킹, 25강 ~ 31강 내용 요약입니다. #DFS, BFS, 백트래킹 1. 그래프(Graph) 1.1. 그래프 실생활 예 - 지도, 네비게이션, 노선도, SNS 관계도, VCS(버전관리 시스템) - 지하철 노선도를 예로, 그래프에서는 각 역을 Vertex(=node)라고 하고 연결선을 edge 라고 한다. - 그리고 Vertex(=node)를 V 또는 N개, edge를 E 또는 M개라고 주로 표현한다. 1.2. 그래프 종류1 - 무방향(양방향) 그래프, 방향 그래프 1.3. 그래프 종류2 - 순환 그래프(Cyclic Graph), ..

아래 코드는 Udemy 알고리즘 코딩 테스트 입문부터 합격까지 (Feat. 컴공선배 알고리즘캠프) 강의 섹션 5: PART 2. 알고리즘 유형 분석 - 탐욕법, 20강 ~ 24강 내용을 요약한 코드입니다. # 탐욕법 # boj/kr 11047 동전 0 # 예제문제(2) N, K = map(int, input().split()) coins = [int(input()) for _ in range(N)] coins.reverse() ans = 0 for coin in coins: ans += K // coin K %= coin print(ans) # 예제문제(3) # boj/kr 1449 수리공 항승 N, L = map(int, input().split()) coord = [False] * 1001 for i..

아래 코드는 Udemy 알고리즘 코딩 테스트 입문부터 합격까지 (Feat. 컴공선배 알고리즘캠프) 강의 섹션 4: PART 2. 알고리즘 유형 분석 - 완전탐색, 15강 ~ 19강 내용을 요약한 코드입니다. # 순열 from itertools import permutations v = [0, 1, 2, 3] for i in permutations(v, 4): print(i) # 조합 from itertools import combinations v = [0, 1, 2, 3] for i in combinations(v, 2): print(i) # 18. Capter 2. 완전 탐색 - 예제문제 (3) -1 # boj.kr/2309 일곱 난쟁이 from itertools import combinations ..

아래 코드는 Udemy 알고리즘 코딩 테스트 입문부터 합격까지 (Feat. 컴공선배 알고리즘캠프) 강의 섹션 3: PART 2. 알고리즘 유형 분석 - 자료구조, 13강 Chapter1. 자료구조 - 예제문제 (4) 내용을 요약한 코드입니다. # 예제문제 (4) # boj.kr/1302 베스트셀러 # 맵 d = dict() for _ in range(int(input())): book = input() if book in d: d[book] += 1 else: d[book] = 1 m = max(d.values()) candi = [] for k, v in d.items(): if v == m: candi.append(k) candi.sort() print(candi[0])

아래 코드는 Udemy 알고리즘 코딩 테스트 입문부터 합격까지 (Feat. 컴공선배 알고리즘캠프) 강의 섹션 3: PART 2. 알고리즘 유형 분석 - 자료구조, 12강 Chapter1. 자료구조 - 예제문제 (3) 내용을 요약한 코드입니다. # 예제문제 (3) # boj.kr/11286 절댓값 힙 # 우선순위 큐 import heapq as hq import sys input = sys.stdin.readline pq = [] for _ in range(int(input())): x = int(input()) if x: hq.heappush(pq, (abs(x), x)) else: print(hq.heappop(pq)[1] if pq else 0) import heapq as hq import sys ..