알고리즘 별 자료구조 선택

728x90

Java Collection 을 권장 하는 경우

1. 그래프 알고리즘
- 인접 리스트 표현할 때

: List<List<Integer>> 또는 Map<Integer, List<Integer>>로 사용

List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
    graph.add(new ArrayList<>());
}

- BFS나 DFS에서 큐(Queue<Integer> queue = new LinkedList<>())나 스택을 쓰는 경우

//BFS
Queue<Integer> queue = new LinkedList<>();

//DFS
Stack<Integer> stack = new Stack<>();

2. 우선순위가 필요한 경우
- 다익스트라(Dijkstra) 같은 최단경로 알고리즘

: PriorityQueue (최소 힙) 사용.

PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> a.cost - b.cost);

(최소 신장 트리(MST, Prim)도 마찬가지.)

3. 집합/중복 제거가 필요한 경우
- 방문 체크

: boolean[]로도 가능하지만, 값 범위가 클 경우 HashSet이 유

Set<Integer> visited = new HashSet<>();

- 부분 집합, 중복 단어 제거 문제 등.

(HashSet, TreeSet).

4. 맵핑이 필요한 경우
- 문자열 알고리즘

//문자 빈도 세기
Map<Character, Integer> map = new HashMap<>();

- 그래프에서 노드 ID (인접 노드 리스트 연결할 때도 Map 사용)

Map<Integer, List<Integer>> graph = new HashMap<>();

5. 슬라이딩 윈도우 & 문자열 문제
- 윈도우 내 원소 빈도 추적 → HashMap이 편리 (char → count).
예: "최대 k개의 다른 문자를 포함하는 가장 긴 부분 문자열" 문제.

Map<Character, Integer> freq = new HashMap<>();

1. 단순 정렬 알고리즘

- 버블 정렬, 삽입 정렬, 선택 정렬, 퀵 정렬, 병합 정렬, 힙 정렬 등

- 정렬 대상이 int 등 기본형이면 int[] 권장

int[] arr = {5, 2, 8, 1};
Arrays.sort(arr); // 퀵 정렬 기반

2. 이진 탐색

- 정렬된 배열에 대해 int[]로 구현

- Arrays.binarySearch() 사용하거나 직접 구현

int index = Arrays.binarySearch(arr, target);

3. DP (동적 프로그래밍)

- 대부분의 DP 테이블은 고정 크기이므로 배열이 적합

- 1차원: int[] dp

- 2차원: int[][] dp

int[] dp = new int[n + 1];
dp[0] = 1; // 예: 계단 오르기

4. 분할 정복

- 배열 분할/복사 등에 사용되므로 배열 구조로 충분

- 예: 병합 정렬, 퀵 정렬, Karatsuba 곱셈 등

5. 백트래킹 문제

- 대표 예: N-Queens, 순열, 조합 등

- 상태 추적용으로 int[], boolean[] 자주 사용

boolean[] visited = new boolean[n];
int[] queens = new int[n]; // 열 위치 저장

728x90