본문 바로가기

백준 백트래킹8

[백준] 14889번 스타트와 링크 사용 언어 - Python3 14889번: 스타트와 링크 (실버2, DFS 백트래킹 문제) 문제 ★백트래킹 문제, 삼성 SW 역량 테스트 기출 문제 ★ 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 정답 DFS 백트래킹 재귀함수 조합 문제 !! 다른 분들 답중에 가장 좋다고 생각하는 풀이법 2가지로 공부했습니다. 맨 아래에 링크를 올립니다! 1. 방문 여부에 따라 팀 지정하는 방법 1팀은 2팀이 방문하지 않은 곳, 2팀은 1팀이 방문하지 않은 곳으로 생각한다. visited[i]를 순차적으로 방문해서 visited를 True로 해.. 2023. 1. 20.
[백준] 14888번 연산자 끼워넣기 사용 언어 - Python3 14888번: 연산자 끼워넣기 (실버1, DFS 백트래킹 문제) 문제 ★백트래킹 문제, 삼성 SW 역량 테스트 기출 문제★ 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 정답 DFS 백트래킹 재귀함수 조합 문제 !! 다른 분들 답중에 가장 좋다고 생각하는 풀이법으로 공부했습니다. 맨 아래에 링크를 올립니다! 1. maximum, minimum 지정 결과값을 출력할 때 결과값은 항상 -10억보다 크거나 같고, 10억보다 작거나 .. 2023. 1. 19.
[백준] 2580번 스도쿠 사용 언어 - PyPy3 2580번: 스도쿠 (골드4, DFS 백트래킹 문제) 문제 ★백트래킹 문제★ 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 정답 DFS 백트래킹 재귀함수 조합 문제 !! 다른 분들 답중에 가장 좋다고 생각하는 풀이법으로 공부했습니다. 맨 아래에 링크를 올립니다! 1. 전체 숫자를 모두 확인하면 재귀함수가 너무 많이 필요하기 때문에 답을 구해야하는 0인 부분만 찾는다. zeros = [(i,j) for i in range(9) for j in range(9) if sudoku[i][j.. 2023. 1. 19.
[백준] 9663번 N-Queen 사용 언어 - PyPy3 9663번: N-Queen (골드4, DFS 백트래킹 문제) 문제 ★백트래킹 문제★ 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 정답 DFS 백트래킹 재귀함수 조합 문제 !! (아래 그림 참고) 1. DFS nqueen() 행(x)이 고정되어 있을 때 열(i)를 하나씩 증가시켜준다. (0,0) -> (0,1) -> (0,2) -> (0,3) 조건을 만족해서 퀸을 두려고 한다면, row[x] = i 로 (x,y)에 퀸의 위치를 저장해야한다. 모든 열에 테스트를 완료했으면, 행을 한개 증가시켜 다시 .. 2023. 1. 19.
[백준] 15652번 N과 M(4) 사용 언어 - Python3 15652번: N과 M(4) (실버3, DFS 백트래킹 문제) 문제 ★LG CNS 21년 상반기 코테랑 유사★ 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 정답 DFS 백트래킹 재귀함수 조합 문제 !! 15649,15450,15651,15652번은 세트로 공부 아래 백트래킹 문제 링크를 첨부합니다. 15450번과 15652번을 적절히 조합하는 문제이다. 중복을 제거하는 if문을 없애고, start 지점을 활용한다. 현재 i가 ans에 있을 때, i부터 N까지를 for문으로 차례.. 2023. 1. 18.
[백준] 15651번 N과 M(3) 사용 언어 - Python3 15651번: N과 M(3) (실버3, DFS 백트래킹 문제) 문제 ★LG CNS 21년 상반기 코테랑 유사★ 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 정답 DFS 백트래킹 재귀함수 조합 문제 !! 15649,15450,15651,15652번은 세트로 공부 아래 백트래킹 문제 링크를 첨부합니다. 중복도 허용하는 모든 가능한 수열을 뽑는 문제이다. 15651번에서 중복이 가능하게만 해주면 된다. if i not in ans: 제거 # 정답 N, M = map(int,input.. 2023. 1. 18.
[백준] 15650번 N과 M(2) 사용 언어 - Python3 15650번: N과 M(2) (실버3, DFS 백트래킹 문제) 문제 ★LG CNS 21년 상반기 코테랑 유사★ 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 정답 DFS 백트래킹 재귀함수 조합 문제 !! 15649,15450,15651,15652번은 세트로 공부 아래 백트래킹 문제 링크를 첨부합니다. (정답 풀이) 15649번에서 start 포인트만 지정해주면 되는 문제 똑같은 구조로 back() 함수를 진행하지만, 다음 재귀함수를 시작할 때 start 포인트를 한개씩 증가시켜준.. 2023. 1. 18.
[백준] 15649번 N과 M(1) 사용 언어 - Python3 15649번: N과 M(1) (실버3, DFS 백트래킹 문제) 문제 ★LG CNS 21년 상반기 코테랑 유사★ 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 정답 DFS 백트래킹 재귀함수 문제 !! 15649,15450,15651,15652번은 세트로 공부 아래 백트래킹 문제 링크를 첨부합니다. (정답 풀이) [1] -> [1,2] -> [1] -> [1,3] -> [2] -> [2,1] -> [2] -> [2,2] ->.... 1. N=3, M=3을 리스트 형태로 입력받는다. .. 2023. 1. 17.

티스토리툴바