Baekjoon

문제 링크 https://www.acmicpc.net/problem/18352 문제 해설 Idea BFS 시작 노드 X부터 연결된 노드를 순차적으로 방문하면서 X로부터 떨어진 거리를 기록 거리가 K와 같은 노드를 출력하고, 해당하는 노드가 없을 경우 -1을 출력 거리가 K를 넘어가지 않는 노드에 대해서만 탐색하여 시간 단축 Time Complexity BFS: O(N+M) = 1,300,000 Data Size N: 2 <= int <= 300,000 M: 1 <= int <= 1,000,000 K: 1 <= int <= 300,000 X: 1 <= int <= N A, B: 1 <= int <= N 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 from collections import deque import sys input = sys....

문제 링크 https://www.acmicpc.net/problem/1495 문제 해설 Idea Dynamic Programming P[i] = max(P[i-1]+V[i-1],P[i-1]-V[i-1]), 0 <= P[i] <= M 모든 P[i-1]가 P[i+1]에 영향을 줄 수 있기 때문에 범위 내 모든 값을 집합에 저장 마지막 곡에 대한 P가 존재할 경우 최댓값을 출력하고, 없을 경우 -1을 출력 Time Complexity DP: O(NM) = 50,000 Data Size N: 1 <= int <= 50 M: 1 <= int <= 1,000 S: 0 <= int <= M V: int * N 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 N, S, M = map(int, input()....

문제 링크 https://www.acmicpc.net/problem/2805 개요 이분 탐색으로 해결할 수 있는 문제이다. Python3을 사용하면 시간초과가 발생하므로 PyPy3를 사용한다. 문제 조건 일정 높이에 대해 모든 나무를 잘랐을 때, 조건을 만족하는 절단기의 최대 높이(H)를 구하는 문제이다. 잘린 나무의 길이의 합은 상근이가 필요로 하는 나무의 길이(M)보다 크거나 같아야 한다. 문제 해설 나무의 수(N)의 최댓값이 1,000,000이므로 모든 범위에 대해 반복하는 순차 탐색을 이용할 경우 시간초과가 발생한다. 시간 복잡도가 O(log n)인 이분 탐색을 이용하면 시간 복잡도가 O(n)인 순차 탐색을 쓰는 것보다 훨씬 빠르다....

문제 링크 https://www.acmicpc.net/problem/11650 개요 배열 형태의 자료들을 정렬하는 간단한 문제이다. 파이썬에서는 내장 함수 sort()를 사용하면 쉽게 풀 수 있다. 문제 해설 문제에서 요구하는 것은 x좌표 값과 y좌표 값으로 구성된 배열들의 리스트를 x 값, y 값 순으로 정렬하는 것이다. 배열의 자료구조는 인덱싱으로 접근이 가능한 것이면 아무거나 상관없기에 좌표 표현에 직관적인 튜플을 사용한다. 정렬의 기준이 반대였으면 람다 식을 써야겠지만 좌표의 위치가 곧 정렬 순서이기 때문에 Key값은 사용하지 않는다. 해설 코드 1 2 3 4 5 6 7 8 9 10 import sys input = sys....

문제 링크 https://www.acmicpc.net/problem/4949 개요 스택을 이용하여 풀 수 있는 문제이다. 문자열 처리에 관한 능력이 추가로 요구된다. 최대 입력 크기가 정해지지 않았기에 시간 복잡도는 무시한다. 문제 해설 해당 문제에서 고려해야할 문자는 종료 조건인 점(’.’)을 제외하면 소괄호와 대괄호 뿐이다. 균형잡힌 문장의 구분 여부는 1. 닫힌 괄호가 열린 괄호보다 앞에 나온 경우 2. 열린 괄호가 안 닫힌 경우로 판단했다. 문자 하나하나마다 확인하며 괄호를 골라낼 수도 있지만 이번엔 정규식을 사용해본다. 우선 정규식 라이브러리인 re에 속한 sub 메서드를 사용해 괄호를 제외한 모든 문자를 제거한다....