프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 전형적인 탐색 문제.DFS/BFS를 활용해서 풀 수 있다. DFS 풀이 코드import syssys.setrecursionlimit(int(1e9)) dx = [-1, 1, 0, 0]dy = [0, 0, 1, -1]foods_sum = 0def dfs(x, y, visited, maps): global foods_sum n = len(maps) m = len(maps[0]) visited[x][y] = True # 방문 처리 foods_sum += int(maps[x][y]..
dfs
https://www.acmicpc.net/problem/1926 DFS # 1926번: 그림(DFS)import syssys.setrecursionlimit(10**6)cnt = 0 # 그림의 개수max_area = 0 # 가장 넓은 그림의 넓이n, m = map(int, input().split())visited = [[False]* m for _ in range(n)]arr = []for _ in range(n): arr.append(list(map(int, input().split())))dx = [0, 0, 1, -1]dy = [1, -1, 0 , 0]def dfs(x, y): visited[x][y] = True global area for i in range(4):..
9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 대표적인 백트래킹 문제다. 퀸을 2차원 리스트 체스판에 놓을 수 있는 경우는 다음과 같다. 1. 이전까지 놓은 퀸들이 같은 행에 없는 경우 2. 현재 놓으려는 퀸의 이전 대각선에 퀸이 위치하지 않는 경우 그래서 1번, 2번 조건을 각각 만들어줬다. # 9663번: N-Queen n = int(input()) visited = [[False] * (n+2) for _ in range(n+2)] visited_row = [False] * (n+2) # 1~n번 행에 퀸이 놓였는지 ..
16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 백트래킹 문제다. 계란으로 계란을 쳐서 최대 몇 개의 계란을 깰 수 있는지 맞추는 문제다. 조건은 다음과 같다. 일렬로 놓여 있는 n개의 계란에 대해 왼쪽부터 차례대로 들어서 한 번씩만 다른 계란을 쳐 최대한 많은 계란을 깨면 된다. 1. 가장 왼쪽의 계란을 든다. 2. 손에 들고 있는 계란으로 깨지지 않은 다른 계란 중 하나를 친다. 단, 손에 든 계란이 깨졌거나 깨지지 않은 다른 계란이 없으면 치지 않고 넘어간다. 이후 손에 든 계란을 원래 자리..
1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 이 문제는 이전에 itertools 라이브러리의 combination함수를 사용해서 풀었던 문제다. 근데 백트래킹으로도 풀 수 있다고 해서 백트래킹으로 다시 풀어봤다. # 1759번: 암호 만들기 l, c = map(int, input().split()) arr = sorted(list(input().split())) vowels = ['a', 'e', 'i', 'o', 'u'] # 모음 result = [] visited = [False] * c def is_pos..
6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 백트래킹 문제다. 1~45까지의 숫자 중 6보다 큰 N개의 숫자를 고른다. 고른 N개의 숫자 중 6개를 고르는 경우의 수를 모두 출력하면 되는 문제. N과M 문제중, 중복되지 않고, 오름차순으로 숫자를 출력하는 경우와 동일한 문제라고 생각했다. # 6603번: 로또 import sys input = sys.stdin.readline def backTracking(num): if len(result) == 6: print(*result) return f..
1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net N개의 정수가 주어질 때, 크기가 양수인 부분수열 중 해당 부분수열의 합이 S가 되는 경우의 수를 구하는 문제. 문제의 설명이 약간 부족한 면이 있는 것 같다. 만약 N개의 정수 중 같은 숫자가 주어질 경우에는 어떻게 해야 하는지 명확하게 나와있지 않다. 일단 같은 숫자도 부분 수열에 포함될 수 있다고 생각하고 문제를 풀었다. # 1182번: 부분수열의 합 n, s = map(int, input().split()) arr = ..
15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트래킹 문제다. 이번 조건은 같은 수를 여러번 골라도 되고, 비내림차순 수열이어야 한다는 것이다. 여기서 같은 수라는 것은 같은 인덱스에 있는 수를 의미한다. 그러므로 visited 리스트를 사용할 필요가 없다. 그리고 backTracking함수의 인자로 현재 탐색한 인덱스를 넘겨줘서 다음 backTracking시 for문의 시작값으로 넣어줘서 비내림차순으로 만들어준다. # 15666번: N과 M (12) n, m = map(int, input().split..
15665번: N과 M (11) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 이전 문제에서 다른 점은 중복이 허용된다는 점이다. 여기서의 중복은 수열의 중복이 아니라, 같은 인덱스의 수가 들어갈 수 있다는 것이다. # 15665번: N과 M (11) n, m = map(int, input().split()) arr = sorted(list(map(int, input().split()))) result = [] def backTracking(depth): if depth == m: print(*result) return remember ..
def 재귀함수(n): if 정답이면 : 출력 or 저장 else : 정답이 아니면 : for 모든 자식 노드에 대해서: if 정답에 유망하다면(답의 가능성이 있으면) : 자식노드로이동 재귀함수(n+1) 부모노드로 이동 혹은 유망 조건을 따로 함수로 빼줘서 구현한다. def 백트래킹(n): if 정답이면 : 출력 or 저장 else : for 모든 자식 노드에 대해 : if 유망한지확인(m) : 자식노드로 이동 백트래킹(n+1) 부모노드로 이동 def 유망한지확인(m): if 조건에 안맞으면 : return False return True # 1182번: 부분수열의 합 n, s = map(int, input().split()) arr = sorted(list(map(int, input().split())..
