Algorithm (3) 썸네일형 리스트형 깊이 우선 탐색 DFS 깊이 우선 탐색은 하나의 순환 알고리즘으로 백트래킹에 사용하는 대표적인 탐색 알고리즘이다. 노드와 간선으로 이루어진 그래프에서 한 노드에서 시작해 더 이상 진행할 수 없을 때까지 깊게 들어가며 탐색하는 방식이다. 더 이상 진행할 수 없게 되면 마지막으로 방문했던 노드로 돌아가서 다른 경로를 탐색하는 백트래킹 기법을 사용한다. DFS의 특징 비선형 자료구조 탐색: DFS는 트리나 그래프와 같은 비선형 자료구조에서 사용되며, 모든 노드를 방문하기 위한 효과적인 방법을 제공 스택 또는 재귀 이용: DFS는 내부적으로 스택을 사용하거나 재귀 호출을 통해 구현. 재귀 호출의 경우 시스템 스택이 사용 경로 탐색 및 사이클 감지: DFS는 특정 경로의 존재 여부를 확인하거나 그래프 내 사이클을 감지하는 데 유용 메모.. 구현 구현이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'이다. 어떻게 보면 소스코드를 작성하는 과정은 필수이므로 구현 문제 유형은 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이라고 보면 된다. 구현하기 어려운 문제란? 대체로 사소한 조건 설정이 많은 문제일수록 코드로 구현하기 어려움 구현 문제를 풀기 위해서는? 문법의 정확한 숙지 라이브러리 사용 경험 알고리즘 구현의 단계 문제 이해하기 알고리즘 설계하기 알고리즘 작성하기 테스트 및 디버깅 분석 및 최적화 알고리즘의 효율성은 대게 시간 복잡도와 공간 복잡도로 측정된다. 시간 복잡도는 알고리즘이 문제 해결하는 데 걸리는 시간을, 공간 복잡도는 필요한 메모리 공간을 의미한다. 특히, C/C++/Java에서 구현 유형 문제가 더 어렵게 다가온다. 문.. 정렬 1. 선택 정렬 주어진 리스트 중에서 최솟값을 찾는다. 그 값을 맨 앞에 위치한 값과 교체 arr 배열이 아래와 같을 때, 5 3 1 4 2 ↑ 최솟값 탐색 : 1 첫 번째 값 5와 최솟값 1을 교환 1회전 결과 1 3 5 4 2 ↑ 최솟값 탐색 : 2 두 번째 값 3과 최솟값 2를 교환 2회전 결과 1 2 5 4 3 ↑ 최솟값 탐색 : 3 세 번째 값 5와 최솟값 3을 교환 3회전 결과 1 2 3 4 5 ↑ 4보다 작은 최솟값이 없으므로 종료 오름차순 완성상태 1 2 3 4 5 for(int i=0; i key; j--){ arr[j+1] = arr[j]; } arr[j+1] = key; } 3. 퀵 정렬 피벗을 기준으로 피벗보다 작은 요소들은 피벗의 왼쪽에 위치시키고 피벗보다 큰 요소는 오른쪽에 위치.. 이전 1 다음
