본문 바로가기

알고리즘

 (305)
[백준] 4386번 : 별자리 만들기 4386번: 별자리 만들기 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 🤔 문제분석 간선의 개수를 작은 것부터 하나씩 그려나아가면서 가장 짧은 간선으로 모든 노드를 연결 할 수 있는 방법은 최소신장트리이다. 최소신장 트리를 구현하기위해서 유니온-파인트 자료구조를 활용하여 문제를 해결한다. 💻 코드 import sys from math import sqrt input = sys.stdin.readline def get_distance(y1, x1, y2, x2): y = pow(abs(int((y1*100 -..
[백준] 1963번 : 소수경로 1963번: 소수 경로 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 🤔 문제분석 모든 숫자를 대입해보면서(완전탐색) 소수이고 방문하지 않는 소수만 방문해(너비우선탐색)나아가면서 문제를 해결하면 된다. 4자리 숫자이기 때문에 시간내에 문제를 해결 할 수 있습니다. 참고 : 소수를 판별하는 방법은 제곱근의 수 + 1 만큼만 비교하면 된다. (에라토스테네스의 체) 💻 코드 import sys input = sys.stdin.readline from collections import deque def is_prime(nu..
[백준] 6593번 : 상범 빌딩 6593번: 상범 빌딩 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 🤔 문제분석 3차원 배열에서 너비우선탐색을 이용하면 된다, 가로,세로,높이를 입력받고 갈수 있는 방향은 6가지로 모든 경우의수를 너비우선탐색으로 방문해가면서 도달 할 수 있는지 체크하면 된다. 💻 코드 import sys from collections import deque input = sys.stdin.readline moves = [(0, 0, 1), (0, 1, 0), (1, 0, 0), (0, 0, -1), (0, -1, 0), (-1..
[백준] 2458번 : 키 순서 2458번: 키 순서 🤔 문제분석 플로이드 워셜로 문제를 접근하면 됩니다. s에서 g로 갈 수 있는 경로가 존재한다는것을 모두 파악한 뒤에 해당 그래프가 다른 그래프와 모두 연결되어있는지 확인하면 됩니다. 💻 코드 import sys input = sys.stdin.readline N, M = map(int,input().split()) arr = [[0] * (N+1) for _ in range(N+1)] for _ in range(M): small, big = map(int,input().split()) arr[big][small] = 1 for k in range(1,N+1): for s in range(1,N+1): if k==s: continue for g in range(1,N+1): if g..
[백준] 17822번 : 원판 돌리기 17822번: 원판 돌리기 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net 🤔 문제분석 원판을 구성하는걸 배열로 생각하여 문제를 해결하면 쉽게 해결 할 수 있습니다. i좌표는 첫번째와 마지막 좌표를 비교하지 않아야하고, i일때 (i+1, i-1) 만 비교하면된다. j좌표는 j가 0일때 M-1를 확인해야하고 j가 M-1일때 0을 확인해야하고 또한 j일때 (j+1, j-1) 확인해야한다. 위의 논리라면 filter 함수를 구현하였는데 filter는 x값을 -1이나 M으로 넘어가면 M-1, 0으로 치..
[백준] 1865번 : 웜홀 1865번: 웜홀 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 🤔 문제분석 밸만포드로 문제를 해결할 수 있습니다. 어떠한 노드에서 출발해도 상관이 없기때문에 1번 노드에서 출발 하여 문제를 해결하였습니다. 💻 코드 import sys input = sys.stdin.readline TC = int(input()) def bellman_ford(start): distance = [INF for _ in range(N+1)] distance[start] = 0 for n in range(N): f..
[백준] 1613번 : 역사 1613번: 역사 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 🤔 문제분석 위상정렬과 플로이드 워셜로 풀 수 있는 문제입니다. 저는 처음에 문제를 풀때 위상정렬로 접근하였습니다. 위상정렬을 할때에 **부모노드를 자식노드에 업데이트(부모노드는 자식노드에게 내가 너보다 먼저 야 라고 표시)**하면서 자기자신을 방문할때 자기자신을 추가하면 됩니다. 💻 코드 import sys input = sys.stdin.readline INF = sys.maxsize n, k = map(int, input().spl..
[백준] 4179번 : 불! 4179번: 불! 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net 🤔 문제분석 불, 지훈 순으로 큐에 넣고 너비우선탐색을 하여 지훈이 그래프의 끝자락에 도착 할 수 있는 거리 + 1을 계산해주면된다. 만약, 불이 지훈이를 가로막는다면 지훈이는 갈 수 없다. 💻 코드 import sys input = sys.stdin.readline from collections import deque R, C = map(int, input().split()) table = [] queue = deque() j..

티스토리툴바