처리중입니다. 잠시만 기다려주세요.
TTJ 코딩클래스
정규반 단과 자료실 테크 뉴스 코딩 퀴즈
더보기
인사이트 FAQ 유튜브 카페

로그인

| 비밀번호찾기

추가 정보 입력

서비스 이용을 위해 휴대전화 번호를 입력해주세요.

회원가입

무료 회원가입 가입비 없이 무료로 가입할 수 있습니다

이미 계정이 있으신가요?

비밀번호 찾기

퀴즈 / 알고리즘 / 문제

타잔(Tarjan) 알고리즘의 주된 용도는?

보통 freeCodeCamp
보기 및 정답
A 방향 그래프에서 강연결 요소(Strongly Connected Components)를 한 번의 DFS로 찾는다
B 무방향 그래프에서 임의의 두 정점 사이의 최단 경로를 하나의 DFS 호출로 찾는 알고리즘이다
C 정렬되지 않은 배열의 원소들을 분할 정복 방식으로 재배치하여 오름차순으로 정렬하는 알고리즘이다
D 이진 트리에서 루트 노드부터 리프 노드까지의 경로를 순회하면서 전체 트리의 높이를 계산하는 트리 순회 알고리즘이다

해설

타잔 알고리즘은 DFS를 한 번 수행하면서 발견 순서(discovery time)와 도달 가능한 최소 순서(low-link value)를 추적하여 강연결 요소를 효율적으로 식별합니다. 시간 복잡도는 O(V+E)이며, 코사라주 알고리즘과 함께 SCC를 찾는 대표적 방법입니다.

코딩, 제대로 배우고 싶다면?

개념 확인은 퀴즈로, 실력은 실전 프로젝트로.
투더제이 코딩클래스에서 시작하세요.

정규반 살펴보기

관련 문제

피보나치 수열을 재귀로 구현할 때 시간 복잡도가 O(2^n)인 이유와 개선 방법은?
알고리즘
유니온-파인드(Union-Find, Disjoint Set)의 주된 용도는?
알고리즘
자료구조에서 AVL 트리의 핵심 특성으로 올바른 것은?
알고리즘
알고리즘에서 '위상 정렬(Topological Sort)'을 적용할 수 있는 그래프의 조건은?
알고리즘
알고리즘에서 '동적 프로그래밍(Dynamic Programming)'의 두 가지 핵심 조건으로 올바른 것은?
알고리즘