백준 검색 결과
248 개의 검색 결과가 있습니다.
코딩/백준 (Python)

백준 9012번: 괄호 (Python)

접근 VPS가 될 수 있는 조건만 잘 생각한다면 아주 쉽게 풀 수 있는 문제이다. VPS가 될 수 있는 조건은 다음과 같다. 문자열에서 '(' 문자와 ')' 문자의 개수가 같아야 한다. 문자열을 앞에서 부터 탐색할 때 ')'의 개수가 '(' 개수보다 많아지는 순간이 있으면 안된다. (예. '(())))(((())' 는 '(' 과 ')' 문자 개수가 같지만 VPS가 아니다. 코드 import sys n = int(sys.stdin.readline()) for i in range(n): m = list(map(str, sys.stdin.readline().rstrip())) vps = 0 for j in ra..

2021. 4. 1. 05:06
코딩/백준 (Python)

백준 2004번: 조합 0의 개수 (Python)

접근 당연히 이전 단계별 문제들에서 풀었던 것과 같이 팩토리얼을 이용한 풀이를 했지만 역시 당연하게도 숫자의 범위 때문에 메모리 초과가 떴다. 풀지 못하고 헤메다가 다른 분들 풀이의 도움을 받았다. 10은 2와 5로 이루어져있다. 어떤 수를 소인수분해 했을 때 2와 5의 개수 중 작은 값이 그 숫자의 0의 값과 일치한다..! 게다가 그 수를 2로 나누면 그 2의 개수가 한개 줄어들게 된다. 이 점을 이용하여 그 수가 가지고 있는 2의 개수와 5의 개수를 계산하여 서로 더하고 빼서 문제를 해결할 수 있다. n!의 2 개수 및 5 개수를 세는 함수를 만들고 함수의 값끼리 더하고 뺀 후, 그 최소값을 이용하여 0의 개수를 구할 수 있다. 코드 def c_two(n): count = 0 while n != 0:..

2021. 3. 31. 20:45
코딩/백준 (Python)

백준 2981번: 검문 (Python)

접근 최대공약수를 이용하는 문제이다. 세개의 수 A, B, C가 M으로 나누었을 때 나머지 R을 가질 경우 다음과 같이 표현할 수 있다. A = M * a + R B = M * b + R C = M * c + R 이 때, 첫째 줄에서 두번째 줄을, 그리고 두번째 줄에서 세번째 줄을 빼면 다음과 같이 나온다. A - B = M * (a - b) B - C = M * (b - c) A - B와 B - C는 M을 공약수로 가지게 되며, 두 수의 최대공약수를 LCM이라고 할 때, LCM의 약수들은 모두 M이 될 수 있다. 즉 N개의 숫자가 주어질 경우, A-B, B-C 등 N[i] - N[i - 1]은 N - 1개의 숫자로 나타게 되며, N - 1 개의 숫자들의 최대공약수를 구하고, 이 최대공약수의 약수들을 오..

2021. 3. 31. 17:05
코딩/백준 (Python)

백준 1931번: 회의실 배정 (Python)

접근 그리디 알고리즘을 이용하여 푸는 문제이다. 회의 시간을 입력받고 이를 다음의 기준에 따라 정렬한 후 탐색을 시작한다. 회의가 끝나는 시간을 오름차순으로 정렬 회의가 동시에 끝날 경우, 같이 끝나는 회의들끼리 회의가 시작하는 시간을 오름차순으로 정렬 이러한 기준으로 정렬했을 경우 다음과 같이 풀 수 있다. 예를 들어 첫번째 회의를 선택하고, 그 회의가 끝나는 시간을 저장한다. 다음 회의들을 탐색하면서 처음으로 시작시간이 이전 회의가 끝나는 시간보다 같거나 커지는 경우를 선택할 경우, 선택된 회의는 기존 회의가 끝난 이후 가장 먼저 시작해서 가장 끝나는 시간이 빠른 회의이다.(회의가 끝나는 시간을 오름차순으로 정렬했기 때문에) 이러한 방식으로 선택하여 가장 많은 회의를 할 수 있는 횟수를 계산할 수 있..

2021. 3. 30. 22:28
코딩/백준 (Python)

백준 12865번: 평범한 배낭 (Python, PyPy3)

접근 대표적인 동적 계획법(Dynamic Programming) 문제 중 Knapsack 문제이다. 일단 (N + 1) * (K + 1) 행렬을 준비하여 문제를 풀게 된다. 행 별로 채워가면서 해당 무게별 채울 수 있는 가장 큰 값을 채워나가기 시작하여 첫 행을 채운다. 무게/가중치 0 1 2 3 4 5 6 7 0 0 0 0 0 0 0 0 0 6 / 13 0 0 0 0 0 0 13 13 4 / 8 3 / 6 5 / 12 무게가 6이고 가중치가 13인 물건을 가지고 가방을 채운다고 했을 때, 5까지는 6의 무게가 나가는 물건을 넣을 수 없기 때문에 0이며, 6부터는 넣을 수 있으므로 13의 가치를 가지게 된다. 무게/가중치 0 1 2 3 4 5 6 7 0 0 0 0 0 0 0 0 0 6 / 13 0 0 0..

2021. 3. 30. 02:02
코딩/백준 (Python)

백준 9251번: LCS (Python)

접근 몇 번 코드를 작성해보다가 전혀 답에 근접해지지 않아 다른 분들의 풀이를 참고하여 풀게 되었다. 다음과 같은 표를 작성해보자. 문자0CAPCAK00000000A0 C0 A0 Y0 K0 P0 표시된 칸부터 순환하며 칸을 채우되, 칸을 채우는 조건은 아래와 같다. dp[i][j] 칸을 채울 때, i행 문자와 j열 문자가 같다면, dp[i - 1][j - 1] + 1 i행 문자와 j열 문자가 다르다면, max(dp[i][j - 1], dp[i - 1][j] 와 같은 방법으로 채워나가면 된다. 두번째 행까지 채울 경우 다음과 같은 결과를 얻을 수 있다. 문자0CAPCAK00000000A0011111C0111222A0 Y0 K0 P0 i 행과 j 열 문자가 같은 경우만 음영으로 표시하였다. 이와 같이 풀어가..

2021. 3. 30. 00:19
반응형