2️⃣ 개발 지식 B+47 C 언어 퀴즈 (feat. RB트리 복습) 출처정글 사관학교C Input and Output (Geeks for Geeks)C Functions (Geeks for Geeks)C Data Types (Geeks for Geeks)C Pointer Basics (Geeks for Geeks)C Dynamic Memory Allocation (Geeks for Geeks) 다음 세 함수 f1, f2, f3 각각에 대해서 문제가 있는지, 문제가 있다면 어떤 문제가 있는지 설명하시오.f1 : 지역변수 x의 주소를 return함 - 지역변수는 해당 함수가 끝나면 유효하지 않아서 값이 바뀔 수 있음 f2 : uninitialized pointer - px의 값이 임의의 값이므로 임의의 주소에 10을 넣으려고 함. Segmentation Fault f3 :.. 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. [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. 이전 1 2 3 4 5 6 다음
