one Book a Day

​ 순서는 그냥 쓰는대로 썼음 1. lambda ​ 수업듣고 이해하게 됐음. 함수를 표현식형태로 다른곳에 인자로 쓰기위한 느낌. ​ lambda 매개변수 리턴값 뒤에 조건문 오던 말던. ​ sorted의 key값으로 쓰면 매우 유용함. sorted(list, lambda x: (x[1],x[0]),reverse=True) ​ => 2번째 열, 1번째 열 순으로 이중정렬을 할수도있음. ​ sorted(dict,lambda x: dict[x]/[2])로 key값 대신서 index값 같고 key다른 여러값 동시에 뽑아 리스트로 만들수도있음. 2. map,reduce,filter ​ 앞에 설명한 lambda를 쓰기 가장 좋은 함수를 인자로 받는 메소드들. ​ map,filter은 (함수,리스트)를 인자로 받고 ..

뜬금 정렬 정리. 최근 문제풀이에 열중하다보니 다시한번 기본서를 보고싶은 느낌이 들어 정리. 버블 정렬 O(n^2) def bubbleSort(lst): LEN = len(lst) for last_idx in range(LEN-2, 0, -1): # 각 턴의 마지막 인덱스 isSwap = False # 최적화 for l_idx in range(0, last_idx+1): if lst[l_idx] > lst[l_idx+1]: lst[l_idx], lst[l_idx+1] = lst[l_idx+1], lst[l_idx] isSwap = True if not isSwap: # swap이 일어나지 않았으면 정렬 완료상태 return lst return lst 나랑 내뒤에랑 비교해서 큰게 뒤로감. 여러번 순회해서 ..

set을 이용하는 문제로 set 삽입, 삭제 메소드인 add remove discard만 알면 무난한 코드로 풀린다. import sys input = sys.stdin.readline m = int(input()) S = set() for _ in range(m): commands = input().strip().split() # split()을 통해 띄어씌기가 있으면 튜플인 commands # 없으면 그냥 commands if len(commands) == 1: if commands[0] == "all": S = set([i for i in range(1, 21)]) else: S = set() # set은 add remove discard(discard는 없는거 없애려해도 오류아냄.) else: c..

후위, 중위순회로 전위순회 찾기. 후위순회의 마지막 순회가 루트노드인 것을 이용 그 루트노드를 기준으로 좌우로 찢을 수 있었다. 인덱싱을 위해 최초 인덱스로 부터 중위순회로 얻은 left,right값으로 트리를 좌우로 분할하면서도 인덱싱이 가능하게 설계. 두세번 코드해석해봤는데 아직도 혼자 설계하라면 할수있을까 싶다. import sys sys.setrecursionlimit(10**6) n = int(input()) in_order = list(map(int, input().split())) post_order = list(map(int, input().split())) pos = [0]*(n+1) for i in range(n): pos[in_order[i]] = i # 중위 순회로 부모노드의 위치에..

부분집합은 조합툴쓰면 너무 편하다.. 자모음 cnt해서 조건 만족하면 정답 리스트에 넣었다. import sys input = sys.stdin.readline from itertools import combinations L,C = map(int,input().split()) secret = list(input().split()) # 암호는 사전순 sorted되어있다. secret.sort() # 최소한개모음 두개자음 mom_char = ['a','e','i','o','u'] combs = list(combinations(secret,L)) ans = [] for chars in combs: mom_cnt=0 child_cnt=0 for char in chars: if char in mom_char: ..

DFS하니까 재귀에러나고 시간초과 메모리초과 가관이어서 BFS로 다시 풀었다. 구조는 똑같이 queue에 1을 넣고 1부터 위에서 아래로 탐색하며 parent값을 자식들에게 할당하는 방식. import sys input = sys.stdin.readline from collections import defaultdict,deque N = int(input()) graph = defaultdict(list) for _ in range(N-1): a,b = map(int,input().split()) graph[a].append(b) graph[b].append(a) queue = deque([1]) ans = {} check = [False for _ in range(N+1)] while queue: pa..

항상 문자열에서 검사하고 중복 갯수세고 하는거 나오면 set()으로 목록 만들고 ord써서 반복문 돌릴수 있게 설계한다거나 char_count 배열에 갯수 저장해 넣고 뺄때 쓸 수 있게 설계. string ='' 두고 더하고 빼고 슬라이싱 인덱싱 하는 스킬 더 기를 것. 문자열로 DFS돌리는 문제 은근 나옴. 슬라이싱으로 두문자씩, 두숫자씩 묶거나 숫자문자면 중간중간 int써서 수식계산 및 비교 까지 가능. 진법변환까지는 아직 문제못봄. from sys import stdin input = stdin.readline def dfs(depth, string): global N, cnt if depth == N: # print(string) cnt += 1 return # 종류별로 알파뱃 검사(깊이마다) f..

강의실의 갯수N = queue의 방의 갯수. 최소 heap을 사용해 가장 빨리 돌아오는 수업 종료시간보다 시작해야하는 수업이 빠르면 방 하나 증가 적으면 끝난수업빼고 새수업 넣는다. 즉 최대 필요한 room의갯수가 계속유지된다. 최솟값, 최댓값을 계속 뽑아내야 할때는 heapq.. 잘 생각해보자 import heapq import sys N = int(input()) timeTable = [list(map(int,sys.stdin.readline().split())) for _ in range(N)] timeTable.sort(key=lambda x: x[0]) queue = [] heapq.heappush(queue,timeTable[0][1]) for i in range(1,N): # last_tim..

싸이클을 만들 수 있느냐는 문제 조건은 1. 이전칸으로 가지 않을 것 2. 이전칸을 제외하고 방문했던 지점을 만나면 싸이클이 존재. N,M=map(int,input().split()) matrix=[list(map(str,input()))for _ in range(N)] visited = [[False]*M for _ in range(N)] dy=[0,0,1,-1] dx=[1,-1,0,0] # 싸이클의 조건 # 1. 바로 이전 칸으로 가지 말 것( 이전 좌표 가억해두고 같으면 이동하지말것.) # 2. 그럼에도 불구하고 갔던 곳(visited true)를 만나면 싸이클이 존재하므로 True를 반환할것. def dfs(x,y,px,py,ball): if visited[x][y]==True: return Tr..

분할정복 대표적인 문제이다. 연산 갯수를 줄이기 위해 반으로 쪼개고 쪼개 A*1로 쪼갠다음 그 결과값을 양쪽에서 곱해주면서 조합해준다. 분할 : 곱해야 하는 갯수 B를 2로 나누어 주며 분할한다. 정복 : A*1의 정복을 통해 계산한다. 조합 : A*A / (A*A) * (A*A) / 이런식으로 결과값을 제곱하면서 올라와 모든 재귀가 끝나면 연산이 끝난다. import sys input = sys.stdin.readline A, B, C = map(int, input().split(' ')) # 정복 def conq(length): # 정복 : length가 1이 되면 A를 반환하겠다.(최소단위 연산의 정복) if length == 1: return A %C # 짝수면 좌우로 찢고 if length % ..