개발왕 양선규

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() # 집합으로 불필요한 중복 알파벳이 들어..

DFS 문제이다. 진짜 최근에 푼 문제중 가장 어렵고 헷갈렸다.그래프의 싸이클을 찾는 문제이며, 문제만 읽고 싸이클을 찾아야 겠다는 유추를 해내기가 힘들다. 그래프로 옮기는 과정도 힘들고, 싸이클 찾는 로직도 매우 헷갈리고, 단방향인지 양방향인지, 역방향은 결과에 영향을 미치는지, 싸이클을 찾으면 해당 거쳐온 노드를 모두 추가하는 건 안되는지 판단해야 했고.. 하여튼 여러 방향으로 미치는 줄 알았다. # DFSimport sysinput = sys.stdin.readline# 입력받기N = int(input())graph = [[] for _ in range(N + 1)]for i in range(1, N + 1):    graph[i].append(int(input()))def DFS(node, sta..

DFS 문제이다. 트리가 주어지며, 각 노드는 실외/실내의 특성을 갖는다.산책 루트는 반드시 실내로 시작해서 실내로 끝나야 한다. 그 사이에 실외가 몇개 있든 상관 없다. 이러한 산책 루트가 최대 몇개인지를 출력하면 되는 문제이다. 방향만 바꾼 것도 포함이다. 1->3 , 3->1 이 루트는 별개의 루트이다.  처음엔 문제 지문 그대로 코드로 옮겨 풀었었다.import sysinput = sys.stdin.readlineN = int(input()) # 노드 개수inout = input().strip()inout = [''] + [int(x) for x in inout] # 실내여부, 노드번호와 동기화를 위해 맨앞 빈값 추가graph = [[] for _ in range(N + 1)] # 노드 연결정보,..

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 {        // 결과 저장할 변..

신장 트리(Spanning Tree) - 그래프 내의 모든 정점을 포함하면서 사이클이 없는 부분 트리 최소 스패닝(신장) 트리(Minimum Spanning Tree, MST) - 가중치가 있는 양방향 그래프에서 싸이클 없이 모든 정점을 포함하며 가중치의 합이 최소인 트리 - 모든 정점을 연결하는 트리를 형성하면서, 가중치 합이 최소화되도록 하는 것 프림(Prim) 알고리즘 - 크루스칼 알고리즘과 더불어 그리디 알고리즘을 기반으로 최소 신장 트리를 구하는 대표적인 알고리즘 - 가중치가 작은 순으로 노드를 그래프에 포함시켜야 하기 때문에 우선순위 큐를 사용한다. - 이미 그래프에 속한 노드엔 적용시키지 않기 위해 visited를 사용한다. 프림 알고리즘 동작원리 1. 임의의 시작 노드를 설정하고 T(트리)..

import sys sys.setrecursionlimit(10 ** 9) input = sys.stdin.readline # 이분 그래프 판별 DFS 함수 def DFS(graph, start, visited, group): visited[start] = group for i in graph[start]: if visited[i] == 0: # 방문 안 한 곳이라면 result = DFS(graph, i, visited, -group) if not result: return False # 하위에서 이분 그래프 아니라고 판단했다면 함수 종료 elif visited[i] == group: # 인접노드인데 그룹이 같을경우 이분그래프 아님 return False return True # 입력받은 갯수만큼 그래..

import sys input = sys.stdin.readline n = int(input()) numList = list(map(int, input().split())) add, sub, mul, div = map(int, input().split()) maxValue = -1e9 minValue = 1e9 def DFS(i, calc): global add, sub, mul, div, maxValue, minValue if i == n: # 수열의 끝에 오면 최대/최솟값 구하기, 수열번호와 인덱스번호 헷갈리지 말자. # 수열번호가 1이면 인덱스번호는 0 maxValue = max(maxValue, calc) minValue = min(minValue, calc) else: if add > 0: ad..