📌 - 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..
정글에서 살아남기 위해서 매일매일 해야할 목표를 설정 일단 해보자! 지난 과거 뭔가 항상 만족하지 못하는 삶을 살고 있는 것 같다. 걱정이 많고 생각이 많은 한 사람으로써 항상 내가 하는 일에 대한 신뢰가 부족하고 또 두렵고, 그렇다고 막 무언가를 잘 해내는 사람도 아니었던 것 같다. 대학교 시절에는 다른 친구들이 코딩을 너무 잘하고 즐기는 것에 비해 본인은 잘하지도 않고 또 잘하지 못하니 즐겁지도 않아서 취직을 이 쪽 분야로 하지 않겠다고 생각했었고, 생각의 여파인지 외우기나 하자해서 이론만 공부했었던 것 같다. 시험치고 까먹고 시험치고 까먹고 반복하다보니 취업을 준비할 시기에는 CS도, 프로젝트도, 실력도 뭐 하나 제대로 된게 없었다. 취업을 준비하는 기간에 생각을 해보니 뭔가 공부를 할 때 가장 ..
