데이터 구조 및 알고리즘(DSA) 데이터를 구성하고 저장하는 방법과 이러한 데이터 구조에서 작동하는 문제 해결을 위한 절차(알고리즘) 설계에 대한 연구를 참조하세요. DSA 모든 컴퓨터 과학 학생이 갖춰야 할 가장 중요한 기술 중 하나입니다. 이러한 기술에 대한 좋은 지식을 가진 사람들은 다른 사람들보다 더 나은 프로그래머이기 때문에 거의 모든 거대 기술 기업의 인터뷰에 합격하는 경우가 종종 있습니다. 이것 DSA 튜토리얼 데이터 구조 및 알고리즘(DSA)을 빠르고 쉽게 배울 수 있도록 돕는 것을 목표로 합니다.
내용의 테이블
- 검색 알고리즘
- 정렬 알고리즘
- 분할 정복 알고리즘
- 그리디 알고리즘
- 재귀
- 역추적 알고리즘
- 동적 프로그래밍
- 그래프 알고리즘:
- 패턴 검색
- 수학적 알고리즘
- 기하학적 알고리즘
- 비트 알고리즘
- 무작위 알고리즘
- 분기 및 바운드 알고리즘
DSA 전체 양식
DSA라는 용어는 데이터 구조 및 알고리즘 , 컴퓨터 과학의 맥락에서.
DSA란 무엇입니까?
데이터 구조 및 알고리즘(DSA) 데이터를 구성하고 저장하는 방법과 이러한 데이터 구조에서 작동하는 문제 해결을 위한 절차(알고리즘) 설계에 대한 연구를 참조하세요.
DSA를 배우는 방법?
가장 먼저 해야 할 일은 전체 절차를 순차적으로 수행해야 하는 작은 조각으로 나누는 것입니다. DSA를 처음부터 배우는 전체 과정은 5개 부분으로 나눌 수 있습니다.
- 적어도 하나의 프로그래밍 언어를 배우십시오. (이것은 귀하의 선택에 맡깁니다.)
- 데이터 구조 배우기
- 알고리즘 배우기
- 시간과 공간의 복잡성에 대해 알아보기
- DSA 연습 문제
DSA를 배우는 방법?
선택한 프로그래밍 언어를 배웠기를 바랍니다. 이 DSA 튜토리얼에서 DSA를 배우기 위한 다음 단계로 넘어가겠습니다.
여기에는 데이터 구조 및 알고리즘 학습을 위한 로드맵의 가장 중요하고 가장 기다려지는 단계, 즉 DSA에 대해 학습을 시작하는 단계가 있습니다. DSA의 주제는 두 부분으로 구성됩니다.
- 데이터 구조
- 알고리즘
서로 다른 두 가지이지만 서로 밀접하게 연관되어 있으므로 가장 효율적으로 학습하려면 올바른 길을 따르는 것이 매우 중요합니다. 어떤 것을 먼저 배워야 할지 혼란스러우면 해당 주제에 대한 자세한 분석을 살펴보는 것이 좋습니다. 여기에서는 데이터 구조를 학습한 다음 해당 데이터 구조에서 사용되는 가장 관련성이 높고 중요한 알고리즘을 학습하는 흐름을 따랐습니다.
데이터 구조 배우기
데이터 구조 컴퓨터 메모리에서 데이터를 효율적으로 구성하고 저장하는 데 도움이 되는 필수 구성 요소입니다. 이는 데이터를 효과적으로 관리하고 조작하는 방법을 제공하여 더 빠른 액세스, 삽입 및 삭제 작업을 가능하게 합니다. 일반적인 데이터 구조는 다음과 같습니다. 배열, 연결 목록, 스택, 큐, 트리 및 그래프 , 각각은 당면한 문제의 요구 사항에 따라 특정 목적을 수행합니다. 데이터 구조를 이해하는 것은 효율적인 알고리즘을 설계하고 소프트웨어 성능을 최적화하는 데 필수적입니다.
정렬 동일한 데이터 유형의 요소 모음을 저장하는 선형 데이터 구조입니다. 요소에는 연속적인 메모리가 할당되어 지속적인 액세스가 가능합니다. 각 요소에는 고유한 색인 번호가 있습니다.
- 어레이 작업:
- 순회 : 배열의 요소를 반복합니다.
- 삽입 : 배열의 특정 인덱스에 요소를 추가합니다.
- 삭제 : 배열의 특정 인덱스에 있는 요소를 제거합니다.
- 수색 : 값이나 인덱스로 배열의 요소를 찾습니다.
- 배열 유형 :
- 1차원 배열 : 단일 차원의 간단한 배열입니다.
- 다차원 배열 : 행렬과 같은 다차원 배열입니다.
- 어레이의 응용 :
- 데이터를 순차적으로 저장
- 큐, 스택 및 기타 데이터 구조 구현
- 행렬과 테이블 표현
- 어레이 관련 주제:
- 배열 튜토리얼
- 인터뷰를 위한 상위 50가지 어레이 코딩 문제
- 배열 연습 문제
2. 문자열
ㅏ 끈 일반적으로 텍스트를 나타내는 데 사용되는 일련의 문자입니다. 컴퓨터 프로그램에서 텍스트 데이터를 조작하고 처리할 수 있는 데이터 유형으로 간주됩니다.
- 문자열에 대한 작업 :
- 연쇄 : 두 개의 문자열을 하나로 합칩니다.
- 비교 : 두 문자열을 사전순으로 비교합니다.
- 하위 문자열 추출 : 문자열에서 하위 문자열을 추출합니다.
- 찾다 : 문자열 내에서 하위 문자열을 검색합니다.
- 가감 : 문자열 내의 문자를 변경하거나 대체합니다.
- 문자열의 응용 :
- 텍스트 처리
- 패턴 매칭
- 데이터 유효성 검사
- 데이터베이스 관리
- 관련 게시물:
- 문자열 튜토리얼
- 인터뷰를 위한 상위 50가지 문자열 코딩 문제
- 문자열 연습 문제
삼. 연결리스트
ㅏ 연결리스트 포인터로 연결된 노드에 데이터를 저장하는 선형 데이터 구조입니다. 배열과 달리 연결된 목록은 인접한 메모리 위치에 저장되지 않습니다.
- 연결리스트의 특징:
- 동적 : 연결된 목록은 노드를 추가하거나 제거하여 쉽게 크기를 조정할 수 있습니다.
- 비연속 : 노드는 임의의 메모리 위치에 저장되고 포인터로 연결됩니다.
- 순차적 접근 : 노드는 목록의 선두부터 순차적으로만 접근할 수 있습니다.
- 연결 목록에 대한 작업:
- 창조 : 새 연결 리스트를 생성하거나 기존 리스트에 새 노드를 추가합니다.
- 순회 : 목록을 반복하고 각 노드에 액세스합니다.
- 삽입 : 목록의 특정 위치에 새 노드를 추가합니다.
- 삭제 : 목록에서 노드를 제거합니다.
- 찾다 : 목록에서 특정 값을 갖는 노드를 찾습니다.
- 연결리스트의 종류 :
- 단일 연결 목록 : 각 노드는 목록의 다음 노드를 가리킵니다.
- 이중 연결리스트 : 각 노드는 목록의 다음 노드와 이전 노드를 모두 가리킵니다.
- 순환 연결 목록 : 마지막 노드는 첫 번째 노드를 다시 가리키며 원형 루프를 형성합니다.
- 연결리스트의 응용 :
- 연결된 목록은 다음을 포함한 다양한 응용 프로그램에서 사용됩니다.
- 큐 및 스택 구현
- 그래프와 트리 표현
- 주문된 데이터 유지
- 메모리 관리
- 관련 주제:
- 연결리스트 튜토리얼
- 인터뷰를 위한 연결 목록의 상위 50개 문제
- 연결리스트 연습문제
4. 매트릭스/그리드
ㅏ 행렬 행과 열로 배열된 요소의 2차원 배열입니다. 행과 열의 교차점에 각 요소가 있는 직사각형 그리드로 표시됩니다.
- 주요 개념:
- 행 : 행렬 요소의 수평선입니다.
- 열 : 행렬에 있는 요소의 수직선입니다.
- 치수 : 행렬의 행과 열 수입니다(예: 3×4 행렬에는 3개의 행과 4개의 열이 있습니다).
- 요소 입장 : 행 및 열 인덱스를 사용하여 요소에 액세스할 수 있습니다(예: M[2][3]은 행 2, 열 3의 요소를 나타냅니다).
- 매트릭스/그리드의 응용 :
- 이미지 처리
- 데이터 분석
- 최적화 문제
- 관련 게시물:
- 매트릭스/그리드 튜토리얼
- 인터뷰를 위한 매트릭스/그리드의 상위 50개 문제
- 행렬/격자 연습 문제
5. 스택
스택 작업이 수행되는 특정 순서를 따르는 선형 데이터 구조입니다. 주문은 다음과 같습니다. LIFO(후입선출) 또는 FILO(선입후출) . LIFO 마지막에 삽입된 요소가 먼저 나오고, 열 먼저 삽입된 요소가 마지막에 나오는 것을 의미합니다.
- 스택에서의 작업 :
- 푸시 : 스택의 맨 위에 요소를 추가합니다.
- 팝 : 스택의 맨 위에 있는 요소를 제거하고 반환합니다.
- 몰래 엿보다 : 스택의 맨 위에 있는 요소를 제거하지 않고 반환합니다.
- 크기 : 스택의 요소 수를 반환합니다.
- 비었다 : 스택이 비어 있는지 확인
- 스택의 응용 :
- 함수 호출
- 발현 평가
- 역추적
- 실행 취소/다시 실행 작업
- 스택 관련 주제:
- 스택 튜토리얼
- 인터뷰를 위한 스택의 상위 50개 문제
- 스택 연습 문제
6. 대기줄
ㅏ 대기줄 데이터 구조는 특정 순서로 데이터를 저장하고 관리하는 데 사용되는 컴퓨터 과학의 기본 개념입니다. 그것은의 원리를 따른다 선입선출 ( FIFO ), 여기서 대기열에 추가된 첫 번째 요소는 제거될 첫 번째 요소입니다.
- 대기열 작업 :
- 대기열에 추가 : 대기열 뒤쪽에 요소를 추가합니다.
- 따라서 : 큐의 앞부분에서 요소를 제거합니다.
- 몰래 엿보다 : 앞의 요소를 제거하지 않고 검색합니다.
- 비었다 : 큐가 비어 있는지 확인
- 가득 : 대기열이 가득 찼는지 확인합니다.
- 대기열 유형 :
- 순환 대기열 : 마지막 요소가 첫 번째 요소에 연결됩니다.
- 이중 종료 대기열(Deque) : 양쪽 끝에서 작업을 수행할 수 있습니다.
- 우선순위 대기열 : 우선순위에 따라 요소를 배열합니다.
- 대기열의 응용 :
- 작업 예약
- 메시지 대기열
- 시뮬레이션 모델링
- 데이터 버퍼링
- 관련 주제:
- 대기열 튜토리얼
- 인터뷰 대기열의 상위 50개 문제
- 대기열 연습 문제
7. 더미
ㅏ 더미 힙 속성을 충족하는 완전한 이진 트리 데이터 구조입니다. 모든 노드에 대해 해당 하위 값은 자체 값보다 작거나 같습니다. 힙은 일반적으로 구현에 사용됩니다. 우선순위 대기열 , 여기서 가장 작은(또는 가장 큰) 요소는 항상 트리의 루트에 있습니다.
- 힙의 작동 :
- 끼워 넣다 : 힙 속성을 유지하면서 힙에 새 요소를 추가합니다.
- 추출-최대/추출-최소 : 루트 요소를 제거하고 힙을 재구성합니다.
- 증가/감소-키 : 노드의 값을 업데이트하고 힙을 재구성합니다.
- 힙의 유형 :
- 최대 힙 : 루트 노드는 하위 노드 중에서 최대값을 갖습니다.
- 최소 힙 : 루트 노드는 하위 노드 중에서 최소값을 갖습니다.
- 힙의 응용 :
- 우선순위 대기열
- 정렬
- 그래프 알고리즘(예: Dijkstra 알고리즘)
- 관련 게시물:
- 힙 튜토리얼
- 인터뷰를 위한 힙 관련 상위 50개 문제
- 힙에 대한 연습 문제
8. 해시시
해싱 이라는 수학 공식을 사용하여 가변 크기의 입력에서 고정 크기의 출력(해시 값)을 생성하는 기술입니다. 해시 함수 . 해싱은 데이터 구조에서 항목을 저장하기 위한 인덱스나 위치를 결정하는 데 사용되므로 효율적인 검색 및 삽입이 가능합니다.
- 주요 개념:
- 해시 함수 : 입력을 해시 값에 매핑하는 수학 함수입니다.
- 해시 테이블 : 키-값 쌍을 저장하는 데이터 구조로, 키는 해시 값이고 값은 실제 데이터입니다.
- 충돌 : 두 개의 서로 다른 키가 동일한 해시 값을 생성하는 경우.
- 해시 함수 유형 :
- 분할 방법 : 입력값을 상수로 나누고 나머지를 해시값으로 사용합니다.
- 미드스퀘어 방법: 입력값을 제곱하고 가운데 숫자를 해시 값으로 사용합니다.
- 접는 방법 : 입력된 내용을 동일한 크기의 블록으로 나누고 합산하여 해시값을 얻습니다.
- 곱셈 방법 : 입력에 상수를 곱하고 소수 부분을 해시 값으로 사용합니다.
- 충돌 해결 기술 :
- 별도의 체인(오픈 해싱) : 충돌하는 요소를 연결된 목록의 해당 해시 값에 저장합니다.
- 개방형 주소 지정(폐쇄형 해싱) : 해시 테이블 내에서 요소가 충돌할 대체 위치를 찾기 위해 다양한 전략을 사용합니다.
- 해싱의 응용 :
- 데이터베이스와 파일 시스템에 데이터를 효율적으로 저장하고 검색합니다.
- 비밀번호 및 디지털 서명을 확인합니다.
- 여러 서버에 요청을 분산합니다.
- 데이터 무결성 및 인증을 위한 보안 해시를 생성합니다.
- 관련 게시물:
- 해시 튜토리얼
- 해싱 연습 문제
9. 나무
ㅏ 나무 루트라고 불리는 최상위 노드와 자식 노드를 갖는 노드로 구성된 노드로 구성된 비선형 계층적 데이터 구조입니다. 데이터를 효율적으로 구성하기 위해 컴퓨터 과학에서 사용됩니다.
Java의 유효한 식별자
- 트리 순회 : 트리 순회 방법은 트리 데이터 구조의 노드를 방문하고 처리하는 데 사용됩니다. 세 가지 일반적인 순회 방법은 다음과 같습니다.
- 나무의 분류:
- 분류 나무 특정 특성이나 기준에 따라 나무를 그룹화하는 것을 말합니다. 여기에는 균형 요소, 노드 수준, 순서 속성 등을 기준으로 트리를 분류하는 작업이 포함될 수 있습니다. 다음은 트리에 대한 몇 가지 중요한 분류입니다.
| 분류 | 설명 | 유형 | 설명 |
|---|---|---|---|
| 학위별 | 트리는 각 노드가 가질 수 있는 최대 자식 수에 따라 분류될 수 있습니다. | 이진 트리 | 각 노드에는 최대 2개의 하위 항목이 있습니다. |
| 삼항 트리 | 각 노드에는 최대 3개의 하위 항목이 있습니다. | ||
| N-ary 트리 | 각 노드에는 최대 N개의 하위 항목이 있습니다. | ||
| 주문으로 | 트리는 노드와 하위 트리의 순서에 따라 분류될 수 있습니다. | 이진 검색 트리(BST) | 왼쪽 아이 |
| 더미 | 힙 속성을 가진 특수한 이진 트리입니다. | ||
| 잔액별 | 나무는 얼마나 균형이 잘 잡혀 있는지에 따라 분류될 수 있습니다. | 하위 트리의 높이는 최대 1만큼 다릅니다. 예로는 AVL 트리와 Red-Black 트리가 있습니다. | |
| 불균형 트리 | 하위 트리의 높이는 크게 다를 수 있으며 이는 검색 및 삽입과 같은 작업의 성능에 영향을 미칩니다. |
- 나무의 응용:
- 파일 시스템
- 데이터베이스
- XML 문서
- 인공지능
- 관련 게시물:
- 트리 튜토리얼
- 상위 50개 트리 코딩 문제
- 트리의 연습 문제
10. 그래프
ㅏ 그래프 유한한 정점(또는 노드) 집합과 한 쌍의 노드를 연결하는 가장자리 집합으로 구성된 비선형 데이터 구조입니다.
- 그래프 순회:
- 너비 우선 검색(BFS) : 노드를 레벨별로 방문합니다.
- 깊이 우선 검색(DFS) : 노드를 재귀적으로 방문하여 한 번에 하나의 분기를 탐색합니다.
- 그래프의 응용 :
- 소셜 네트워크
- 지도 및 내비게이션
- 스케줄링
- 데이터 수집
- 관련 게시물:
알고리즘 배우기
일단 개념을 정리하고 나면 데이터 구조 , 이제 여행을 시작할 시간입니다. 알고리즘 . 성격 유형과 용도에 따라 알고리즘은 아래와 같이 여러 범주로 그룹화됩니다.
1. 검색 알고리즘
알고리즘 검색 더 큰 데이터 세트 내에서 특정 데이터를 찾는 데 사용됩니다. 데이터 내에서 목표 값의 존재를 찾는 데 도움이 됩니다. 다양한 유형의 검색 알고리즘이 있으며 각각 고유한 접근 방식과 효율성을 가지고 있습니다.
- 가장 일반적인 검색 알고리즘:
- 선형 검색 : 한쪽 끝에서 다른 쪽 끝까지 반복 검색합니다.
- 이진 검색 : 정렬된 배열에 대한 분할 정복 검색으로, 반복할 때마다 검색 공간이 절반으로 줄어듭니다.
- 삼항 검색 : 각 반복마다 검색 공간을 세 부분으로 나누어 정렬된 배열에 대한 분할 정복 검색입니다.
- 기타 검색 알고리즘:
- 점프 검색
- 보간 검색
- 지수 검색
- 관련 주제:
- 검색 알고리즘 연습 문제
2. 정렬 알고리즘
정렬 알고리즘 숫자순이나 알파벳순과 같은 특정 순서로 목록의 요소를 배열하는 데 사용됩니다. 항목을 체계적인 방식으로 구성하여 특정 요소를 더 쉽게 검색하고 액세스할 수 있습니다.
정렬 알고리즘에는 다양한 유형이 있습니다. 널리 사용되는 일부 알고리즘은 다음과 같습니다.
| 정렬 알고리즘 | 설명 |
|---|---|
| 버블정렬 | 인접한 요소를 반복적으로 비교하고 순서가 잘못된 경우 교체합니다. 패스할 때마다 가장 큰 요소가 목록 끝에 버블링됩니다. |
| 선택 정렬 | 목록의 정렬되지 않은 부분에서 최소 요소를 찾아 첫 번째 요소와 바꿉니다. 전체 목록이 정렬될 때까지 이 과정을 반복합니다. |
| 삽입 정렬 | 정렬되지 않은 각 요소를 정렬된 부분의 올바른 위치에 삽입하여 한 번에 한 요소씩 정렬된 목록을 작성합니다. |
| 빠른 정렬 | 피벗 요소를 선택하고 목록을 피벗을 기준으로 두 개의 하위 목록으로 분할한 다음 동일한 프로세스를 하위 목록에 반복적으로 적용하는 분할 정복 알고리즘입니다. |
| 병합 정렬 | 목록을 더 작은 하위 목록으로 재귀적으로 나누고 정렬한 다음 다시 병합하여 정렬된 목록을 얻는 또 다른 분할 정복 알고리즘입니다. |
관련 주제:
- 정렬 알고리즘 튜토리얼
- 상위 정렬 인터뷰 질문 및 문제
- 정렬 알고리즘 연습 문제
3. 분할 정복 알고리즘
분열시켜 정복하라 알고리즘은 문제를 더 작은 하위 문제로 나누고, 해당 하위 문제를 해결하고, 솔루션을 결합하여 최종 솔루션을 얻는 방식으로 문제를 해결하는 재귀 전략을 따릅니다.
단계:
- 나누다 : 문제를 더 작고 독립적인 하위 문제로 분할합니다.
- 정복하다 : 각 하위 문제를 재귀적으로 해결합니다.
- 결합하다 : 하위 문제의 솔루션을 병합하여 최종 솔루션을 얻습니다.
예:
- 병합 정렬(Merge Sort): 배열을 두 부분으로 나누고, 각 절반을 재귀적으로 정렬하고, 정렬된 절반을 병합합니다.
- 빠른 정렬: 피벗 요소를 선택하고, 피벗을 기준으로 배열을 두 개의 하위 배열로 분할하고, 각 하위 배열을 재귀적으로 정렬합니다.
- 이진 검색: 대상 요소를 찾거나 검색 공간이 소진될 때까지 검색 공간을 반복적으로 절반으로 나눕니다.
관련 기사:
- 분할 정복 튜토리얼
- Divide And Conquer 알고리즘 연습 문제
4. 그리디 알고리즘
이름에서 알 수 있듯이 이 알고리즘은 한 번에 하나씩 솔루션을 구축하고 가장 명확하고 즉각적인 이점을 제공하는 다음 조각, 즉 그 순간에 가장 최적의 선택을 선택합니다. 따라서 로컬 최적을 선택하는 문제는 Greedy에 가장 적합한 글로벌 솔루션으로 이어집니다.
탐욕 알고리즘의 몇 가지 중요한 문제는 다음과 같습니다.
| 연산 | 설명 |
|---|---|
| 분수 배낭 | 배낭에 넣을 수 있는 항목의 최대 총 가치를 구하여 항목을 부분적으로 포함할 수 있습니다. |
| Dijkstra의 알고리즘 | 가중치 그래프의 소스 정점에서 다른 모든 정점까지의 최단 경로를 찾습니다. |
| 크루스칼의 알고리즘 | 가중치 그래프의 최소 스패닝 트리를 찾습니다. |
| 허프만 코딩 | 전체 인코딩 길이를 최소화하여 기호 세트에 대한 최적의 접두사 코드를 생성합니다. |
관련 기사:
- 그리디 알고리즘 튜토리얼
- Greedy 알고리즘 연습 문제
5. 재귀
재귀 함수가 자체 정의 내에서 자신을 호출하는 프로그래밍 기술입니다. 일반적으로 동일한 문제의 더 작은 인스턴스로 나눌 수 있는 문제를 해결하는 데 사용됩니다. 예를 들어: 하노이 타워(TOH) , 계승 계산 그리고 피보나치 수열 등.
단계 :
- 기본 케이스 : 재귀 호출을 중지하고 해결 방법을 제공하는 조건을 정의합니다.
- 재귀 사례 : 문제를 더 작은 인스턴스로 나누고 재귀 호출을 수행하는 단계를 정의합니다.
- 반품 : 재귀 호출에서 솔루션을 반환하고 이를 결합하여 원래 문제를 해결합니다.
재귀를 가장 많이 사용되는 알고리즘 중 하나로 만드는 요점은 다음과 같은 다른 많은 알고리즘의 기반을 형성한다는 것입니다. 트리 순회 , 그래프 순회 , 분할하고 정복하는 알고리즘 그리고 역추적 알고리즘 .
관련 주제:
6. 역추적 알고리즘
앞서 언급했듯이, 역추적 알고리즘은 재귀 알고리즘에서 파생되었으며, 재귀 솔루션이 실패하면 되돌릴 수 있는 옵션이 있습니다. 즉, 솔루션이 실패하는 경우 프로그램은 실패한 순간을 추적하여 다른 솔루션을 기반으로 합니다. 따라서 기본적으로 가능한 모든 솔루션을 시도하고 올바른 솔루션을 찾습니다.
계속 진행하기 전에 해결해야 하는 역추적 알고리즘의 몇 가지 중요하고 가장 일반적인 문제는 다음과 같습니다.
배우 제나트 아만
| 문제 | 설명 |
|---|---|
| 나이트 투어 문제 | 체스판에서 기사가 모든 사각형을 정확히 한 번 방문하도록 하는 일련의 동작 찾기. |
| 미로 속의 쥐 | 벽으로 표시된 장애물이 있는 미로에서 시작 위치에서 출구까지의 경로를 찾습니다. |
| N-퀸 문제 | 두 개의 퀸이 서로 공격하지 않도록 N×N 체스판에 N개의 퀸을 배치합니다. |
| 부분합 문제 | 주어진 합계를 가진 주어진 집합의 하위 집합이 존재하는지 확인합니다. |
| 스도쿠 | 각 행, 열 및 3×3 하위 그리드에 반복 없이 모든 숫자가 포함되도록 1부터 9까지의 숫자로 구성된 9×9 그리드 퍼즐을 푸는 것입니다. |
관련 기사:
- 역추적 튜토리얼
- 역추적 알고리즘 연습 문제
7. 동적 프로그래밍
동적 프로그래밍 복잡한 문제를 더 간단한 하위 문제로 분해하여 해결하기 위해 수학과 컴퓨터 과학에서 사용되는 방법입니다. 각 하위 문제를 한 번만 해결하고 결과를 저장함으로써 중복 계산을 방지하여 광범위한 문제에 대한 보다 효율적인 솔루션을 제공합니다.
주요 개념:
- 최적의 하부구조 : 문제에 대한 최적해는 해당 하위 문제에 대한 최적해로부터 구성될 수 있습니다.
- 겹치는 하위 문제 : 더 큰 문제에서 하위 문제가 반복되는 경우가 많아 중복 계산이 발생합니다.
- 메모 / 표 : 재계산을 피하기 위해 하위 문제에 대한 솔루션을 저장합니다.
계속 진행하기 전에 해결해야 하는 동적 프로그래밍 알고리즘의 몇 가지 중요하고 가장 일반적인 문제는 다음과 같습니다.
| 문제 | 설명 |
|---|---|
| 피보나치 수열 | 중복 계산을 피하기 위해 동적 프로그래밍을 사용하여 피보나치 수를 생성합니다. |
| 가장 긴 공통 부분 수열 | 두 시퀀스에 공통되는 가장 긴 부분 시퀀스를 찾습니다. |
| 가장 긴 증가 부분 수열 | 요소가 오름차순으로 정렬된 주어진 시퀀스의 가장 긴 하위 시퀀스를 찾습니다. |
| 0/1 배낭 문제 | 지정된 중량 한도를 초과하지 않는 범위에서 주어진 중량과 값을 가진 품목을 선택하여 얻을 수 있는 최대 값을 결정합니다. |
| 로드 절단 문제 | 주어진 길이의 막대를 조각으로 잘라서 주어진 가격에 맞춰 판매함으로써 이익을 극대화합니다. |
| 코인 변경 문제 | 주어진 동전 단위 세트를 사용하여 주어진 금액을 변경하는 방법의 수를 결정합니다. |
| 거리 편집 | 한 문자열을 다른 문자열로 변환하는 데 필요한 최소 작업 수(삽입, 삭제, 대체)를 찾습니다. |
| 부분합 문제 | 주어진 합계를 가진 주어진 집합의 하위 집합이 존재하는지 확인합니다. |
| 가장 긴 회문 부분 수열 | 회문인 주어진 수열의 가장 긴 부분 수열을 찾는 것입니다. |
| 최대 하위 배열 합계 | 주어진 1차원 배열 내에서 합이 가장 큰 인접한 부분 배열을 찾습니다. |
| 파티션 동일 하위 집합 합계 | 주어진 집합을 동일한 합을 갖는 두 개의 하위 집합으로 분할하는 것이 가능한지 결정합니다. |
| 최소 비용 경로 | 주어진 그리드의 왼쪽 상단에서 오른쪽 하단까지의 최소 비용 경로를 찾습니다. |
| 최대 제품 하위 배열 | 주어진 1차원 배열 내에서 가장 큰 곱으로 인접한 부분 배열을 찾습니다. |
관련 기사:
- 표 작성과 메모
- 동적 프로그래밍 문제를 해결하는 방법은 무엇입니까?
- 동적 프로그래밍 튜토리얼
- 인터뷰를 위한 상위 50가지 동적 프로그래밍 코딩 문제
- 동적 계획법 알고리즘 연습 문제
8. 그래프 알고리즘 :
그래프 알고리즘 데이터 구조 및 알고리즘(DSA)은 노드와 에지의 집합인 그래프와 관련된 문제를 해결하는 데 사용되는 일련의 기술과 방법입니다. 이러한 알고리즘은 다음과 같은 그래프에서 다양한 작업을 수행하도록 설계되었습니다. 탐색, 탐색, 최단 경로 찾기 , 그리고 결정 연결성 . 이는 네트워크 라우팅, 소셜 네트워크 분석 및 리소스 할당을 포함한 광범위한 실제 문제를 해결하는 데 필수적입니다.
| 주제 | 주제 설명 | 연산 | 알고리즘 설명 |
|---|---|---|---|
| 그래프 순회 | 그래프의 모든 정점을 방문하는 기술. | 깊이 우선 검색(DFS) | 역추적하기 전에 각 분기를 따라 가능한 한 멀리 탐색합니다. |
| 너비 우선 검색(BFS) | 다음 정점 수준으로 이동하기 전에 이웃 정점을 탐색합니다. | ||
| 최소 스패닝 트리 | 최소 스패닝 트리는 가능한 가장 짧은 간선을 추가하여 사이클을 형성하지 않고 그래프의 모든 노드를 연결하는 가장 작은 트리입니다. | 연결된 가중치 그래프에 대한 최소 스패닝 트리를 찾습니다. 순환을 형성하지 않는 가장 작은 가중치 가장자리를 추가합니다. | |
| 또한 연결된 가중치 그래프에 대한 최소 스패닝 트리를 찾습니다. 두 나무를 연결하는 가장 작은 가중치 가장자리를 추가합니다. | |||
| 토폴로지 정렬 | 토폴로지 정렬은 정점 u에서 정점 v까지 모든 방향 간선에 대해 u가 순서에서 v보다 앞에 오도록 방향성 비순환 그래프(DAG)에서 정점의 선형 순서입니다. | 칸의 알고리즘 | Kahn의 알고리즘은 방향성 비순환 그래프(DAG)의 위상적 순서를 찾습니다. |
| DFS 기반 알고리즘 | DFS 기반 알고리즘은 깊이 우선 검색을 사용하여 방향성 비순환 그래프(DAG)에서 위상 정렬을 수행합니다. | ||
| 최단 경로 | 그래프의 최단 경로는 동일한 두 정점 사이의 다른 모든 경로와 비교하여 가장자리를 따라 최소 가중치 합을 갖는 그래프의 두 정점 사이의 경로입니다. | O(E * V logV) 시간 내에 모든 노드 사이의 최단 경로를 찾는 그리디 알고리즘입니다. | |
마크다운 이미지 | O(V^3) 시간 내에 모든 노드 쌍 사이의 최단 경로를 찾습니다. | ||
| O(V * E) 시간에 단일 소스로부터 최단 경로를 찾습니다. | |||
| 존슨 알고리즘 | O(V^2 logV + V * E) 시간에 모든 정점 쌍 사이의 최단 경로를 찾습니다. | ||
| 강하게 연결된 구성요소 | 유향 그래프의 강하게 연결된 구성 요소(SCC)는 집합의 모든 정점에서 집합의 다른 모든 정점까지의 경로가 있는 최대 정점 집합입니다. | Kosaraju 알고리즘은 유향 그래프의 SCC(강하게 연결된 구성 요소)를 효율적으로 찾는 2단계 알고리즘입니다. | |
| 타잔의 알고리즘 | Tarjan의 알고리즘은 유향 그래프에서 SCC를 찾는 또 다른 효율적인 알고리즘입니다. |
관련 주제:
- 그래프 튜토리얼
- 인터뷰를 위한 상위 50가지 그래프 코딩 문제
- 그래프 알고리즘 연습 문제
9 . 패턴 검색
패턴 검색 주어진 텍스트 내에서 특정 패턴의 발생을 찾는 데 사용되는 DSA의 기본 기술입니다.
다음은 몇 가지 표준 패턴 검색 알고리즘입니다.
| 연산 | 설명 | 시간 복잡도 |
|---|---|---|
| 무차별 대입 | 패턴을 텍스트의 모든 하위 문자열과 비교합니다. | 오(백만) |
| 크누스-모리스-프랫 | 불필요한 비교를 건너뛰기 위해 미리 계산된 실패 함수를 사용합니다. | O(m + n) |
| 보이어-무어 | 패턴을 오른쪽에서 왼쪽으로 비교하고 마지막 불일치를 기준으로 문자를 건너뜁니다. | 오(백만) |
| 라빈카프 | 해싱을 사용하여 잠재적 일치 항목을 빠르게 확인합니다. | O(m + n) |
관련 주제:
- 패턴 검색 튜토리얼
- 연습문제 패턴 검색
10 . 수학적 알고리즘
수학적 알고리즘 수학적 개념과 관련된 문제를 해결하는 알고리즘 클래스입니다. 컴퓨터 그래픽, 수치해석, 최적화, 암호화 등 다양한 분야에서 널리 사용되고 있습니다.
| 연산 | 설명 |
|---|---|
| GCD 그리고 LCM | 두 숫자의 최대 공약수와 최소 공배수를 구합니다. |
| 소인수 분해 | 숫자를 소인수로 분해합니다. |
| 피보나치 수열 | 각 숫자가 이전 두 숫자의 합인 피보나치 수열을 생성합니다. |
| 카탈로니아어 숫자 | 주어진 수의 괄호 쌍을 사용하여 유효한 표현식의 수를 셉니다. |
| 모듈러 산술 | 주어진 값을 모듈로 숫자에 대해 산술 연산을 수행합니다. |
| 오일러 토션트 함수 | 주어진 숫자보다 작은 양의 정수 중 상대적으로 소수인 수를 셉니다. |
| nCr 계산 | n개 요소 집합에서 r개 요소를 선택하는 방법의 수를 나타내는 이항 계수를 계산합니다. |
| 소수 및 소수성 테스트 | 주어진 숫자가 소수인지 확인하고 효율적으로 소수를 찾습니다. |
| 체 알고리즘 | 주어진 한계까지의 모든 소수를 찾으십시오. |
관련 주제:
- 수학 알고리즘 연습 문제
11. 기하학적 알고리즘
기하학적 알고리즘 기하학과 관련된 문제를 해결하는 알고리즘 클래스입니다. 기하학적 알고리즘은 다음과 같은 컴퓨터 과학의 광범위한 문제를 해결하는 데 필수적입니다.
| 연산 | 설명 |
|---|---|
| 볼록한 선체 | 점 집합을 포함하는 가장 작은 볼록 다각형을 찾습니다. |
| 가장 가까운 점 쌍 | 세트에서 서로 가장 가까운 두 점을 찾습니다. |
| 선 교차점 | 두 선이 교차하는지 확인하고 교차하는 경우 교차점을 찾습니다. |
| 다각형의 점 | 주어진 점이 다각형 내부에 있는지 외부에 있는지 결정합니다. |
관련 주제:
- 기하알고리즘 연습문제
12. 비트 알고리즘
비트 알고리즘 숫자의 개별 비트에 대해 작동하는 알고리즘입니다. 이러한 알고리즘은 숫자의 이진 표현을 조작하여 비트 조작, 비트 논리 연산(AND, OR, XOR), 비트 이동 , 그리고 환경 또는 특정 비트 지우기 숫자 내에서. 비트별 알고리즘은 일반적으로 다음에서 사용됩니다. 저수준 프로그래밍, 암호화 및 최적화 작업 개별 비트의 효율적인 조작이 필요한 경우.
| 주제 | 설명 |
|---|---|
| 비트 이동 | 지정된 위치 수만큼 비트를 왼쪽이나 오른쪽으로 이동합니다. |
| 왼쪽 시프트(<<) | 비트를 왼쪽으로 이동하여 숫자에 2를 효과적으로 곱합니다. |
| 오른쪽 쉬프트(>>) | 비트를 오른쪽으로 이동하여 숫자를 효과적으로 2로 나눕니다. |
| 비트 추출 | 마스크를 사용하여 정수에서 특정 비트를 추출합니다. |
| 비트 설정 | 마스크를 사용하여 정수의 특정 비트를 1로 설정합니다. |
| 비트 지우기 | 마스크를 사용하여 정수의 특정 비트를 0으로 설정합니다. |
| 비트 토글 | XOR(^)을 사용하여 정수의 특정 비트를 전환합니다. |
| 세트 비트 계산 | 정수에서 설정된 비트(1s) 수를 계산합니다. |
관련 주제:
- 비트 알고리즘 튜토리얼
- 비트별 알고리즘 연습 문제
13. 무작위 알고리즘
무작위 알고리즘은 무작위성을 사용하여 문제를 해결하는 알고리즘입니다. 그들은 목표를 달성하기 위해 무작위 입력을 사용하며 종종 더 간단하거나 효율적인 솔루션으로 이어집니다.
무작위 알고리즘의 유형:
- 라스베가스 : 항상 올바른 결과를 생성하지만 실행 시간은 무작위입니다.
- 몬테카를로 : 낮은 확률로 잘못된 결과가 나올 수 있지만 일반적으로 실행 시간이 더 빠릅니다.
무작위화 알고리즘을 사용하는 중요한 알고리즘:
| 연산 | 설명 |
|---|---|
| 퀵정렬 | 평균 사례 시간 복잡도가 O(n log n)인 무작위 정렬 알고리즘입니다. |
| 건너뛰기 목록 | 빠른 검색 및 삽입 작업을 제공하는 무작위 데이터 구조입니다. |
| 블룸 필터 | 효율적인 세트 멤버십 테스트를 위한 확률적 데이터 구조입니다. |
14. 분기 및 바인딩 알고리즘
그만큼 분기 및 바운드 알고리즘 조합최적화 문제에서 최적의 해를 체계적으로 찾기 위해 사용하는 방법이다. 문제를 더 작은 하위 문제 또는 분기로 나눈 다음 최적 솔루션의 경계에 따라 특정 분기를 제거하는 방식으로 작동합니다. 이 프로세스는 최상의 솔루션을 찾거나 모든 분기를 탐색할 때까지 계속됩니다.
분기 및 바인딩 알고리즘의 표준 문제:
| 독특한 문제 | 설명 |
|---|---|
| Branch and Bound를 사용하는 0/1 배낭 | 0/1 배낭 문제를 해결하기 위한 분기 및 경계 접근 방식의 구현 세부정보입니다. |
| 최소 비용 분기 및 경계를 사용하는 0/1 배낭 | 최소 비용 분기 및 경계 기술을 사용하여 0/1 배낭 문제를 해결합니다. |
| 8퍼즐 Branch and Bound 사용 시 문제 | 인기 있는 슬라이딩 퍼즐 게임인 8퍼즐 문제를 해결하기 위해 브랜치와 바운드를 적용했습니다. |
| N Queen 문제는 Branch와 Bound를 사용합니다. | 브랜치와 바운드를 활용하여 고전적인 체스 문제인 N Queens 문제에 대한 해결책을 찾습니다. |
관련 주제:
- 분기 및 경계 알고리즘 튜토리얼
복잡성에 대해 알아보기
데이터 구조 및 알고리즘(DSA)의 주요 목표는 문제를 효과적이고 효율적으로 해결하는 것입니다. 프로그램의 효율성을 결정하기 위해 우리는 두 가지 유형의 복잡성을 살펴봅니다.
- 시간 복잡도 : 코드를 실행하는 데 걸리는 시간을 알려줍니다.
- 공간 복잡도 : 코드에서 사용하는 메모리 양을 알려줍니다.
점근 표기법 :
알고리즘의 효율성을 비교하기 위해 우리는 다음을 추정하는 수학적 도구인 점근적 표기법을 사용합니다. 시간 기반으로 입력 크기 코드를 실행하지 않고. 프로그램의 기본 작업 수에 중점을 둡니다.
| 표기법 | 설명 |
|---|---|
| 빅오(Ο) | 알고리즘의 상한 시간을 제공하여 최악의 시나리오를 설명합니다. |
| 오메가(Ω) | 알고리즘의 하한 시간 제한을 제공하는 최상의 시나리오를 설명합니다. |
| 세타(θ) | 알고리즘의 알고리즘의 평균 복잡도를 나타냅니다. |
코드 분석에 가장 일반적으로 사용되는 표기법은 다음과 같습니다. 빅오 표기법 , 입력 크기와 관련된 실행 시간 또는 메모리 사용량에 대한 상한을 제공합니다.
관련 주제:
- 간단한 예제를 통해 시간 복잡도 이해하기
- 다양한 데이터 구조의 시간 복잡성
- 알고리즘의 복잡성 분석을 위해 루프를 분석하는 방법
- 시간 복잡도 분석 연습 문제
연습 문제 치트 시트:
아래 기사에서 선별된 문제 목록:
- Sandeep Jain의 DSA 로드맵
- SDE 시트 – SDE 준비를 위한 완벽한 가이드
- techcodeview.com 마스터 시트 – 모든 치트 시트 목록