목록백준 python 기록 (69)
작은 지식주머니

백준 링크:https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net dfs로 풀려했었는데 이해가 잘 안됐었다. 특히 예제 2번 6을 입력받았을떄 어떻게 해야하나 걱정했었는데 그냥 모든 조합을 구하면 되는거였다. dfs로 visit 값을 구하면서 cnt가 만약 n//2값이 된다면 이중 for문을 작동시켜서 서로 짝일 경우에 start와 link 따로 계산해서 abs(start-link) (절대값)으로 계산했다. n=int(input()) matrix=[] for i in ra..

백준 링크:https://www.acmicpc.net/problem/2529 2529번: 부등호 여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력 www.acmicpc.net 처음부터 끝까지 조건에 맞는 경우를 새는 브루트포스 and 백트레킹 문제인데 부등호를 어떻게 넣나 한참을 생각을 하고 결국 모르겠어서 다른 분들이 푼 해결법으로 해결했다. n=int(input()) string=list(map(str,input().split())) nums=[0]*10 min_value="" max_value="" def check(i,j,k): if k == '

백준 링크:https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 이분 탐색 문제. 다만 카운트를 어떻게 해야 하는지 좀 고민했다가 그냥 이분탐색 알고리즘 의 start , end부분까지 검색하기로함 import sys input = sys.stdin.readline def binary_search(i,s_n,start,end): if start > end: return 0 mid = (start + end) // 2..

백준 링크:https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net DFS 브루트포스로 해결했음. PYPY로 제출함. import sys n=int(input()) s=[list(map(int,sys.stdin.readline().split())) for i in range(n)] min_value = sys.maxsize visited=[False for _ in range(n)] def dfs(start,..

백준 링크:https://www.acmicpc.net/problem/10451 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 문제가 뭔말인지 조금 햇갈려서 고생했다. 간단한 dfs문제였는데ㅜㅜ dfs를 사용해서 카운트 숫자를 하나씩 늘려주었다. 다만 sys.setrecursionlimit를 안하면 오류가 나기때문에 대충 100만정도 설정했다. import sys sys.setrecursionlimit(1000000) input = sys..

https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 배열 전체를 탐색하면서 첫 체크와 다른숫자가 나오면 9등분시켜서 재귀로 탐색한다. import sys n=int(input()) s=[list(map(int,sys.stdin.readline().split())) for i in range(n)] minus=0 zero=0 one=0 def search(x,y,n): global minus,zero,one check=s[x][y] for..

백준 링크:https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 최단거리를 계산하므로 BFS를 사용하면 간단히 해결 가능하다. 다만 배열 전부의 BFS를 구하면 많은 시간이 걸리므로 내가 원하는 배열에 도착하면 BFS를 종료시켜야한다. from collections import deque TC=int(input()) for i in range(TC): n= int(input()) matrix=[[0]*n for _ in range(n)] a,b=map..

백준 링크:https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 미로 탐색과 비슷한 유형의 BFS문제이다. 처음에는 시간 초과가 나오길래 뭔가 잘못되었다 생각했는데. 처음 배열 지정할때 1이 여러개있으면 QUEUE에 있는 수를 꺼내는데 많은 시간이 걸리기 떄문에 DEQUE를 사용해 시간 단축을 하였다. import sys from collections import deque n,m=map(int,input().split()) queu..