2️⃣ 개발 지식 B+46 🏃[백준/python] DP 유형 모음집 및 접근 컨셉 분할정복 vs 다이나믹 프로그래밍 여러 하위 문제로 나누어 먼저 해결한 뒤, 그 결과들을 이용해 큰 문제를 해결하는 기법 분할정복다이나믹 프로그래밍 (이하 DP)하위 문제중복이 없음중복 있음즉, 단순 분할정복 수행 시 중복된 작업을 수행(해결 방법은 아래 이어서)고려사항 시간 - 메모리 간의 trade-off DP 구현방법TODO 두 방식의 차이점 체감하기 Top DownBottom Up구현 방법재귀, memoizationfor 루프, Tabulation [생각해보기] 시간복잡도 (피보나치 수열 vs 팩토리얼 문제) 피보나치 수열팩토리얼점화식fibo(n) = fibo(n-1) + fibo(n-2)factorial(n) = n*factorial(n-1)시간복잡도[재귀로 구현 시] O(2^n)함수를 계.. 2024. 8. 28. [백준/python] Greedy 유형 모음집 및 접근 컨셉 [알고리즘/python] DP 유형 - 배낭(Knapsack) 문제DP 유형으로 종종 언급되는 배낭 문제 (knapsack) 유형에 대해 알아 봅시다.0 / 1 Knapsack 담거나 담지 않거나코드트리 #Knapsack, 배낭문제 (보석 무게, 가격을 고려한 최대 가치 만들기) 백준 #12865 평범kr-ddubbu.tistory.com 앞서 Fraction Knapsack 문제는 그리디 알고리즘으로 풀 수 있음을 언급했습니다. 어떤 조건 하에 그리디 탐색을 적용할 수 있을지 알아보겠습니다. 정의 및 조건 - 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법- 지역적으로 최적이면서 전역적으로 최적인 문제들에 적용 가능- 혹여 사용하지 못하더라도 근사 알고리즘으로 사용 가능, 최적해.. 2024. 8. 28. [C] 문법 빠르게 훑기 해당 링크를 토대로 주요 문법들을 복습했다. 5년 전 기억을 더듬고 있는데 꽤 기억에 남았다는 사실이 재밌다. 이번 만큼은 그 당시 힘들었던 포인터를 극복하고 RedBlack트리까지 멋있게 구현해보고 싶다. 반복적으로 실수했던 부분1. 모든 변수는 자료형 선언해주기2. printf 변수를 위해서는 자료형 지정 필요함3. 세미콜론(;) 필수4. char s 작은 따옴표로 할당하기 주제별로 학습하기 // C언어#define _CRT_SECURE_NO_WARNINGS #include#includevoid practice_data_type() { /* 모든 자료형 - 형식 지정자 연결 짓기 */ // 정수형 int a = 123; long b = pow(10, 6); printf("a=%d, int자료형 크기:.. 2024. 8. 27. [백준/python] DP 유형 - 배낭(Knapsack) 문제 DP 유형으로 종종 언급되는 배낭 문제 (knapsack) 유형에 대해 알아 봅시다.0 / 1 Knapsack 담거나 담지 않거나코드트리 #Knapsack, 배낭문제 (보석 무게, 가격을 고려한 최대 가치 만들기) 백준 #12865 평범한 배낭 (기본); 시간복잡도 O(N*K)백준 #10844 쉬운 계단 (풀어봐야함)백준 #2629 양팔문제 (응용)2D 배열로 풀기; dp[i][w] = i번째 물건까지 사용해서 w무게를 갖는 최대 가치 import sysreadline = lambda: sys.stdin.readline().strip()# 전처리N, TARGET_WEIGHT = map(int, readline().split())bag = [(0, 0)] # empty itemfor _ in range.. 2024. 8. 26. [백준/python] DP 유형 - LIS & LDS 그리고 LCS 내용은 더 추가될 수 있습니다 LIS (Longest Increasing Subsequence)LDS (Longest Decreasing Subsequence) 조건에 맞게 선택적으로 전진하는 DP최장 감소 부분 수열 (LDS) 백준 #11722 가장 긴 감소하는 부분 수열 (길이)최장 증가 부분 수열 (LIS) 백준 #11053 가장 긴 증가하는 부분 수열 (길이)dp[i] = i번째 원소를 끝으로 하는 LIS 혹은 LDS 길이 Q. 아래 방법은 N^2 아닌가? 매번 탐색해야해서 말야. A. N class Solution: def lengthOfLIS(self, nums: List[int]) -> int: if not nums: return 0 .. 2024. 8. 26. [백준/python] stack 유형 모음집 및 접근 컨셉 사람마다 코딩테스트 학습 방식이 다른 와중에, 필자는 구현단계에서는 감을 잡기 위해 정답 풀이를 보는 것은 공감하나, 응용 문제는 다양하고 결국 아이디어 싸움인 것 같아 접근 컨셉이 중요하다는 생각이 들었다. 유형별 접근 컨셉을 기록하려하고 코드보다는 도식화가 많을 것이다. 코드를 보고 싶은 분은 아래 링크를 참고 부탁한다. - 성공 풀이는 [깃헙] 혹은 백준 (ID = tjsal9335) 로 검색해서 확인 가능- 색칠된 표는 다시 풀어보면 좋을 문제 혹은 진행 중인 문제 FYI. stack 유형 문제들은 백준 > 문제 > 알고리즘 분류 > 스택에서 가져왔다. [링크] #10828 스택 #28278 스택2구현 기본, 기본 메소드를 학습할 수 있음. (append, pop, len) #9012 괄호스택 유.. 2024. 8. 21. [알고리즘/python] 위상정렬 지난 시간 DFS, BFS를 이용해 그래프 탐색하는 방법을 배웠다. 다음 과제인 '위상정렬' 문제를 풀기 전에 그 개념에 대해 공부해보려한다. 위상정렬 (Topological-Sort) 순서가 정해져있는 일련의 작업을 차례대로 수행해야할 때 사용하는 알고리즘 - 조건; dag (Directed Acyclic Graphs, 비순환 방향 그래프) - 모든 방향의 간선이 왼쪽 > 오른쪽 향하며 수평선을 따르는 정점들의 순서- 시간 복잡도 = O(V+E); 모든 노드를 확인(O(V))하면서, 해당 노드에서 출발하는 간선을 차례대로 제거해나감 (O(E))- 해가 여러개일 수 있음 구현 방법 의사코드1. 진입 차수 테이블을 만든다.2. 진입 차수가 0인 정점을 큐에 삽입한다. (이 말은 출발점이 여러개가 될 수 있.. 2024. 8. 19. [자료구조/python] stack, queue 위 책을 토대로 궁금한 점을 추가 리서치 후 기술하였다.스택 LIFO (Last In, First Out) 기존의 리스트 자료구조와 같지 않나 생각이 들었다. 하지만, python에서는 대체로 collections.deque 라이브러리를 이용해 구현했다. 그 이유가 궁금했다. Q. 리스트 vs 배열- 리스트: 적은 요소- 배열: 매우 큰 요소를 저장하거나 수학적 연산이 필요할 경우 arr (배열)list (리스트)선언 필요성OX값 정의array.module, numpy대괄호로 감싸주기만 하면 됨사칙연산쉬움어려움데이터 크기 (자료형?)같아야함X, 리스트 중첩 가능 Q. 리스트 vs 덱 - deque (덱): Double Ended Queue deque (덱) list (리스트) 양방향에서 삽입과 .. 2024. 8. 16. 코테 시간초과 분석 방법 코딩테스트에 관심있다면, 시간 복잡도 Big-O에 대해 한번쯤은 들어봤을 것이다. 필자 또한 리스트 탐색은 O(n), 정렬이 된 경우 이분탐색 시 O(log(n))까지 최적화 가능하다는 것은 학습했다. 하지만 문제를 보고 어쩔 때 최적화가 필요할지 판단이 서지 않았었다. 그냥 시간을 줄일 수록 좋은거 아닌가? 라고 막연히 생각했다. 이때 백준 정렬 1~3 문제 간의 비교를 통해 왜 어느 문제는 O(N^2) 으로 통과가 되고, 다른 문제는 O(n*log(n))까지 최적화가 필요한지 알아보겠다. 같은 정렬 문제가 아니다. 다음은 정렬과 관련된 3문제를 캡쳐했다. 박스 표시한 곳을 보면 각기 다른 시간/메모리 제한 그리고 입력개수(N)이 다름을 확인할 수 있다. 정렬 관련 로직은 다양하고 각 상황에 맞는 정.. 2024. 8. 14. 이전 1 2 3 4 5 6 다음
