본문 바로가기

Algorithm/BOJ133

[백준] 1525번 - 퍼즐 (파이썬) # 퍼즐 from collections import deque N = 3 arr = [] zero_x = 0 zero_y = 0 for i in range(N): arr.append(list(map(int, input().split()))) for j in range(N): if arr[i][j] == 0: zero_x = i zero_y = j dx = [0, 1, 0, -1] dy = [1, 0, -1, 0] visit = dict() def bfs(a, b): global arr q = deque() string = change(arr) if string == '123456780': return '0' q.append((a, b, 0, string)) visit[string] = True while.. 2022. 2. 9.
[백준] 11779번 - 최소비용 구하기 2 (파이썬) # 최소비용 구하기 2 import sys import heapq input = sys.stdin.readline MAX = sys.maxsize N, M = int(input()), int(input()) arr = [[]for _ in range(N+1)] for _ in range(M): start, end, cost = map(int, input().split()) arr[start].append((cost, end)) def dijkstra(start): q = [] heapq.heappush(q, (0, start)) result[start] = 0 while q: cost, city = heapq.heappop(q) if result[city] < cost: continue for ncost.. 2022. 2. 9.
[백준] 4386번 - 별자리 만들기 (파이썬) # 별자리 만들기 import heapq import sys import math input = sys.stdin.readline N = int(input()) star = [] for _ in range(N): x, y = map(float, input().split()) star.append((x, y)) arr = [[]for _ in range(N)] for i in range(N): for j in range(N): if i == j: continue x, y = star[i][0], star[i][1] nx, ny = star[j][0], star[j][1] dist = math.sqrt(abs(x-nx)**2+abs(y-ny)**2) arr[i].append((dist, j)) result .. 2022. 2. 9.
[백준] 17136번 - 색종이 붙이기 (파이썬) # 색종이 붙이기 import sys import copy input = sys.stdin.readline MAX = sys.maxsize N = 10 arr = [] length_one = 0 for i in range(N): arr.append(list(map(int, input().split()))) for j in range(N): if arr[i][j] == 1: length_one += 1 paper = [5] * 6 paper[0] = 0 result = MAX def check(x, y, nx, ny, arr): possible = True if 0 2022. 2. 7.
[백준] 12738번 - 가장 긴 증가하는 부분 수열 3 (파이썬) # 가장 긴 증가하는 부분 수열 3 import sys import bisect input = sys.stdin.readline N = int(input()) arr = list(map(int, input().split())) result = [arr[0]] for i in range(1, N): if arr[i] > result[-1]: result.append(arr[i]) else: index = bisect.bisect_left(result, arr[i]) result[index] = arr[i] print(len(result)) 이진탐색, bisect 1. 전체 리스트를 돌면서 - result의 마지막 원소보다 크면 append를 해준다 - 작으면 bisect_left를 이용하여 해당 인덱스의 .. 2022. 2. 7.
[백준] 11437번 - LCA (파이썬) # LCA import sys input = sys.stdin.readline sys.setrecursionlimit(10**5) def make_depth(node, dep): visited[node] = True depth[node] = dep for nnode in arr[node]: if not visited[nnode]: parent[nnode] = node make_depth(nnode, dep+1) def lca(x, y): if depth[x] > depth[y]: y, x = x, y while True: if depth[x] == depth[y]: break y = parent[y] for _ in range(depth[x]): if x == y: return x x = parent[x.. 2022. 2. 7.
[프로그래머스] - 자동완성 class Trie(): head = [0, dict()] def add(self, word): current = self.head current[0] += 1 for x in word: if x not in current[1]: current[1][x] = [0, dict()] current = current[1][x] current[0] += 1 def check(self, word): current = self.head result = 0 for x in word: if current[0] == 1: return result result += 1 current = current[1][x] return result def solution(words): answer = 0 T = Trie() for w.. 2022. 2. 7.

티스토리툴바