one Book a Day

set의 교집합과 합집합에 대한 이해가 좀 필요한 문제이다. 평소 set을 잘 쓰지 않는데 많이 배운 문제. 종종 개념을 활용한 풀이를 구상해봐야겠다. from collections import Counter def solution(str1, str2): str1 = str1.lower() str2 = str2.lower() str1_elements_set = [] str2_elements_set = [] # 두글자씩 끊어 원소집합으로 만듦(둘다 알파뱃일 경우만.) for i in range(len(str1)-1): if str1[i].isalpha() and str1[i+1].isalpha(): str1_elements_set.append(str1[i] + str1[i+1]) for j in range..

분기있는 bfs. 벽을 뿌순 횟수에 따라 분기를 나눠준다. import sys input = sys.stdin.readline from collections import deque def bfs(x,y): queue = deque() queue.append([x,y,0]) visited = [[[0]*(K+1) for _ in range(M)] for _ in range(N)] visited[x][y][0] = 1 while queue: x,y,b_cnt = queue.popleft() if x==N-1 and y==M-1: return visited[x][y][b_cnt] for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0

다익쓰 다익써야한느 이유는 최소 거리로 갱신시키면서 가야 최대한 멀리 갈 수 있기 때문. import sys input = sys.stdin.readline from heapq import heappop,heappush def dijkstra(start): heap = [] heappush(heap,[start,0]) visited = {i: float('inf') for i in range(1,n+1)} visited[start] = 0 item_check = {i: False for i in range(1,n+1)} item_check[start] = True item_cnt = items[start] while heap: cur_node, total_dist = heappop(heap) for ne..

그냥 방향 바뀌는 부분만 체크해주면 댄당 import sys input = sys.stdin.readline N = int(input()) maps = input() cnt = 1 for i in range(1,N): if maps[i]=='E': if maps[i-1]=='W': cnt +=1 print(cnt)

라인스위핑 스위핑 알고리즘이란? 특정 선이나 공간을 한쪽에서부터 쓸어버리는 식의 알고리즘. 일정 좌표, 축기준 정렬 한 뒤 일정 시점의 좌우 가장 가까운 두 점사이의 거리보다 멀리떨어진 점은 조사하지 않는 방식. 가지치기를 하겠다는 이야기다.(O(NlogN)) 아래는 2261번 문제에 대한 분할정복 풀이. import sys input=sys.stdin.readline INF=sys.maxsize # 두 점 사이의 거리를 구하는 함수 def dist(a,b): return (a[0]-b[0])**2+(a[1]-b[1])**2 def divide(start,end): # 점 하나면 버림 if start==end: return INF # 점 두개면 거리구해서 리턴 elif end-start==1: retur..

Trie(트라이) = radix tree = prefix tree = digital search tree 탐색이라는 뜻의 retrieval에서 trie를 따온 것. 문자열 집합을 표현하는 트리 자료구조. 하나하나 비교가 아닌 key로 노드를 탐색. 원하는 원소를 찾는 작업을 O(M)에 해결 이진트리는 O(logN)*문자열의 길이 M => O(MlogN) 빠르지만 저장공간의 크기가 매우 크다.(자식들의 포인터를 모두 배열로 저장하고 있기때문.) 문자열 검색 문제에서 입력되는 문자열이 많을 경우 사용. 적용되는 기능. 검색엔진 사이트에서 제공하는 자동완성 및 검색어 추천기능에서 Trie 알고리즘 사용. 맞춤법 검사, IP라우팅 (라우터에서 packet을 포워딩해줄때 다음 라우터로 경로를 결정하기 위해 패킷의..

유니온 파인드. 정순, 역순으로 오르막길 포함된 갯수 파악해서 연산. import sys input = sys.stdin.readline def find(x): if parent[x] == x: return x parent[x] = find(parent[x]) return parent[x] def union(a,b): a = find(a) b = find(b) if level[a] >= level[b]: parent[b] = a if level[a]==level[b]: level[a] +=1 else: parent[a] = b N, M = map(int, input().split()) parent = {i:i for i in range(N+1)} level = {i:0 for i in range(N+1)..

오랜만에 직사각형 누적합 import sys input = sys.stdin.readline N, M = map(int, input().split()) areas = [list(map(int, input().split())) for _ in range(N)] K = int(input()) dp = [[0 for _ in range(M+1)] for _ in range(N+1)] dp[1][1] = areas[0][0] for i in range(1,N+1): for j in range(1,M+1): dp[i][j] = dp[i-1][j] + dp[i][j-1] + areas[i-1][j-1] - dp[i-1][j-1] for _ in range(K): x1,y1,x2,y2 = map(int, input(..

그냥 성별조건 추가된 크루스칼 import sys input = sys.stdin.readline def find(x): if parent[x] == x: return x parent[x] = find(parent[x]) return parent[x] def union(a,b): a = find(a) b = find(b) if level[a] >= level[b]: parent[b] = a if level[a]==level[b]: level[a] +=1 else: parent[a] = b N, M = map(int, input().split()) sex = [0] + list(input().split()) arr = [] parent = {i:i for i in range(1,N+1)} level = {..

경우의 수 따라 진입 하면 된다. 주의할 점은 for 문 순회기 때문에 key를 0으로 바꿔 넣으면 다시 1로 바꿔주어야 한다는 것. 분기 문제일때 변수를 직접 바꾸는 것은 주의하자. import sys input = sys.stdin.readline from collections import deque def bfs(): queue = deque() queue.append([s_x-1,s_y-1,0,1]) visited = [[[False for _ in range(M)] for _ in range(N)] for _ in range(2)] visited[1][s_x-1][s_y-1] = True while queue: x,y,time,key = queue.popleft() if x==t_x-1 and ..