본문 바로가기

전체 글94

[미완] 백준 9373 복도뚫기: 크루스칼 (python, 파이썬) 1. 문제 https://www.acmicpc.net/problem/9373 9373번: 복도 뚫기 각 테스트 케이스마다 센서에 감지되지 않고 복도를 지나갈 수 있는 원형 물체의 최대 반지름을 부동소수점 실수로 한 줄에 출력한다. 물체는 매우 정밀하게 움직일 수 있다고 가정한다. 만약 www.acmicpc.net 2. 풀이 1. 벽을 heap에 넣는 것이 어려웠다. 왼쪽 벽에 모든 원에 대해 수직으로 꽂아 dist를 측정. 음수는 벽과 원을 잇고, 그렇지 않은 경우 가장 짧은 dist를 heap에 넣었다. 오른쪽도 마찬가지. 2. 시간초과가 나오는데 pypy3 정답 코드를 python으로 제출해도 시간초과가 나오기 때문에, 우선은 넘어가려고한다. 3. 구현 import sys import heapq sy.. 2021. 7. 5.
[백준 2887] 행성 터널: 크루스칼 (python, 파이썬) 1.문제 https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 2.풀이 O(N^2)으로 풀리지 않는다. 각 차원마다 정렬하고, 가까이 있는 행성들끼리의 거리를 heap에 넣어준다. 될까 싶지만 되는 꿀팁 문제인 것 같다. 3.구현 import sys import heapq sys.stdin = open("input.txt") N = int(sys.stdin.readline()) lis=[] for i in range(.. 2021. 7. 4.
[백준 4343] Arctic Network 번역 : 크루스칼 정답코드 (python, 파이썬) https://www.acmicpc.net/problem/4343 4343번: Arctic Network The first line of input contains N, the number of test cases. The first line of each test case contains 1 2021. 7. 3.
[백준 4386] 별자리 만들기: 크루스칼 파이썬, python 1. 문제 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 2. 풀이 어려웠던 부분은 별이 2차원인데 1차원의 parent에 어떻게 표시하나였다. 1번 별(예: 1.0 1.0)을 0 번, 2번 별을 1번... 이런 식으로 쌍을 맞추면 된다. 또 수학적인 표현도 기억하기. parent=[i for i in range(n+2)] stars = [list(map(float, sys.stdin.readline().split())) for _ in ran.. 2021. 7. 3.
[파이썬 에러] invalid literal for int() with base 10: '1.0' 1. 방법: 문자형을 정수형으로 바꿀 때, 실수형 문자열을 받으면 나는 에러 (x,y)=(1.0,3.0) x, y = map(int, sys.stdin.readline().split()) >> invalid literal for int() with base 10: '1.0' 에러발생 2. 해결: int 형을 float로 바꾼다. x, y = map(float, sys.stdin.readline().split()) 2021. 7. 3.
[백준 1647] 도시 분할 계획: 크루스칼 (python, 파이썬) 1. 문제 https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net 2. 풀이 두 개로 분리한다는 것은 최소한으로 연결 한 후 가장 cost가 높은 노드를 하나 제거한다는 것이다. 3. 구현 import sys import heapq # sys.stdin = open("input.txt") N,M = map(int, sys.stdin.readline().split()) edges=[] parent=[i for i i.. 2021. 7. 3.
백준 6497번 : 전력난, 50% 에서 런타임 에러나는 경우 (python, 파이썬) 1. 문제 https://www.acmicpc.net/problem/6497 6497번: 전력난 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들 www.acmicpc.net 2. 풀이 와 이거 진짜.. input 에서 문제가 있다. 크루스칼만 연습하는거라면 50%까지만 봐도 될 것 같다. 50% 에서 런타임에러가 나는 경우를 해결하고 싶으면.. input에 대해 설명을 하자면, 이 부분이 문제가 된다. 우선 테스트 케이스는 다음과 같이 주어졌는데, 쉽게 생각해서 계속 받다가 0,0가 나오면 end flag이구나.. 2021. 7. 3.
백준: 네트워크 python 파이썬 1. 문제 https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 2. 풀이 크루스칼 알고리즘의 풀이: 1. 간선을 cost 기준으로 오름차순(작->큰) 정렬 2. 연결이 안되어있으면 union + weight추가 3. 간선 v-1개가 연결되면 종료 (이번 문제에선 3번 제외) 3. 구현 import sys import heapq # sys.stdin = open("input.txt") n = int(sys.stdin.readline()) edge = int(sys.stdin.readline()) edges=[] parent=[i for i.. 2021. 7. 3.
프로그래머스: 순위 python, 파이썬 1. 문제 https://programmers.co.kr/learn/courses/30/lessons/49191# 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 2. 풀이 이 분의 아이디어를 읽고 구현했다. 내 언어로 설명해보자면, 1) 주어진 값 넣기: 먼저 n*n 배열을 만들고, 배열[이긴사람][진사람]에 1(이김) 배열[진사람][이긴사람]에 -1 짐을 넣는다. 여기서 중요한 건 몇등이냐가 아니라 모든 다른 사람에 대해 내 결과를 가지고 있는 사람이 몇사람이냐는 것이다. 2) 배열을 채운다: 이제 배열을 순회하면서 A가 B를 이겼다면 B에게 진 사람들은 A에게 모두 졌을 것이라고 생각하고 이것을 채워넣는다. 마.. 2021. 7. 3.
프로그래머스: 가장 먼 노드 python, 파이썬 1. 문제 https://programmers.co.kr/learn/courses/30/lessons/49189#qna 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 2. 풀이 bfs 3. 구현 from collections import deque def solution(n, edge): answer = 0 dic={} for s,e in edge: if s in dic: dic[s].append(e) else: dic[s]=[e] if e in dic: dic[e].append(s) else: dic[e]=[s] q=deque() visit = {} dist=0 q.appen.. 2021. 7. 2.
프로그래머스: 네트워크 (python, 파이썬) 1.문제 https://programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 2. 풀이 연결이 되어있는 컴퓨터는 하나의 그룹으로 생각해서 같은 parent를 가지도록 한다. 각각의 컴퓨터가 연결되어있는 parent값을 가진 parent 리스트를 set으로 만들어 unique한 값을 가져온다, 다만 여기서는 parent를 완전히 찾아가지 않은 값이 들어있을 수 있으므로 마지막으로 parent값을 채워주는 작업을 한다. 3. .. 2021. 7. 2.
[미완] 프로그래머스: 여행경로 ( python, 파이썬 ) 1. 문제 https://programmers.co.kr/learn/courses/30/lessons/43164# 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr 2. 풀이 생각나는 대로... bfs 구현해서 모든 경우를 다 살펴보고 각 경우마다 그때의 answer list와 cnt_dic(중복된 숫자를 셈)을 가져와서 구현한다. 3. 구현 1. dict에서 특정 value 제거할 때 dic['key'].remove(val) 2. TypeError: object of type.. 2021. 7. 2.
반응형

티스토리툴바