알고리즘

배열의 index와 value를 프로그래머가 의미 부여해서 사용하는 것일반 배열을 통해서도 문제 풀이가 가능하지만 DAT는 문제 유형에 따라 연산 횟수를 줄일 수 있음(1) 숫자 게임심판이 1~9까지의 숫자 중 하나를 부름1~9까지의 숫자 중 하나를 몇개인지 질문(2)

2차원 좌표 상에서 한 점을 기준으로 상하좌우 좌표를 구할 때 사용하는 배열 방향 배열은 BFS, Flood Fill 등 다른 알고리즘에서 활용될 수 있음 코드 예시 (Java)

함수 스스로가 자기 자신을 다시 호출하는 함수문제를 더 작은 단위의 동일한 문제로 쪼개서 해결할 때 주로 사용종료 조건 (Base Case)재귀 호출을 멈추는 조건종료 조건이 없으면 함수가 영원히 자신을 호출하다가 컴퓨터 메모리가 꽉 차서 프로그램이 강제로 종료되는 '

지금 경로가 해결책으로 이어질 것 같지 않으면 더 이상 가지 않고 되돌아가(Backtrack) 다시 해를 찾는 기법가능한 모든 경우의 수를 확인하되, 정답이 될 가능성이 없는 길은 미리 포기해서 효율을 높임$N \\times N$ 체스판 위에 $N$개의 퀸을 서로 공격

그래프를 행렬로 구현정점의 개수가 $N$일 때, $N \\times N$ 크기의 2차원 배열matrixi = 1이면 $i$와 $j$가 연결됨, 0이면 연결되지 않음 (가중치 그래프라면 1 대신 가중치 값 저장)그래프를 리스트로 구현각 정점마다 리스트(List, Vect

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다. Queue를 사용 (FIFO) 문제 유형 두 노드 사이의 최단 경로 혹은 임의의

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 스택 또는 재귀 함수를 사용 Cycle이나 양방향 그래프를 고려하여 visited 배열 사용 필요!! 문제 유형 검색 대상 그래프가 큰 경우

우선순위가 가장 높은 요소가 먼저 나오는 자료구조 각 요소는 우선순위와 함께 저장되며, 삽입 순서와 상관없이 우선순위에 따라 요소가 추출 특징 우선순위가 높은 데이터가 먼저 나옴 힙(Heap) 자료구조로 구현되는 것이 일반적 시간 복잡도: 삽입: O(log

한 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘 조건: 가중치가 0 이상인 그래프 음수 간선이 있는 경우 사용할 수 없음 (그럴 땐 벨만-포드 사용)

키(Key)와 값(Value)을 쌍으로 저장하고, 키를 이용해 빠르게 검색, 삽입, 삭제가 가능한 자료구조키를 해시 함수(Hash Function)로 변환 → 배열(버킷) 인덱스로 사용충돌(Collision)이 발생하면 별도의 처리 필요복잡도 \- 평균: O(1) (