one Book a Day

포인터로 와리가리하면서 삽입, 출력해야하는문제 뭔가 insert를 써야할 것 같은 문제는 보통 stack을 2개쓰거나 heap을 두개쓰거나 하면 된다. import sys input = sys.stdin.readline T = int(input()) for test in range(T): L = input().rstrip() left,right = [],[] for chr in L: if chr=="": if right: left.append(right.pop()) elif chr=="-": if left: left.pop() else: left.append(chr) answer = left + right[::-1] print("".join(answer))

처음에 조합으로짰다가 최대한 줄여도 메모리 시간초과나서 고생하다 결국 c++코드보고 이분탐색풀이로 다시 짰다. 이분탐색 안그래도 공부하려고 생각중이었는데 오늘 기본문제부터 조금씩 풀어봐야 할듯 싶다. 위는 조합풀이, 아래는 이분탐색 풀이. import sys input= sys.stdin.readline from itertools import combinations # N-1개의 사이에서 M-1개의 작대기를 뽑는 조합. # 각 max값중 최댓값과 slice한 작대기 위치 패킹해 저장. # 저장된 max값 정렬 후 맨앞에있는 배열 출력. N,M = map(int,input().split()) ball_lists = list(map(int,input().split())) maxes = float('inf')..

점에서 각 집까지 최소거리 = 대놓고 다익스트라. 처음엔 조건 못보고 dp그려야하나 고민하고 있었는데 다시보니 가까운 순서로 방문이라고 대놓고 써줘서 다익스트라 결과값 정렬때린다음 반복문 으로 쉽게 해결했다. import sys input = sys.stdin.readline from heapq import heappop,heappush # 1. 0번에서 각 집에 가는 최소거리. -> 다익스트라 def dijkstra(start): heap = [] dp_dists[start] = 0 heappush(heap,[dp_dists[start],start]) while heap: cur_dist,cur_node = heappop(heap) for next_node,next_dists in graph[cur_n..

뭔가 줄일수 있을 것 같긴한데 일단 통과. 3차원 배열은 뭔가 3차원값들에 대해 늘 초기화해줘야 한다는게 좀 짜증난다. 얕은복사라 그런가 자꾸 초깃값을 가져와서 새로 덮어씌우는 바람에 아직 설계가 손에 익지 않는다. 오늘 좀 더 설계에 대해 연습해 볼 것. 3차원 배열 내 값의 수정과 반복문에 대해서. import sys input = sys.stdin.readline # 세로 M 가로 M M,N = map(int,input().split()) K = int(input()) maps = [list(input().rstrip()) for _ in range(M)] dp = [[[0,0,0] for _ in range(N)] for _ in range(M)] # 정글 J 바다 O 얼음 I for i in r..

다른 스터디원들 보면 뭔가 짧게 풀었던데 일단 나는 0,0기준 고쳐야하는것 체크하고 그 값 범위마다 따로sum구해서 비교했다. import sys input = sys.stdin.readline N,M = map(int,input().split()) chess = [list(input().rstrip()) for _ in range(N)] dp = [[0]*M for _ in range(N)] for i in range(N): for j in range(M): if i%2 == j%2: if chess[0][0] != chess[i][j]: dp[i][j]=1 else: if chess[0][0] == chess[i][j]: dp[i][j]=1 min_change = float('inf') for i i..

Tree 탐색등등 종종 나오는 경우의수를 따지는 DFS문제이다. idx 값을 1개 늘리냐 2개 늘리냐의 분기로 재귀를 실시. 실질적인 4방탐색이나 숨바꼭질 같은 문제와 다를게 없다. 재귀로 값을 누적시키며 달릴것이냐 큐나 스택을 이용할 것이냐의 차이. 선택의 문제. 경우의 수. 종료조건은 max값이 수열 길이와 같은 것. 왜 못풀었을까 생각해보자. import sys from collections import deque def DFS(idx): # idx 1부터 시작 kriii의 검사가 모두 끝나면 수열의 가장 큰 값을 찾는다. if idx == len(kriii): high = 0 for i in range(len(sequence)): high = max(high,int(sequence[i])) # 가..

0,1 knapsack 선택하느냐 마느냐의 문제는 greedy가 안되기 때문에 점화식을 세울 수 있다면 dp 아니면 완탐이다. K라는 무게값을 1~target값까지 증가시키며 최고 가치를 누적시키면 된다. import sys input = sys.stdin.readline N, K = map(int, input().split()) wei_cost = [[0,0]] dp = [[0 for _ in range(K + 1)] for _ in range(N + 1)] for _ in range(N): wei_cost.append(list(map(int, input().split()))) for i in range(1, N + 1): for j in range(1, K + 1): weight = wei_cost[..

dp로 풀라고 대놓고 써있는 문제. 대충 계산해보면서 점화식 세우고 바로 풀었다. 사각형에서 사각형 빼고 겹치는 사각형은 더해주는 방식. import sys input = sys.stdin.readline N,M = map(int,input().split()) matrix = [list(map(int,input().split())) for _ in range(N)] dp = [[0]*N for _ in range(N)] for i in range(N): for j in range(N): dp[0][0] = matrix[0][0] if i==0 and j>0: dp[i][j] = dp[i][j-1]+matrix[i][j] elif j==0 and i>0: dp[i][j] = dp[i-1][j]+matrix..

이해하는데 꽤 오래 걸렸다. dp를 대각선으로 그려야 답을 구할 수 있는 문제로 아주 신박하고 연습이 필요한 문제일 것 같다. dp[i][i+j]로 놓고 i를 증가시키면 양쪽이 1,1씩 증가해 대각선 배열을 먼저 연산 할 수 있으며 j가 늘어나면 가운데 대각선에서 한칸 더 멀어진 배열을 연산하게 되는 식이다. 즉 2개씩 묶은 행렬을 계산하고(AB,BC,CD,CE) 그 값을 가지고 3개씩 묶은 행렬을 계산. min(AB*C or A*BC) 그걸 가지고 4개씩 묶은 행렬을 계산min(A*BCD,AB*CD,ABC*D) N*N 인접 행렬에서 대각선으로 배열을 채우는법을 이해할 수 있었고 차후 다른 문제에서도 쓸만한아이디어인 것 같다. 행렬의 곱셈이 이루어지는 숫자는 [앞행렬의 행값 * 앞행렬의 열값(==뒷행렬의..

경우의 수를 만들어 연산자를 대입하는 문제였다. 보자마자 DFS가 생각나서 설계했는데 처음에는 +-보다 */연산을 먼저 처리하는 줄 알고 문자열로 calculate를 쌓고 eval answer에 삽입햇으나 테케 통과 못하고 문제 다시일어보니 앞에서부터 순차 연산... str에서 int로 바꾸고 진입시마다 계산해주면서 들어갔다. import sys input = sys.stdin.readline def DFS(idx,calculate): if idx==N: answer.append(calculate) return num = seqs[idx] for operator in '+-*/': if operator == '+'and opers[0]: opers[0] -=1 DFS(idx+1,calculate+num)..