코딩테스트/알고리즘 (2) 썸네일형 리스트형 백트래킹 백트래킹(Backtracking)은 문제를 해결하는 과정에서 가능한 모든 경우를 시도하는 방법입니다. 쉽게 말해, 여러 선택지를 하나씩 시도해보면서 조건을 만족하는 해를 찾는 과정입니다. 만약 어떤 선택이 조건을 어긴다면, 그 선택을 취소하고 다른 선택을 시도하는 방식으로 진행됩니다.백트래킹의 기본 개념상태(State): 현재 선택한 값이나 설정.목표(Goal): 문제의 해결책.유효성 검사: 현재 상태가 목표를 만족하는지 확인.재귀 호출: 다음 상태로 넘어가는 과정.되돌아가기(Backtrack): 더 이상 진행할 수 없는 경우 이전 상태로 돌아가는 과정.예시: 부분집합 구하기부분집합 문제는 주어진 집합의 모든 부분집합을 구하는 문제입니다. 예를 들어, 집합 {1, 2, 3}의 모든 부분집합을 찾아보겠습니.. 코딩테스트 알고리즘 - BFS, DFS 그래프 탐색어떤 것들이 연속해서 이어질 때 모두 확인하는 방법Graph : Vertex(어떤것. 노드) + Edge(이어지는 것. 연결선)BFS너비 우선 탐색 : 자기 자식 우선 탐색시작점에 연결된 vertex찾기 -> 찾은 vertex를 queue에 저장DFS깊이 우선 탐색 : 자식의 자식을 우선 탐색 깊이 우선 탐색 : 자식의 자식을 우선 탐색연결된 vertex 찾기 -> 찾은 vertex를 stack에 저장시간복잡도알고리즘이 얼마나 오래 걸리는지Big-OBFS : O(V+E)사용 자료구조BFS검색할 그래프방문 여부 확인(재방문 금지 목적)Queue : BFS 실행 이전 1 다음
