시나위

1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 문제 요약 동전이 보드 위에서 움직일 수 있는 최대횟수 구하기 접근 1. 생각의 흐름 1 - BFS 보드가 이차원이고 모든 방향을 탐색하면서 최대로 움직이는 횟수를 파악해야하므로 그래프 탐색중 BFS를 사용해야할 것 같았다. BFS는 특정 지점까지의 최소 거리를 구할 때 사용하는데 이 경우에서도 충분히 사용할수 있을 거라고 생각했다. (멈추는 지점까지의 최소 거리를 구하면 최대로 움직인 거리를 구하는 거랑 같을 거니까) 간단하게 적어보면 다음과 같다. (0,0)..

https://programmers.co.kr/learn/courses/30/lessons/1835 코딩테스트 연습 - 단체사진 찍기 단체사진 찍기 가을을 맞아 카카오프렌즈는 단체로 소풍을 떠났다. 즐거운 시간을 보내고 마지막에 단체사진을 찍기 위해 카메라 앞에 일렬로 나란히 섰다. 그런데 각자가 원하는 배치가 모두 programmers.co.kr 꽤 오래 걸린 문제이다. 우선 어떻게 풀어야할지 감이 안왔다. 처음 문제를 봤을때 순열을 구하는 공식을 사용해서 만들어야하나 고민했다. 하지만 level 2에서 그런 문제가 나올리가 없다고 생각해서 다른 방법을 생각했다. 물론 공식을 사용해서 풀수만 있으면 훨씬 빠르게 끝낼수 있었겠지만 범위가 있어서 공식은 아니라고 판단헀다. 오랫동안 고민했는데 도저히 떠오..

https://www.acmicpc.net/problem/1311 1311번: 할 일 정하기 1 N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명 이어야 한다. 또한, 모든 사람은 모든 일을 할 능력이 있다. 사람은 1번부터 N번까지 번호가 매 www.acmicpc.net 어제와 이어서 비트마스크를 사용한 동적 계획법을 공부했다. 문제만 보면 모든 조합 만들어서 최솟값을 찾으면 된다. 그러면 완전탐색이나 백트래킹을 사용해서 탐색을 하면 모든 조합을 찾을수있다. 하지만 N의 최댓값이 20이므로 20^20 이나 20!은 매우 큰 숫자이므로 다른 방법을 찾아야한다. 완전 탐색을 하다보면 항상 겹치는 부분이 생기게 되는데 이때의 값들을 저장하고 일반적인 값을..

https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net import sys; input = sys.stdin.readline sys.setrecursionlimit(10**7) n = int(input()) nums = [0]+[int(input()) for _ in range(n)] visit = [False] * (n+1) finish = [False] * (n+1) result = [] def dfs(node): global resu..

import sys; input = sys.stdin.readline sys.setrecursionlimit(10**7) def dfs(node): global result visit[node] = 1 cycle.append(node) stu = st[node] if visit[stu]: if stu in cycle: result += cycle[cycle.index(stu):] return dfs(stu) for tc in range(int(input())): n = int(input()) st = [-1] + list(map(int, input().split())) visit = [False] * (n + 1) result = [] for i in range(1, n+1): if not visit[i..

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net import sys; input = sys.stdin.readline def sum_arr(array): ret = 0 for i in range(N): for j in range(M): ret += array[i][j] return ret def backtrack(arr, total=0, ind=0): global max_val if ind == 3: if max_val < total: max_..

www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진 www.acmicpc.net import sys input = sys.stdin.readline from collections import deque N = int(input()) s, e = map(int, input().split()) link_arr = [list() for _ in range(N + 1)] M = int(input()) for _ in range(M): n1, n2 = map(int, input().s..

www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net delta = [(-1, 0), (1, 0), (0, -1), (0, 1)] def backtrack(inboard, inred, inblue, ind=0): global result, cnt, delta # if result == 1: # return if ind == 10: return else: for i in range(4): tmp_board = [in..

www.acmicpc.net/problem/13459 13459번: 구슬 탈출 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net delta = [(-1, 0), (1, 0), (0, -1), (0, 1)] def backtrack(inboard, inred, inblue, ind=0, arr=[]): global result, delta if result == 1: return if ind == 10: return else: for i in range(4): tmp_board = [inboa..

www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net number_set = set() matrix = [list(map(int, input().split())) for _ in range(5)] delta = [(-1,0),(1,0),(0,-1),(0,1)] def backtrack(x,y, index=0, string=''): if index == 5: number_set.add(string) else: for i i..