본문 바로가기

Algorithm/DFS&BFS&백트래킹&재귀52

[백준] 10872번 팩토리얼 사용 언어 - Python3 10872번: 팩토리얼 (브론즈5, 재귀) 문제 ★재귀 문제★ 10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net 정답 재귀 함수 또는 for문으로 처리하기 (코드 풀이) 1. 정답1 - 재귀함수 def factorial(n) 재귀함수 정의하기 n이 0보다 클때만 result = n*factorial(n-1) # 정답1 n = int(input()) def factorial(n): result = 1 if n > 0 : result = n * factorial(n-1) return result print(factorial(n)) 2. 정답2 - for문 n이 0보다 클때만 i를 한개씩 증가.. 2023. 1. 23.
[백준] 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.
[백준] 2339번 석판 자르기 사용 언어 - Python3 2339번: 석판 자르기 (골드1, DFS 백트래킹 문제) 문제 ★분할 정복 문제★ 2339번: 석판 자르기 첫 번째 줄에는 석판의 크기 N(1 ≤ N ≤ 20)이 들어온다. 다음 줄부터 N줄에 걸쳐서 석판의 상태가 입력으로 들어온다. 여기서 1은 불순물을 의미하며, 2는 보석 결정체, 0은 불순물과 보석결정체가 www.acmicpc.net 정답 석판을 자를 수 있을 때까지 분할하는 "분할 정복" 알고리즘 (백준에서 정답자의 풀이를 보고 이해했습니다) x의 start, end 범위 설정 sx, ex y의 start, end 범위 설정 sy, ey #정답 def f(sx, sy, ex, ey, hv): noise = [] #불순물 dia = 0 #보석결정체 for i in ra.. 2023. 1. 18.
[백준] 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.
[백준] 2667번 단지번호붙이기 사용 언어 - Python3 2667번: 단지번호붙이기 (실버1, DFS 문제) 문제 ★코테 자주 등장하는 DFS 문제★ 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 정답 DFS 재귀함수 (정답 풀이) 1. dfs 함수 정의 1.1. 1 값인 x,y 좌표 찾기 x,y가 N*N 정사각형 범위 안에 없다면 return해준다. N*N 정사각형 범위 안에 속해있다면, 1이 있는 좌표 x,y를 찾는다. 개수를 한개씩 더해주면서 1이 있는 총 개수를 카운트한다. (count+=1) 방문한 좌표는 0으로 만들어 방문했다.. 2023. 1. 17.

티스토리툴바