개발왕 양선규

2019 카카오 개발자 겨울 인턴십에 출제된 백트래킹 문제이다.주어지는 입력값의 크기가 크지 않아, 완전탐색으로도 풀린다고 들었지만 백트래킹이 정석인 문제라고 생각한다. def solution(user_id, banned_id): def is_match(user, banned_user): if len(user) != len(banned_user): return False for i in range(len(user)): if banned_user[i] != '*' and banned_user[i] != user[i]: return False return True ..

기본적인 백트래킹 문제이다.주어진 집합에서 6개 숫자의 조합(순서가 다른 같은 숫자를 중복으로 간주)을 구해야 한다. # 실버2 -> 백트래킹import sysinput = sys.stdin.readlinedef back_tracking(depth, start, result):    # 6개의 숫자가 모이면 출력    if depth == 6:        print(*result)        return        for i in range(start, len(S)):        result.append(S[i])        back_tracking(depth + 1, i + 1, result)        result.pop()while True:    K, *S = map(int, input..

DFS, 백트래킹 문제이다. 상하좌우 탐색을 요하기 때문에 BFS로도 잠시 생각했었으나 백트래킹이 필요했기에 DFS로 진행했다. 어느정도 정석에 가까운 백트래킹 문제 같다. # DFS, 백트래킹import sysinput = sys.stdin.readline# 입력받기R, C = map(int, input().split())board = []for _ in range(R):    board.append(list(input().strip()))# 사전준비directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]visited = [[False] * C for _ in range(R)]visited[0][0] = Truepath = set() # 집합으로 불필요한 중복 알파벳이 들어..

BFS, 백트래킹 문제이다. 거창한 백트래킹.. 이라기 보다, 그냥 모든 경우의 수를 찾기 위한 부분에서 백트래킹이 사용되었다. BFS가 메인이고 백트래킹은 거드는 느낌의 문제이다. # BFS, 백트래킹# 백트래킹으로 벽 3개를 세우는 경우의 수를 전부 구한 후, BFS로 바이러스를 전파시킨 후 안전 영역의 개수를 센다from collections import dequeimport sysimport copyinput = sys.stdin.readlineN, M = map(int, input().split()) # 행, 열graph = [] # 지도for _ in range(N):    graph.append(list(map(int, input().split())))dx = [-1, 1, 0, 0]dy =..

import sysinput = sys.stdin.readlineN = int(input()) # 부등호 개수boo = list(input().split()) # 부등호 리스트result = []visited = [False] * 10 # depth는 숫자 개수만큼def compare(a, b, op):    if op == '>':        if a b: return False    elif op == ':        if a > b: return False    return True# 깊이, 현재숫자(문자열)def backTracking(depth, num):    # 숫자가 완성되었다면 결과 리스트에 추가    if depth == N + 1:        result.append(num) ..

기본 3대중량은 500이다.매일매일 중량은 K 씩 감소한다.매일매일 하나의 운동 키트를 사용하여 중량을 증가시킬 수 있다. 3대중량이 단 하루도 500 미만으로 내려가지 않도록, 운동 키트를 사용하는 순서의 경우의 수를 모두 찾기 결국 중량의 변화는 (K + 키트로 인한 중량 증가량) 이므로, 입력받은 배열에서 미리 K를 빼 주었다.중량 변화가 음수일 경우 500 미만으로 내려가는 것 이므로, 중량 변화량이 N일동안 계속해서 양수인 경우의 수를 찾으면 된다. import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.StringTokenizer;public class 근손실_18429 {        // 결과 저장할 변..

스택(Stack) - 후입선출(Last In First Out) 구조 - 마지막에 들어온 데이터가 가장 먼저 나간다 - 파이썬에서는 리스트와 pop(), append() 메소드로 스택을 구현할 수 있다 큐(Queue) - 선입선출(First In First Out) 구조 - 먼저 들어온 데이터가 가장 먼저 나간다. “공정한 자료구조” - from collections import deque 사용해서 deque 자료구조를 활용하는 게 좋다 - deque는 스택, 큐의 장점을 모두 채택한 것인데 리스트에 비해 빠르고 queue 라이브러리를 이용하는 것 보다 간단하다 - append(), popleft()를 이용하여 큐를 구현할 수 있다 DFS(Depth-First Search, 깊이 우선 탐색) - 그래프에..

n = int(input()) pos = [0] * n # 퀸 위치 담을 리스트 flag_heng = [False] * n # 행 배제 flag_a = [False] * ((n-1) * 2 + 1) # 우상향 대각 배제 flag_b = [False] * ((n-1) * 2 + 1) # 좌상향 대각 배제 count = 0 # 경우의 수 def set(i): global count for j in range(n): if not flag_heng[j] and not flag_a[i + j] and not flag_b[(n-1) + i - j]: # 행 , 대각, 대각 안전할 때 pos[i] = j # i번째 열의 j번째 행에 퀸을 둔다 if i == n - 1: # 마지막 열까지 n개의 퀸을 뒀을 때, 즉 경..