본문 바로가기

분류 전체보기

(402)
[백준 17387번] 선분 교차 2 (Python3) import sys input = sys.stdin.readline x1,y1,x2,y2 = map(int,input().split()) x3,y3,x4,y4 = map(int,input().split()) def eq1(x,y): return (x2-x1)*(y-y1)-(y2-y1)*(x-x1) def eq2(x,y): return (x4-x3)*(y-y3)-(y4-y3)*(x-x3) def check(): if eq1(x3,y3)*eq1(x4,y4) =min(y1,y2): return 1 elif (y4-y3)*(x2-x1) == (y2-y1)*(x4-x3): if y1-(y2-y1)/(x2-x1)*x1 == y3-(y4-y3)/(x4-x3)*x3: if max(x1,x2)>=min(x3,x4) an..
[백준 17386번] 선분 교차 1 (Python3) import sys input = sys.stdin.readline x1,y1,x2,y2 = map(int,input().split()) x3,y3,x4,y4 = map(int,input().split()) def eq1(x,y): return (x2-x1)*(y-y1)-(y2-y1)*(x-x1) def eq2(x,y): return (x4-x3)*(y-y3)-(y4-y3)*(x-x3) if eq1(x3,y3)*eq1(x4,y4) < 0 and eq2(x1,y1)*eq2(x2,y2) < 0: print(1) else: print(0) class5에 선분교차 2가 있길래 1은 어떤문제인가 궁금해서 풀어보았다. 그냥 말그대로 고등학교때 배우는 부등식의 영역 문제였다. 고딩때 배운 부등식의 영역을 기억할 수 ..
[백준 1562번] 계단 수 (Python3) 처음에는 브루트 포스 알고리즘으로 풀어보려고 했다. 숫자를 사용할때마다 check에서 각 자릿수의 개수를 +1 해주고, 재귀깊이가 10이 되면 모든 숫자가 사용되었는지 확인하는 코드이다. 코드는 다음과 같다. import sys input = sys.stdin.readline N = int(input()) result = 0 check = [0]*10 def stair(last,cnt): global result if cnt == N: success = True for i in range(10): if check[i] == 0: success = False if success: result += 1 return for i in [-1,1]: now = last+i if 9>=now>=0: check[no..
[백준 4386번] 별자리 만들기 (Python3) 도시 분할 계획과 마찬가지로 최소 스패닝 트리 문제를 풀고 나면 풀어야지 하고 묵혀놨던 문제이다. 최소 스패닝 트리 알고리즘을 공부하면 너무나 쉬운 문제 import sys input = sys.stdin.readline from math import sqrt from heapq import heappush, heappop def findparent(x): if parent[x] == x: return x parent[x] = findparent(parent[x]) return parent[x] N = int(input()) graph = [[0]*N for i in range(N)] co = [] for i in range(N): co.append(tuple(map(float,input().split(..
[백준 1647번] 도시 분할 계획 (Python3) import sys input = sys.stdin.readline from heapq import heappush,heappop def findparent(x): if parent[x] == x: return x parent[x] = findparent(parent[x]) return parent[x] V,E = map(int,input().split()) hq = [] for i in range(E): x1,x2,w = map(int,input().split()) heappush(hq,(w,x1,x2)) parent = {i:i for i in range(1,V+1)} result = 0 while hq: w,x1,x2 = heappop(hq) if findparent(x1) == findparent..
[백준 1197번] 최소 스패닝 트리 (Python3) import sys input = sys.stdin.readline from heapq import heappush,heappop def findparent(x): if parent[x] == x: return x parent[x] = findparent(parent[x]) return parent[x] V,E = map(int,input().split()) hq = [] for i in range(E): x1,x2,w = map(int,input().split()) heappush(hq,(w,x1,x2)) parent = {i:i for i in range(1,V+1)} result = 0 while hq: w,x1,x2 = heappop(hq) if findparent(x1) == findparent..
[백준 12100번] 2048 (Easy) (Python3) 굉장히 까다로웠던 문제 골드 1인 구슬탈출이 훨씬 쉬운거같은데 왜 골2? 처음에는 아무생각없이 이렇게 코드를 짰다. import sys input = sys.stdin.readline from copy import deepcopy dy = [1,-1,0,0] dx = [0,0,1,-1] N = int(input()) board = [] for i in range(N): board.append(list(map(int,input().split()))) def move(y,x,direction,copyboard): num = copyboard[y][x] copyboard[y][x] = 0 while True: y1 = y+dy[direction] x1 = x+dx[direction] if not (N>y1>=..
[백준 13460번] 구슬 탈출 2 (Python3) import sys input = sys.stdin.readline from collections import deque dy = [1,0,-1,0] dx = [0,1,0,-1] N,M = map(int,input().split()) board = [] for i in range(N): board.append(list(input().strip())) def go(y,x,direction,opcolor): while True: y1 = y+dy[direction] x1 = x+dx[direction] if (y1,x1) == opcolor: break if board[y1][x1] == "O": return 0,0 if board[y1][x1] == ".": y,x = y1,x1 else: break re..