본문 바로가기

2️⃣ 개발 지식 B+/코딩 테스트10

[python] 코테 유형별 템플릿 모음 #stackst = [] # 과거값 참조for item in items: if st[-1] vs item: st.pop() else: st.append(item)  #priority-queueimport heapqarr = []# Q = heapq.heapify(arr)for item in items: heapq.heappush(arr, item) # min-heap # heapq.heappush(arr, -item) # max-heap; 꺼낼 때 유의while Q: poped = heapq.heappop(arr) # action  #graph #위상정렬# n = vertex 개수# edges: List[Tuple[int, int]]from collections import defau.. 2024. 10. 27.
[python] 유용한 문법 iteratoritems = [1, 2, 3, 4, 5]filtered = list(filter(lambda i: i%2 == 0, items))arr = map(int, input().split()) 비트 연산자# addmask = 0mask = mask | 1   기타# 문자열 포매팅var = 345.6789s1 = f'{variable}' # 345.6789s2 = f'{variable:.2f}' # 345.68 # 주의! variable 콜론 뒤에 여백 반영되므로 꼭! 붙이기# 숫자 문자열 리스트화s = "101110"arr = [int(char) for char in s] # [1, 0, 1, 1, 1, 0]# zip, unzipA = [1, 2, 3]B = [4, 5, 6]pairs = zi.. 2024. 9. 7.
🏃[백준/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.
[백준/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.

티스토리툴바