파이썬 백준 1920번 실버4 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 문제 보기 분류: 자료 구조, 정렬, 이분 탐색 문제 풀기 이분 탐색 카테고리의 문제이긴 하나 문제를 보자마자 리스트 안의 원소를 찾는 형식의 코드가 바로 떠올랐다. 하지만, 이분 탐색을 배우기 위한 지금의 시간이니 이분 탐색으로 풀어본다. 일단 주어진 N 값들을 sorted() 함수로 오름차순 정렬을 하여 중간 나눌 ..

파이썬 백준 1992번 실버1 https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 문제 보기 분류: 분할 정복, 재귀 문제 풀기 이전에 풀었던 2630번 색종이 만들기 문제와 거의 동일하다. https://xcevor.tistory.com/56 [Python] 백준 풀기 2630 - 색종이 만들기 파이썬 백준 2630번 실버2 https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체..

파이썬 백준 2630번 실버2 https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 문제 보기 문제 풀기 2차 array 형태로 모든 색종이의 맵을 저장하고 이중 for loop 를 통해 왼쪽 위 구석에서 부터 차례대로 color_check != colorpaper_ls[i][j]: 체크해 나간다. 이 때, 기준이 되는 원소는 맨 처음에 시작하는 왼쪽 위이며, 흰색 또는 파란색과 같은지를 계속 비교해 나간다. 모든 원소에 ..

파이썬 백준 1541번 실버2 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 문제 보기 분류: 그리디 알고리즘, 수학, 문자열, 파싱 문제 풀기 괄호를 적절히 섞어 최소가 되는 값을 찾기 위한 문제이기에 최소가 되기 위해서는 - 항이 많아져야 한다. 이를 위해 수식에서 - 가 나타나면 괄호의 시작으로 하여 모든 + 들을 거쳐 다음 - 가 나오기 전까지 묶어 주면 된다. 이 말인즉슨, - 문자를 기준으로 분리하여 개별적 묶음을 형성하고 첫..

파이썬 백준 1931번 실버1 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 보기 분류 그리디 알고리즘 문제 풀기 회의 시간이 겹치는 복수의 회의에서 늦게 끝날수록 전체 횟수가 늘어나는데 유리하다. 이를 기준 삼아 끝나는 시각을 오름차순으로 만들어야 한다. 그리고, 시작 시각의 경우 이전에 진행 중인 또는 진행된 회의의 끝나는 시각과 비교를 하게 되기에 시작 시각도 오름차순으로 정렬이 되어야 한다. 이 두 조건을 만족해야 하는데 최종 기준은 회의 끝나는 시각으로 결정되기 때문에 시작 시각인 timetable.sort(key = lambda x : (x[..

파이썬 백준 11047번 실버4 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 문제 보기 분류 그리디 알고리즘 문제 풀기 처음 접근은 어렵지 않았다. 하지만 한 번 더 생각해 보지 않았던 순간이 "시간초과" 를 한번 내뱉게 하였다. 일단, 문제에서 주어진 N 과 K 를 입력받고, 동전의 종류를 리스트에 하나하나 저장하여 초기 세팅을 한다. 처음에 생각한 방법은 K 를 만들 수 있..

파이썬 백준 2231번 브론즈2 https://www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net 문제 보기 분류 브루트 포스 문제 풀기 어떻게 접근할까 생각해 보았으나 역시나 브루트 포스 분류답게 작은 수 1 부터 시작하여 만족하는 해당 조건이 나올때까지 숫자를 대입한다. N = abc + a + b + c 를 만족하는 abc 가 나올때까지 숫자 abc 대입. N_check = M + sum(map(int, str(M))) int ..

파이썬 백준 2559번 실버3 https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 문제 보기 for 문 안의 for 문으로 풀어볼까 deque 를 사용해서 풀어볼까 list 의 index 를 이용해 풀어볼까 문제 풀기 제출을 하면서 엄청난 시간초과를 뿌려댔던 문제였다. 답을 제출하면 "시간초과" 단어 하나로만 알려주지 말고 몇 초를 초과하였는지 알려줬으면 좋겠다. 물론, 문제에서 제시한 1초의 제한 시간이 지난 후에도 서버는 지속적으로..

파이썬 백준 1904번 실버3 https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 문제 보기 처음에는 00 타일을 하나로 묶어 가짓수를 줄여 생각해야 했는데, 힌트를 찾다 보니 피보나치 수열을 갖는 문제였다. 문제의 형태를 피보나치 수열로 이해를 해야 하는데 이 부분 접근이 쉽지 않았다. 아래의 그림을 통해 이해한 부분을 정리 하였다. 문제 풀기 이해의 핵심 부분으로는 N 이 증가하면서 타일이 오른쪽으로 하나씩 늘어나는데, 이 맨 오른쪽 타일 (빨간색)..

파이썬 백준 9148번 실버3 https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 문제 보기 재귀 함수를 사용하면 입력값이 같은 상황에서 반복되는 계산을 지속적으로 하기 때문에 속도가 많이 느려진다. 이를 해결하기 위해 동일한 입력값에 대한 계산의 결과는 미리 저장해 두고 필요할 때 불러와 속도를 현저히 상승시킨다. 문제 풀기 이전에 풀었던 24416번 (알고리즘 수업 - 피보나치 수 1) 문제를 통해 반복되는 계산 결과를 저장하여 동일한 계산을 이미..