알고리즘 (17) 썸네일형 리스트형 BFS(너비 우선 탐색) 그래프를 완전히 탐색하는 방법 시작 노드를 기준으로 가장 가까운 노드를 먼저 방문하며 탐색하는 방법 FIFO 방법 Queue 자료구조 이용 경로가 여러 개일때 최단 경로를 보장 과정 BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기 큐 자료구조에 값이 없을 때 까지 반복 DFS(깊이 우선 탐색) 그래프 완전 탐색 기법 시작 노드에서 출발하여 탐색할 쪽 분기를 정한 뒤, 최대 깊이 탐색 후 다른쪽 분기 탐색 재귀함수, Stack 자료 구조 이용 시간복잡도(V + E) 재귀함수 구현시 스택 오버플로우를 유의 트리 완전 탐색에서 사용 DFS 실행 횟수가 연결 요소 개수와 같음 핵심이론 노드 방문을 체크할 배열이 필요 그래프는 인접리스트로 표현 과정 DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입 스택 자료구조에 값이 없을 때 까지 반복 방문한 노드는 확인후 스택에 넣지 않음 선택 정렬 시간 복잡도: O(n^2) 최소값 찾는데 n 번, 그 다음 최솟 값을 찾는데 n번 해서 N^2 최솟값 또는 최댓값을 찾고, 남은 정렬 부분의 가장 앞에 있는 데이터와 swap N이 100,1000처럼 작은 경우에서 사용하는게 좋음 버블 정렬 데이터의 인접 요소끼리 비교하고, Swap 연산을 사용하여 정렬 O(n^2) n번 걸리는 것을 n번 하므로 n^2 (0,1) - (1,2) - (2,3) 과 같은 과정으로 비교 Stack , Queue 스택과 큐 Stack(스택)후입선출용어Top: 삽입과 삭제가 일어나는 위치push: top 위치에 새로운 데이터를 삽입pop: top 위치에 새로운 데이터를 삭제하고 확인peek: top 위치에 현재 있는 데이터를 단순 확인우선 탐색(DFS), 백트래킹 종류에서 효과적new Stack()은 자바 초창기에 나온 Vector 기반이라 멀티 코어 성능에서 좋지 않다.Deque를 사용하는 것을 추천Thread-safe가 필요한 경우 concurrentLinkedDeque 사용큐선입선출삽입 삭제가 양방향용어rear: 큐에서 가장 끝 데이터를 가리키는 영역(가장 최근에 들어온 데이터)front: 큐에서 가장 앞의 데이터를 가리키는 영역add: rear 부분에 새로운 데이터를 삽입poll: front 부분에 데이터를 삭제하고 .. 구간 합 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 알고리즘 합 배열 : S[i] = S[i-1] + A[i] 합의 값을 계속 더한다. 구간 합: S[j] - S[i-1] 구하고자 하는 범위 끝에서 해당하지 않는 부분 제거 배열과 리스트 배열 연속적인 공간에 값이 채워져있는 형태, Index를 통해 참조 값을 삽입하거나, 삭제하는 경우, 해당 인덱스 주변의 값을 이동시키는 과정이 필요 크기는 선언할 때 지정, 그 후 변경 불가능 코딩테스트에서 많이 사용 리스트 값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조 Head 포인터부터 순서대로 접근, 속도가 느림 데이터를 삽입, 삭제 연산 속도가 빠름 크기를 별도로 지정하지 않아도 됨 디버깅 문법 오류나 논리 오류를 찾아 바로잡는 과정 로그를 찍는 방법도 있지만 디버깅이 더 좋은 방법 코테마다 지원하는 곳도 있고 없는 곳도 있지만 개발 습관에 좋은 방향 자료형 범위 오류 찾는데 도움이 됨 자료형은 long형으로 선언 / 하지만 코테과정에서만. 이전 1 2 3 다음