본문 바로가기

백트래킹6

[Java] 알고리즘 백트래킹 [Java] 알고리즘 백트래킹 백트래킹 DFS와 백트래킹이 다른점 DFS는 가능한 모든 경우의 수를 탐색을 한다 (그래서 시간이 많이 걸린다) 백트래킹은 탐색을 하다가, 불필요한 탐색이라고 생각하면, 다른 루트를 탐색을 한다 백트래킹에서는 얼마나 가지치기를 잘 하느냐가 제일 중요하다 용어 유망 (Promising) : 목표의 값이 될 가능성이 있다는 것 가지치기 (Prunning) : 목표의 값이 될 수 있는 가능성이 없어, 해당 노드를 제외 백트래킹 (Backtracking) : 유망하지 않는 쪽으로 가지 않고 다시 돌아오는 것 void dfs(int cnt, int idx) { // 현재까지의 결과, 탐색을 진행할 인덱스 // r개를 선택한 경우 if(cnt == r) { // 결과 처리 후 현재 가.. 2023. 7. 7.
[Python] 백준 9663 N-Queen 🧑‍💻 [Python] 백준 9663 N-Queen Gold 4 - Backtracking Queen은 위, 아래, 오른쪽, 왼쪽, 대각선, 8 방면 모두 공격을 할 수 있다 N이 주어지고, 체스판 사이즈는 N x N 이고, N 개의 Queen을 넣었을 때 서로 공격할 수 없는 때의 경우의 수를 찾는 것 1차적으로 자세히 보면, 각 행과 열마다, Queen은 하나씩 배치할 수 있다 이 뜻은 굳이 체스판 자체를 안 만들어도 된다 board = [0, 3, 1, 4, 2] 아래 사진을 표현한 리스트 (board의 인덱스가 열/row, board의 값이 행/column) board 안에 있는 값들은 모두 달라야 한다 row (board의 인덱스) column (board의 값) 0 0 1 3 2 1 3 4 4.. 2023. 4. 5.
[Python] 백준 15650 N과 M 2 🧑‍💻 [Python] 백준 15650 N과 M 2 Silver 3 - Backtracking 쉽게 itertools의 combinations를 사용해서 풀 수 있는 문제다 하지만 Backtracking을 공부하고 싶어서 풀었던 문제다 기본적으로 if len(nums) == M: 을 통해서 재귀 함수의 base case를 만든다 안 만들면 무한 루프 리스트 안에 for문을 돌며, 나오는 숫자가 없을 때, 리스트 안에 해당 숫자를 넣고 backtracking(start)를 다시 돈다 여기서 중요한 것은, 수열이 오름차순이어야 한다는 것이다 그래서 재귀함수를 돌릴때마다 backtracking(start + 1)를 해야 한다 그렇게 하면, for문에서 전에서 backtracking() 했던 것보다, 큰 수부터.. 2023. 4. 2.
[Python] 백준 15649 N과 M 🧑‍💻 [Python] 백준 15649 N과 M Silver 3 - Backtracking 쉽게 itertools의 permutations를 사용해서 풀 수 있는 문제다 하지만 Backtracking을 공부하고 싶어서 풀었던 문제다 기본적으로 if len(l) == M: 을 통해서 재귀 함수의 base case를 만든다 안 만들면 무한 루프 리스트 안에 for문을 돌며, 나오는 숫자가 없을 때, 리스트 안에 해당 숫자를 넣고 dfs()를 다시 돈다 그리고 l.pop()을 해야, 리스트에 숫자가 사라지고, 다른 경우의 수를 넣을 수 있다 코드 백트래킹 사용 N, M = map(int, input().split()) l = [] def dfs(): if len(l) == M: print(" ".join(ma.. 2023. 4. 2.
[Python] 백준 1915 가장 큰 정사각형 🧑‍💻 [Python] 백준 1915 가장 큰 정사각형 Gold 2 - Backtracking 행렬을 순회하면서, 1을 찾게되면, 그 1에 대한 모든 경우의 수를 가지고 최소값을 구하는 것이다 예) 찾은 1을 기준으로 1X1 색종이를 덮을 경우 예) 찾은 1을 기준으로 2X2 색종이를 덮을 경우 예) 찾은 1을 기준으로 3X3 색종이를 덮을 경우 예) 찾은 1을 기준으로 4X4 색종이를 덮을 경우 예) 찾은 1을 기준으로 5X5 색종이를 덮을 경우 56번째 줄이 끝나면, 대부분의 1은 0으로 바껴져 있을 것이다 (만약 한 사이즈의 색종이를 5장을 넘기면, 1로 유지가 될 것이다) 코드 matrix = [list(map(int, input().split())) for _ in range(10)] count.. 2023. 3. 31.
Udemy : 알고리즘 DFS, BFS, 백트래킹 Udemy : 알고리즘 DFS, BFS, 백트래킹 udemy 알고리즘 코딩 테스트 그래프 자료구조 그래프는 노드와 링크로 이루어진 자료구조다 노드는 점들이고, 노드를 이어주는 링크, Edge 또는 간선이라고 한다 SNS / 메신저 관계도를 그래프로 만들 수 있다 지도 / 네비게이션 같이 그래프를 실생활에 사용될 수 있다 무방향 또는 방향 그래프로 만들 수 있다 무방향이나 양방향 그래프는 동일한 개념이다 트리 자료구조 순환성이 없는 무방향 그래프다 코드를 그래프로 나타날 때에는 인접 리스트와 행열을 만들 수 있다 연결 행 연결 리스트 DFS (Depth First Search) 깊이 우선 탐색 스택 또는 재귀를 사용해서 구현을 한다 DFS는 완전 탐색이다 BFS (Breadth First Search) 너.. 2023. 3. 13.

티스토리툴바