# back tracking
알고리즘 스터디 (스도쿠[백준 2580])
스도쿠 - 2580일반적으로 아는 스도쿠 문제를 해결한다.9X9 스도쿠 문제를 해결가로, 세로, 3X3에 1~9의 수가 하나씩 들어가야 한다.DFS, Back Tracking을 이용해서 문제를 해결한다.스도쿠를 입력받는다.0,0 부터 탐색을 한다.스도쿠의 현재 위치의
[ BOJ / Python ] 15684번 사다리 조작
이번 문제는 백트레킹을 통해 해결하였다. 우선 사다리가 겹치거나 만나면 안되기 때문에 이를 체크할 리스트 ladders를 2차원 리스트로 선언하였다. 그리고 입력받은 사다리에 해당하는 좌표 laddersa를 1로 갱신해주었다. 여기서 주의할 점은 a, b에서 무조건 자
[백준] #12100: 2048 (Easy)
https://www.acmicpc.net/problem/12100moveBoard(direction) 함수에 대한 이해를 돕기 위한 블로그 (https://jellyinghead.tistory.com/53)Time : O(N^2)Space : O(N
[ BOJ / Python ] 12919번 A와 B 2
이번 문제는 백트레킹을 통해 해결하였다. 처음에는 s에 두가지 연산을 계속해서 적용해보는 백트레킹을 구현하였다. 값은 정확하게 도출되었지만 시간초과가 발생하였다. 그래서 이번에는 t에 두가지 연산의 반대 연산을 계속해서 적용하는 백트레킹을 구현하였다. 이 경우에는 t의
백트래킹(Back Tracking)
❗유투브 채널 "코드없는 프로그래밍"의 코딩테스트, 기초, 백트래킹 backtracking 소개를 공부하며 정리한 내용입니다.➡️ 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법🟡 DP Array와 DP Table을 이용하여 중복 연산을 줄
[ BOJ / Python ] 1941번 소문난 칠공주
이번 문제는 백트레킹을 통해 가능한 좌표들의 조합을 구하고, 해당 조합을 순회하며 연결되어 있는지 DFS를 통해 확인하도록 하였다. 조합을 구할 때에는 조합 하나가 완성 되었을 때, S가 4개 이상 존재하지 않으면 추가하지 않도록 하여 갯수를 줄였다.
[ BOJ / Python ] 19236번 청소년 상어
이번 문제는 삼성 기출 문제로, 상어의 이동에 대한 모든 경우를 백트레킹을 통해 구하여 그 중 가장 큰 값을 정답 변수에 저장하는 문제였다. 우선 크게 물고기의 이동과 상어의 이동, 이렇게 2개의 함수로 나눠서 정의하였다.물고기의 이동의 경우에는 물고기의 방향을 반시계
[BOJ] 15686 치킨 배달
https://www.acmicpc.net/problem/15686아이디어딱 보고 단순구현 문제인 줄 알고 풀려고 했는데 back tracking 유형이었다.
[ BOJ / Python ] 15683번 감시
이번 문제는 삼성 기출 문제로 백트레킹과 구현을 통해 해결하였다. 처음에 백트레킹을 생각했지만, 브루트포스로도 해결이 가능할 것이라 생각하였고, 브루트포스로 구현을 하였다. cctv의 위치와 종류를 튜플로 하여 cctvs리스트에 담고, 이를 종류의 내림차순으로 정렬한
[ BOJ / Python ] 17142번 연구소 3
이번 문제는 삼성 기출 문제로, 재귀를 통해 활성화 바이러스의 combinations를 구하고, combinations를 순회하며 해당 위치에서 바이러스가 퍼지는 과정을 BFS를 이용하여 구현하였다. 바이러스가 퍼지는 시간은 방문처리 리스트에 카운팅하는 방식으로 진행하
[ BOJ / Python ] 16198번 에너지 모으기
이번 문제는 주어진 조건대로 백트레킹을 진행하며 모든 경우를 구하고, 그 중 가장 큰 경우를 구하는 방식으로 해결하였다. x-1, x+1 인덱스의 원소의 곱을 에너지로 더하기 위해서 구슬 리스트를 지우기 전에 해당 값들을 미리 저장하고, x위치의 원소를 지운 후, 재귀
[ BOJ / Python ] 10819번 차이를 최대로
이번 문제는 백트레킹을 이용하여 풀이하였다. 처음에는 수열에 중복된 수가 없을 것이라 생각하고 풀이하여 값에 대한 중복 처리를 하여 틀렸다. 중복된 수가 존재할 가능성을 생각하여, 선택된 수들의 인덱스를 따로 저장하고, 이에 대한 중복 처리를 하여 해결할 수 있었다.n
백준 #9663 N-Queen (파이썬)
백트래킹의 가장 대표격 문제라 할 수 있는 N-Queen 문제다. 너무 클리셰고 최적화 기법도 많이 들어있으니, 시간 나면 외우자.
[BOJ] 14889 스타트와 링크
https://www.acmicpc.net/problem/14889problem요즘 문제가 잘 풀린다 \~~
[BOJ] 1182 부분수열의 합
https://www.acmicpc.net/problem/1182Problem아이디어Backtacking으로 풀 때, backTracking()에 for문을 하나 더 둬서 현재 위치 기준 다음 인덱스부터 탐색하도록 구현하였는데(pruning) 반례가 존재하여
[BOJ] 1759 암호 만들기
https://www.acmicpc.net/problem/1759problem아이디어처음에는 idx부터 for문을 돌릴 생각을 못하고 isPromising() 함수를 따로 만들어서 너무 복잡해졌다.Back tracking 알고리즘을 사용할 때, 빈 root n
[ BOJ / Python ] 3980번 선발 명단
이번 문제는 백트레킹을 통해 해결하였다. 가능한 결과값을 백트레킹을 통하여 모두 구한 후에 그 중에서 가장 큰 값을 출력하도록 하였다. 방문 처리는 해당 포지션이 선발된 것과 같은 의미로 사용되었기 때문에 1차원 리스트로 구현하였다. 모든 포지션이 선발되게 되면 idx
BOJ :: 도도의 음식 준비 (no.22953)
도도는 주방장이다. 총 K$K$개의 요리가 준비되는 최소 시간을 구해야 한다.각각의 요리사는 자신만의 음식 조리 시간이 있다. 음식 조리 시간은 음식 하나를 만들 때 걸리는 시간이다.도도는 요리사에게 격려를 해줄 수 있다. 격려받은 요리사는 영구적으로 음식 조리 시간이
[ BOJ / C++ ] 15665번 N과 M (11)
이번 문제는 백트레킹 알고리즘을 활용하여 해결하였다. 문제의 조건없이 출력하는 것은 쉽지만 같은 수를 여러 번 골라도 되지만 길이M의 수열끼리는 중복을 허용하지 않는다는 조건에서 생각이 필요했다.bool형 num_chk 배열을 통해 입력된 값이 존재하는지 확인한다.만약