cch8ii 님의 블로그

문제: 골드 5 괄호의 값https://www.acmicpc.net/problem/2504 풀이코드# (): 2, []: 3# ()() = 2+2# (()) = 2*2# 스택 안에 차례대로 넣는데...# -> ( 다음에 뱌로 )가 나오면 숫자# -> ( 안에 뭔가 있으면.. * S = input().rstrip('\n')stack = []ans = 0tmp = 1prev = ''for s in S: if s == '(': stack.append(s) tmp *= 2 elif s == '[': stack.append(s) tmp *= 3 elif s == ')': if not stack or stack[-1] != '('..

문제: 골드 1 최솟값 찾기https://www.acmicpc.net/problem/11003 풀이코드import sysfrom collections import dequeinput = sys.stdin.readline# 덱에 (값, 인덱스)를 넣고 항상 최솟값이 맨 앞에 오게끔 # + 인덱스 범위에 없는 거면 삭제N, L = map(int, input().split())lst = list(map(int, input().split()))d = deque()out = []for i, x in enumerate(lst): # 새로 들어오는 값이 d에 있는 값보다 작다면 제거 while d and d[-1][0] > x: d.pop() d.append((x, i)) ..

문제: 플래티넘 5 오아시스 재결합https://www.acmicpc.net/problem/3015 풀이코드import sysinput = sys.stdin.readlineN = int(input())s = [] ## (키, 개수)ans = 0for n in range(N): i = int(input()) cnt = 1 while s and s[-1][0] 느낀 점스택이 어려웠는데 그래도 잘 풀었다. 그런데 내가 해당 문제에서 고려하지 못한 점은 같은 키를 가진 사람이었다. 예를 들어보자. 2, 3, 4 의 키를 가진 사람들이 줄을 서있으면 2와 3, 3과 4와 같이 2쌍이 볼 수 있다. 그런데 여기서 2, 3, 3, 3, 4, 5 이렇게 들어왔다고 해보자. 2와 3 * 3쌍,..

문제: 골드 5 오큰수https://www.acmicpc.net/problem/17298 풀이코드import sysinput = sys.stdin.readlineN = int(input())lst = list(map(int, input().split()))s = [] ## 오큰수를 아직 찾지 못한 수들의 인덱스를 넣어두는 스택ans =[-1] * Nfor i in range(N): while len(s) > 0 and lst[s[-1]] 느낀 점너무 헷갈렸다. ...ㅠㅠ일단 스택에 뭘 넣고 뺄지를 생각해야 한다. 이중 for문으로 하면 무조건 시간초과가 난다. for문으로 lst를 돌되 만약 계속해서 오큰수를 찾지 못한다면 스택에 남아있어야 한다. 그리고 오큰수를 찾으면 그 숫자의 오큰수가 이거..

올림 나눗셈 → (x + 1) // 2예: 5개면 → (5+1)//2 = 3예: 4개면 → (4+1)//2 = 2홀수 짝수 나눌 필요 없음만약 2로 나누는 경우가 아니고 일반 K로 나누려면..? → (x + K - 1) // Klist보다 set이 훨씬 빠르다!## x_lst를 리스트로 하면 시간 초과가 나고 set으로 하면 시간 초과가 안 난다?## list에서의 병목 현상## - (x - i) in x_lst: in 연산이 O(n)## - x_lst.remove(x - i): remove 연산이 O(n)## -> 결국 list로 하면 전체가 O(n^2)## set으로 한다면? ## - (x - i) in x_lst: in 연산이 평균적으로 O(1)## - x_lst.remove(x - i): remo..

문제: 브론즈 2 방배정https://www.acmicpc.net/problem/13300 풀이코드import sysinput = sys.stdin.readlinecnt = [[0]*7 for _ in range(2)] ## [성별][학년]N, K = map(int, input().split())for n in range(N): s, y = map(int, input().split()) cnt[s][y] += 1room = 0for s in range(2): for y in range(1, 7): i = cnt[s][y] room += (i+K-1) // Kprint(room)느낀 점중요하게 생각해야 할 점은 3가지이다. 1. 같은 학년이어야 같은 방을 쓸..

https://www.acmicpc.net/workbook/view/7286https://www.acmicpc.net/workbook/view/7306 새롭게 알게 된 것이나 헷갈렸는데 알게 된 것리스트 내에 있는 원소들을 거꾸로 출력하고 싶다면 → print(lst[::-1])리스트 내 원소들의 자리를 바꿀 때는 card_lst[start], card_lst[end] = card_lst[end], card_lst[start]만약 리스트 내에 있는 원소들을 띄어쓰기 기준으로 출력하고 싶다면 → print(*lst)만약 리스트 내에 있는 원소들을 엔터 기준으로 출력하고 싶다면 → print("\n".join(lst))리스트에 있는 값들의 모든 조합을 구하는 라이브러리 → itertools만약 하나의 리..

문제: 골드 1 구간 합 구하기https://www.acmicpc.net/problem/2042풀이코드import sysinput = sys.stdin.readlinen, m, k = map(int, input().split())lst = []for _ in range(n): lst.append(int(input()))## 리프 노드 개수 설정 -> n 이상의 2 제곱수size = 1while size 0: tree[pos] = tree[2*pos] + tree[2*pos+1] pos //= 2## 구간 합def rangesum(start, end): start_pos = size + start end_pos = size + end s = 0 wh..

문제: 골드 5 평범한 배낭 https://www.acmicpc.net/problem/12865풀이코드n, k = map(int, input().split())dp = [[0] * (k+1) for _ in range(n+1)]## dp[i][j] = i번째 물건까지 넣었을 때 무게 j 이하로 얻을 수 있는 최대 가치for i in range(1, n+1): w, v = map(int, input().split()) for j in range(1, k+1): if w 느낀 점일단 DP에선 최대를 어떻게 기존의 값을 사용해 구할 수 있는지를 생각해야 할 것 같다. 일단 dp라는 2차원 리스트를 만들어 각 행은 물건의 종류, 각 열은 무게로 잡았다. 그래서 dp[i][j]는 i번째..

문제: 실버 1 숨바꼭질 https://www.acmicpc.net/problem/1697풀이코드from collections import dequeN, K = map(int, input().split())visited = [False]*100001visited[N] = True ## 0초에 점 N에 위치해있다는 의미q = deque()q.append((0, N))while q: t, n = q.popleft() if n == K: print(t) break ## 걷는다면 if 0 느낀 점원래는 항상 visited 를 행렬로 세워서하니까 행렬로 변수 선언을 하고 진행했는데 추후 코드를 다 짜고 보니까 굳이 행렬로 짜지 않아도 될 것 같았다. 시간 ..