분류 전체보기100 [백준/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. [정글 SW사관학교] WEEK2. 풀이 고민 소요 시간에 대한 이분탐색 🤔회고 팀활동 방식에 대한 고찰 매주 새로운 주제 그리고 사람들과 협업을 하다보니 prev 조에서의 방식이 current 조에서 해답이 될 수 없었다. 1일차에는 같이 공부하고 풀기 > 2일차에는 개인 플레이 > 그리고 3일차 드디어 절충안을 찾을 수 있었다. WEEK2 1조가 찾은 팀활동은 다음과 같다. 개념 공부 후 공유주제별로 1문제씩 (새로운 문제로) 함께 문제 분석 시작 및 로직 세워보기 (이때, 문제를 풀기 위한 아이디어가 나오면 해당 아이디어가 채택되고, 반례는 없는지, 예외 처리는 어떻게 할지 등을 논의합니다)허점 없이 로직이 세워지고 코드를 구현해보는게 가장 베스트겠지만, 코드를 구현해보면서 디버깅을 통해 예외 처리하는 경우도 있어서 30분 정도 시간 제한 후 구현을 시작한다.코드 리뷰.. 2024. 8. 22. [백준/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. [정글 SW사관학교] WEEK1. 나는야 백준 골드 유망주 🤔회고루틴 점검 (아침 산책 > 강의실 도착 및 아침 > 공부(~ 23시) > 저녁 산책 > 스트레칭 (or 요가)오랜만에 '요가소년' 플로우를 따라했는데 너무나 개운했다. 정글 3일째부터 앉아만 있었는데 무릎이 아파와서 발받침대를 사며 여러 노력을 했지만 역시 운동과 스트레칭을 자주해주는 수 밖에 없는 것 같다. 쨌든 저녁에 일찍 귀가한 날 (그게 23시 이지만) 학교 한바퀴를 돌았는데 좋은 시도였던 것 같다. 날씨 선선해지면 더 많이 돌고 싶어질 것 같다. 그 외- 조급해하지 않기, 거북이처럼 느리게 결국에 완주하자! 나 자신과의 싸움- 이번주 유머코드; find = True #찾았다!- 조별 자율 학습이 가능한 이유; 각자 잘 아는 지식이 섞여 시너지가 나는 듯. 그리고 안다고 생각했던 곳에서 허.. 2024. 8. 16. 이전 1 2 3 4 5 6 7 8 ··· 12 다음
