정글/TIL

📌 - G5_12865_평범한 배낭 문제 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net DP문제를 풀기 시작했는데, 계속 머리를 굴려봐도 풀이법이 생각나지 않아서 다른 사람들 풀이를 참고했다. 이때까지는 2차원 배열을 컨트롤 할 때 i,j를 이용해서 i,j의 값에 맞는 칸을 업데이트 시켜주는 느낌이었는데, DP는 여러 문제들을 보다보니 i,j로 컨트롤 하긴 하지만 , 아래의 예..

스택 문제 - G3-2812-크게 만들기 나의 풀이 법 (스택의 갯수와 남은 숫자의 갯수를 비교해서 계산) from sys import stdin as s from collections import deque s = open('input.txt') N, K = list(map(int,s.readline().split())) arr = list(map(str.rstrip,s.readline())) a = deque() a.append(int(arr[0])) for i in range(1,N): while len(a) + N-i-1 >= N-K: # 스택 개수 + 남아있는 숫자 개수 >= 마지막에 필요한 개수 if len(a)-1 >=0 and int(arr[i]) > a[len(a)-1]: # 스택의 크기..

👥 이진 탐색 - 배열이 정렬되어 있어야 하며, 하나의 배열에서 반반 쪼깨서 값을 찾는 탐색이다. - 시간 복잡도는 O(logN)이다 이진 탐색의 기본 틀 from sys import stdin as s s = open('input.txt','rt') N, M = list(map(int,s.readline().split())) arr = list(map(int,s.readline().split())) def binary_search(array, target,start,end): if start > end: return None mid = (start + end) //2 if array[mid] == target: return mid elif array[mid] >target: return binary_s..

🗒️ 시간 복잡도, 공간 복잡도(Big-Oh Notation) - 시간 복잡도에는 O(n) - 시간의 상한(최악의 경우), Ω(n) - 시간의 하한(최선의 경우), Θ(n) - 평균적인 경우 - 시간은 한계치가 명확한 반면 공간은 최근 대용량 시스템이 보편화 되면서, 공간 복잡도 보다는 시간 복잡도가 우선이 된다. 그래서 시간 복잡도가 더 중요하게 생각된다. - 공간 복잡도를 줄이는 방법은 배열의 크기, 동적할당, 재귀호출 수 등으로 줄일 수 있습니다. 🗒️ Quick sort, Insertion sort, merge sort, heap sort - O(n log n) : 퀵 정렬(quick), 힙 정렬(heap), 병합 정렬(merge) - O(n^2) : 삽입 정렬(insertion) Quick so..

입소식 간단하게 입소식 진행 , 장병규 의장님 강연, 생활 안내 아이디어 첫 팀 프로젝트 아이디어 및 와이어 프레임 제작 프로젝트 발표자료 준비 매일 공부 시간 기록하기