자료구조 문제풀이
- 천재수학자 상필 cou
- ✍2021,2022/자료구조
- · 2022. 8. 19.
728x90
세트1 1. 순열 (중복 x) 2. 조합 (중복x) 여기서 어짜피 visited로 중복 체크를 하기 때문에 i+1 이아니라 i를 보내더라도 ㄱㅊ을듯 3. 순 (중복 o) 중복을 체크하는 방문배열이 필요가 없다. (중복을 허용하기 때문) 4. 조 (중복 o) 세트2 5. 순 전체 집합이 1~10000이라고 한다면, visited 를 1~10000까지 확인한다면 이 문제를 풀 수 있을까? -> x 시간이 너무 많이 들엉 arr+1 인 이유가 인덱스 1 부터라서인듯 6. 조 7. 순 8. 조 세트3 9. 전체집합이 1~10000까지임 근데 분명히 이걸 한번씩 돌면 시간초과일것 1부터 10000까지 나온 숫자만 확인하는것 어떻게 뽑아내서 보냐 ? -> 따로 저장해서 인덱스로만 따져보면 12 13 21 23 31..
- 천재수학자 상필 cou
자료를 효율적으로 표현하고 저장하고 처리할 수 있도록 하는 구조 선형구조/비선형구조 스택 - 자료를 차곡차곡 쌓아올린 형태의 자료구조 후입선출 #inlcude stack st; 로 선언 가능 - 멤버함수 push() pop() top() size() empty() 큐 뒤에서는 삽입 앞에서는 삭제 선입선출 #include queue q; push() pop() front() back() size() empty() 덱 양방향 큐 양쪽끝에서 삽입 삭제 가능한 구조 #incldue deque deq; push_front push_back pop_front pop_back front() back() size() empty()
DP : 하나의 큰 문제를 여러개의 작은문제로 분할하여 해결하는 방법 분할정복과 다르게 작은문제들의 답을 저장한 뒤 재활용 Top - Down, Bottom-Up 너무..빨라 1. 겹치는 부분문제 2. 최적부분구조 사용방법 1. DP로 풀수있는지 판단 2. 반복되는 부분문제찾기 3. 점화식 세우기 4. 기저상태 설정 5. 메모제이션 기법 적용(부분문제 값을 저장해서..ex. 1차원배열..2차원배열...) 6. 구현 예시) 돌게임2 ..? 이해할 새도없었음
이진트리: 노드가 왼쪽 자식과 오른쪽 자식만을 갖는 트리. 두 자식 가운데 하나 또는 둘 다 존재하지 않는 노드가 있어도 상관 없음. 이진트리의 특징은 왼쪽 자식과 오른쪽 자식을 구분한다는 점이다. 완전 이진 트리(Complete Binary Tree) • 높이가 h이고 노드 수가 n개일 때 노드 위치가 포화 이진 트리에서의 노드 1번부터 n번까지의 위치와 완전히 일치하는 이진 트리 높이가 k인 완전 이진트리가 가질 수 있는 노드의 수는 최대 2^(k+1)-1 개 이므로, n개의 노드를 저장할 수 있는 완전 이진 트리의 높이는 log n 이다. 편향 이진 트리(Skewed Binary Tree) • 높이가 h일 때 h+1개의 노드를 가지면서 모든 노드가 왼쪽이나 오른쪽 중 한 방향으로만 서브 트리..
스택과 큐는 추상적 자료구조이다. 언제 큐와 스택을 쓰는가? 브라우저에서 뒤로가기 누르면 스택을쓰는것! 뭔가를쓰다가 뒤로가기 하면 스택이닷! 되돌리기 = 스택에 차곡차곡쌓다가 스택으로 가서 과거 되돌리기 이메일 전달, 푸쉬알림, 쇼핑물 주문처리, 콜센터의 백엔드 : 큐 스택과 비슷한 삽입과 삭제의 위치가 제한되어있는 유한 순서 리스트 큐는 뒤에서는 삽입만 하고, 앞에서는 삭제만 할 수 있는 구조 • 삽입한 순서대로 원소가 나열되어 가장 먼저 삽입(First-In)한 원소는 맨 앞에 있다가 가장 먼저 삭제(First-Out)됨 ☞ 선입선출 구조 (FIFO, First-In-First-Out) 삽입: enQueue 삭제 : deQueue rear : 저장된 원소 중 마지막 원소 front : 제일 앞..