study with yuin

1. DP 기본 개념Dynamic Programming (동적 프로그래밍)큰 문제를 작은 문제로 나누고, 한 번 푼 문제의 결과를 저장해서 다시 사용하며(중복 계산 방지) 효율적으로 푸는 알고리즘 기법.조건Overlapping Subproblems — 같은 부분 문제가 반복해서 등장Optimal Substructure — 문제의 최적해가 부분 문제의 최적해로 구성됨핵심 키워드Memoization (Top-Down): 재귀 + 캐싱 방식. 필요할 때만 계산하고 저장.Tabulation (Bottom-Up): 반복문으로 DP 테이블을 순차적으로 채우는 방식.상황별 방식 추천상태·전이 정의가 명확, n이 크며 재귀 깊이 위험Bottom-Up도달하는 상태가 일부, 전이 분기 많음Top-Down + 메모이제이션경..

JAVA의 정렬- 자바에서는 데이터를 정렬하는 여러가지 방 법을 제공 -> 이 기능들이 코테에 유용하게 사용됨!- 기본적인 오름차순, 내림차순정렬 + 사용자 정의 정렬 모두 할 수 있어야 함 📌 1. Java 기본 정렬 APIArrays.sort()배열을 정렬할 수 있는 기본적인 정렬 기능기본 타입 배열, 객체배열 모두 가능하지만 내부 정렬 알고리즘이 다름Primitive 타입(int[], double[] 등): Dual-Pivot QuickSort (O(n log n), 최악 O(n^2))객체 배열(String[], Integer[] 등): TimSort (MergeSort + InsertionSort 혼합, O(n log n))내림차순? 오름차순만 지원하기 때문에 내림차순구현하려면 정렬 기준을 C..

다양한 정렬 알고리즘 알아보는 시간~ ✋ 들어가기 전에 잠깐! '안정 정렬'에 대해서 먼저 알아보자안정 정렬이란? 같은 값을 가진 데이터의 원래 순서가 유지되는 정렬주어진 조건대로 정렬을 하되, 만약에 두개가 같은 값이라면 기존 순서를 유지하는 ㅇㅇ[이름, 점수] 가 있을 때 점수오름차순으로 정렬할 때, A90 B90이 있으면 해당 정렬 기법을 썼을 때 기존 순서그대로 A90 B90으로 순서가 똑같이 유지되는 것!✅ 1. 버블 정렬 (Bubble Sort)🧠 원리인접한 두 수를 비교해서 큰 수를 뒤로 보내는 방식앞에서부터 두수씩 큰수를 뒤로 보내기 → 그럼 가장 큰수가 맨 뒤로 가게 됨!그렇게 반복하면 오름차순 정렬 완료가장 큰 수가 ‘버블’처럼 맨 뒤로 올라옴예시더보기더보기예시[5, 3, 8, ..

Greedy 그리디 탐욕법: 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만 쫓아 최종적인 해답에 도달하는 방법현재 볼 수 있는 선택지 중에 최선의 선택을 하는 알고리즘각 단계에서의 최선의 선택이 전체적으로도 최선이길 바라는 알고리즘동적 계획법보다 구현하기 쉽고 시간복잡도가 우수함공식 없이 창의력을 요구하는 유형항상 최적의 해를 보장하지 못한다는 단점도 있음 → 그리디 사용 전에 항상 논리 유무를 충분히 살펴야 함지금 선택하면 마시멜로 1개 받고, 1분 기다리면 2개 받는 상황에서 그리디 알고리즘 사용하면 매번 1개밖에 받지 못함! 이때는 적절하지 않음방법해 선택: 현재 상태에서 가장 최선이라고 생각되는 해 선택적절성 검사: 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사해답 검사: 현..

✅ 1. 이진 탐색(Binary Search) 기초전제 조건: 반드시 정렬된 배열이어야 함목표: 배열에서 target 값의 위치를 빠르게 찾기 (O(log N))기본 형태 (Java):int binarySearch(int[] arr, int target) { int left = 0, right = arr.length - 1; while (left ✅ 2. Java의 Arrays.binarySearch()int[] arr = {1, 3, 5, 7, 9};int idx = Arrays.binarySearch(arr, 5); // → 2int idx2 = Arrays.binarySearch(arr, 4); // → -3찾으면: 해당 인덱스 반환못 찾으면: (삽입할 위치) - 1 반환👉 따라서 lo..

STL: c++에서 제공하는 library vector vector는 가변크기 배열 stl을 인자로 넘길때 복사본이 넘어감 vector를 그냥 째로 넘기면 복사본이 넘어가기때문에 함수에서 바꿔도 값이 안바뀜! vector를 인자로 넣으면 복사본을 만들기 위한 과정도 필요하기때문에 O(N)임!!! &를 써서 시간복잡도를 줄일 수 있음. 표준입출력 공백포함 문자받을때 string, getline ios::sync_with_stdio(0) cin.tie(0) (ios쓸때는 printf, scanf쓰지x) endl은 절대 쓰지 마세요 개행문자를 출력하고 출력버퍼를 비워라라는 명령인데 중간중간 버퍼를 지울 필요가 없음. 그냥 개행문자를 출력하세요: “\n” 코드작성 팁 코딩테스트와 개발은 다르다!! 깔끔하게 코드..

바킹독 8강 기록 스택의 대표적인 활용사례: 수식의 괄호 쌍, 전위/중위/후위 표기법, DFS, Flood Fill 등이 있음 전중후위 표기법은 코테 문제로 잘 안나와서 빼고 나머지 다룰 거. 이번엔 그중 수식의 괄호쌍 수식의 괄호쌍 32-{6-(2+4)x7} 주어진 괄호쌍이 올바른지 판단하는 문제 눈으로 보면 판단이 쉽지만 우린 이걸 코드로 구현해내야 함. 어떻게 풀 수 있을까? 닫는 괄호 수, 여는 괄호 수 개수 맞는지 확인 배열로 구현하면 o(n2) 연결리스트로는 o(n) 스택은 더 간단. 문자열을 앞에서부터 읽어나갈 대, 닫는 괄호는 남아있는 괄호 중에서 가장 최근에 들어온 여는 괄호와 짝을 지어 없애버리는 명령이라고 생각해도 된다. 문제해결 방법 여는 괄호가 나오면 스택에 추가 닫는 괄호가 나오..

정의 deque double ended queue 양쪽 끝에서 삽입 삭제 모두 가능 성질 성질 원소 추가 제가 O(1) 제일 앞/뒤의 원소확인이 o(1) 원칙적으로 제일 앞/뒤 원소 확인/변경이 불가능인데 독특하게 stl 에선 인덱스로 원소 접근 가능 STL deque vector와 비슷한데 front에도 o(1)에 추가,제거 가능한 느낌? c++ vector vs deque 나중에 찾아보기 앞뒤에서의 추가제거가 필요하면 deque쓰고 굳이 필요없으면 vector쓰면됨. push_back(x): 맨 뒤에 추가 push_front(x): 맨 앞에 추가 pop_back: 맨 뒤 삭제 pop_front: 맨 뒤 삭제 insert(iter, x) : iter앞에 x추가 (d.insert(d.begin()+2, ..

정의 사전적 의미: 줄을 서서 기다리는 것. 줄을 지어 순서대로 처리되는 자료구조 FIFO(First in First Out): 먼저 들어간 원소가 나중에 나오는 구조 *큐는 먼저 집어넣은 데이터가 먼저 나오는 성질 (FIFO)을 가진 자료구조. 나중에 집어넣은 데이터가 먼저 나오는 스택과는 반대되는 개념. 삽입 삭제 O(1), 탐색O(n) 사용되는 예제: cpu작업을 기다리는 프로세스, 스레드행렬, 네트워크 접속을 기다리는 행렬, 너비우선탐색, 캐시 등 성질 - 원소의 추가,제거 O(1) - 추가되는 곳: (뒤쪽)rear, 제거되는 곳:(앞쪽)front (스택에선 top) - 가장 앞뒤원소 확인 O(1) 배열로 만들면 중간 원소도 인덱스로 접근가능. 원칙적으로는 불가. STL queue 보통 큐는 BF..

정의 데이터를 차곡차곡 쌓아올린 형태의 자료구조. LIFO(Last in First Out) 먼저 들어간 원소가 제일 나중에 나옴 한쪽 끝에서만 원소를 넣거나 뺄 수 있는 자료구조 * 스택은 가장 마지막으로 들어간 데이터가 가장 첫번째로 나오는 성질 (LIFO)을 가진 자료구조. 재귀적인 함수, 알고리즘에 사용 EX 웹브라우저 방문기록 등 삽입 삭제 O(1) 탐색 O(n) 성질 - 원소 추가 제거 o(1) - 제일 상단의 원소 확인 o(1) - 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능(배열으로 만들면 확인가능하긴 함) 구현 배열 혹은 연결리스트로 구현가능(배열이 더 쉬움) const int MX = 1000005; int dat[MX]; int pos = 0; //pos는 다음원소..