파이썬 백준 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) 문제를 통해 반복되는 계산 결과를 저장하여 동일한 계산을 이미..

파이썬 백준 1620번 실버4 https://www.acmicpc.net/problem/1620 문제 보기 N 개의 단어를 입력한 후 이를 사전 삼아 M 번에 걸쳐 답안 요구 조건에 따라 문자인 이름 또는 순서인 숫자를 출력하는 문제이다. 문제 풀기 pokemon_encyclopedia = {} 를 set 으로 지정. 포켓몬의 이름을 하나하나 입력받되 pokemon_encyclopedia[i] = pkm pokemon_encyclopedia[pkm] = i 를 통해 딕셔너리를 작성 시 key, value 를 "순서: 이름" 과 "이름: 순서" 둘 모두 저장. 작성된 딕셔너리를 확인해 보고자 중간 프린트해봄. M 번의 for 문을 돌리면서 원하는 답안을 입력받아 그것이 숫자일 때는 포켓몬 이름 문자를 출력..

파이썬 백준 24416번 브론즈1 https://www.acmicpc.net/problem/24416 24416번: 알고리즘 수업 - 피보나치 수 1 오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍 www.acmicpc.net 문제 보기 오랜만에 보아 친숙한듯 친숙하지 않은 피보나치 수. 문제 풀기 재귀함수를 사용하게 되면 지속적인 함수를 호출하는 과정을 거치면서 최종적으로 n = 1 을 터치하고 return 을 통해 다시 돌아오는 과정을 거치게 된다. 게다가 피보나치 수열의 특성상 n - 1 과 n - 2 를 재귀함수로 각각 다시 돌려야하는 비효율적이기까지.. 동적 프로..

파이썬 백준 14425번 https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 문제 보기 문제 풀기 아무 생각 없이 쉬워 보이는 문제를 선택하고 풀고 나서, 기록과 정리를 위해 이곳에 글을 쓰다가 이 문제는 arrray 를 사용하는 게 아니라 set() 을 사용해야 한다는 생각이 들었다. 다시 수정하여 정답을 제출. set() 사용 연습을 하자. N 번 받아오는 각 문자열을 S 에 차례대로 추가를 한 후, set 또는..