class Solution: def minSwaps(self, nums: List[int]) -> int: n = len(nums) ones = nums.count(1) zeros = nums[:ones].count(0) mn_zeros = zeros for i in range(n - 1): if nums[i] == 0: zeros -= 1 if nums[(i + ones)%n] == 0: zeros += 1 mn_zeros = min(mn_zeros, zeros) return mn_zeros

class Solution: def checkValid(self, matrix: List[List[int]]) -> bool: n = len(matrix) for y in range(n): cnts = [0]*n for x in range(n): cnts[matrix[y][x] - 1] += 1 if cnts != [1]*n: return False for x in range(n): cnts = [0]*n for y in range(n): cnts[matrix[y][x] - 1] += 1 if cnts != [1]*n: return False return True

import sys H, W = map(int, input().split()) grid = [] for i in range(H): grid += list(map(int, input().split())), Q = int(input()) ops = [] for i in range(Q): ops += list(map(int, input().split())), def fill(grid, clr, nclr, y, x): if grid[y][x] != clr or grid[y][x] == nclr: return grid[y][x] = nclr for oy, ox in [(1, 0), (-1, 0), (0, 1), (0, -1)]: ny = oy + y nx = ox + x if not (0

import sys import collections def sort_topo(g, N): indegree = [0]*(N + 1) for u, adjs in g.items(): for v in adjs: indegree[v] += 1 q = [1] order = [] while q: u = q.pop(0) order += u, for adj in g[u]: indegree[adj] -= 1 if indegree[adj] == 0: q += adj, return order def calc(g, order, N, K): loads = collections.defaultdict(int) loads[1] = K for u in order: num_adj = len(g[u]) if 0 == num_adj: co..

이진탐색이란? (What is binary search?) 정렬된 수열에서 특정 값을 찾고자 할때 여러가지 검색 알고리즘들이 사용될 수 있습니다. 그 중 가장 손쉽게 구현 및 사용이 가능한 알고리즘이 바로 이진탐색 알고리즘 입니다. 이는 단순히 수열에서뿐만 아니라 이진 탐색 트리에서도 사용되는 알고리즘이라고 볼 수 있습니다. 이진탐색 검색의 동작 방법은 매우 간단합니다. 아래와 같이 [2, 4, 5, 9, 11, 24, 70, 101]의 수열이 있다고 가정합니다. 이 때 여기서 '5'라는 숫자값이 존재하는지 여부를 찾고 싶습니다. 최초 검색은 전체 수열의 중간 값이 찾고자 하는 값과 동일한지를 비교한 것 입니다. 즉, 탐색 범위는 아래에서 노란색으로 표시된 구역이며, 이 구역의 가운데 위치의 값이 찾고자..

hash 개념 Hash는 추가, 삭제, 검색을 거의 O(1)의 성능으로 수행할 수 있는 자료구조입니다. Array와 list의 특징을 합친 자료구조이며, 성능이 좋으면서도 구현이 단순합니다. collision 특정 key 값으로 value를 저장하게 되는데, 이 때 중복된 key가 존재할 수 있습니다. 이런 중복된 key가 존재하는 경우 collision이라고 하며 hash 자료구조에서는 이러한 collision을 해결하기 위한 두 가지 방법을 제공합니다. linear probing (open addressing) collision이 발생한 slot부터 linear하게 증가하며 empty slot을 찾는 방법입니다. 충돌 시 순차적으로 빈 곳을 찾게 되며 입력 자료의 2배 이상의 크기를 지니고 있어야 효..