본문 바로가기

Python/코딩테스트4

백트래킹 (Backtracking) 알고리즘 00 개요목표: 코딩테스트 뽀개기!01 백트래킹1. 백트래킹이란DFS와 같이 모든 경우의 수를 확인해야 할 때 사용됨DFS: 가능한 모든 경로(후보) 탐색, 그러나 불필요할 것 같은 경로를 사전에 차단하는 행동이 없으므로 경우의 수를 줄이지 못함 (i.e., N!가지 경우의 수를 가진 문제에는 적합하지 않음)for로는 확인 불가능한 경우 (깊이가 달라지는 경우)해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아가야 되는 경우 모든 가능한 경우의 수 중 특정 조건을 만족하는 경우만 살펴봐야 하는 경우즉, 답이 될만한지 판단하고 그렇지 않으면 그 부분까지 탐색하는 것을 하지 않고 가지치기 해야하는 경우주로 문제 풀이에서는 DFS 등으로 모든 경우의 수를 탐색하는 .. 2024. 11. 8.
DFS (Depth-first search) 알고리즘 00 개요목표: 코딩테스트 뽀개기!1. 그래프 탐색이란 어떤 것들이 연속해서 이어질 때, 모두 확인하는 방법 Graph: Vertex (어떤 것) + Edge (이어지는 것)2. 그래프 탐색 종류BFS: Breadth-first search (너비 우선 탐색)DFS: Depth-first search (깊이 우선 탐색) 01 DFS1. DFS란Depth-first search, 깊이 우선 탐색그래프 탐색 종류 중 하나Stack 또는 재귀 함수 사용, Queue 미사용!재귀 함수는 백트래킹 알고리즘에서도 사용!2. 재귀함수란자기 자신을 다시 호출하는 함수# 예시def my_function(a): c = a + 1 if c 주의: 재귀 함수가 종료되는 시점을 반드시 명시해야 됨재귀 함수의 깊이가 .. 2024. 11. 8.
BFS (Breadth-first search) 알고리즘 00 개요목표: 코딩테스트 뽀개기!1. 그래프 탐색이란어떤 것들이 연속해서 이어질 때, 모두 확인하는 방법Graph: Vertex (어떤 것) + Edge (이어지는 것)2. 그래프 탐색 종류BFS: Breadth-first search (너비 우선 탐색)DFS: Depth-first search (깊이 우선 탐색) 01 BFS1. BFS란Breadth-first search, 너비 우선 탐색그래프 탐색 종류 중 하나Queue 사용, Stack 미사용!2. 준비하기1) 아이디어시작점에 연결된 Vertex 찾기 찾은 Vertex를 Queue에 저장 Queue의 가장 먼저 것 뽑아서 반복2) 시간 복잡도O(V+E)3) 자료구조검색할 그래프 방문여부 확인(재방문 금지) Queue: BFS 실행3. 연습 문제:.. 2024. 11. 4.
코딩테스트 개요 00 개요다짐: 코딩테스트 뽀개자1. 코딩테스트란시간 안에 주어진 문제를 푸는 시험, 적절한 알고리즘 선택하여 문제 해결이 목적채점 방식: 입력값을 여러개 넣고, 모두 통과하는지 확인 (하나라도 통과 못하면 틀림)공부 방법: 개념 이해, 기본 문제, 코드 imitate, 안 보고도 코드 작성할 수 있을 정도로 외우기, 유사 문제 풀어보기각 알고리즘 이해 후: 하루에 몇 과목 씩 돌아가면서 풀기, 한 문제 Max 30분 넘기지 않기, 틀린 문제 복습하면서 반복, 시간 정하면서 문제 풀기, 스터디 활용2. 필수 알고리즘 10개:BFS, DFS, 백트래킹, 시뮬레이션, 이진탐색, Greedy, DP, MST, 다익스트라, 플로이드3. 문제 페이지백준: https://www.acmicpc.net/프로그래머스: .. 2024. 11. 4.

티스토리툴바