개발하는 개구리

🐸 문제 정보 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 🤖 알고리즘 DP (라고 하지만, 그냥 수학으로 풀었다.) ⏱️ 풀이 시간 약 10m (중간에 맥 업데이트 오류때문에 잠깐 멈추고 체크를 안함..) 📝 풀이 보자마자 조합문제다! 싶었다. mCn 으로 풀면 되지만, 문제는 itertools의 combinations를 이용하면 세 번째 테케에서 엄청나게 오래 걸린다. 그래서 직접 수를 구해야하나? 싶었지만, math.comb 모듈이 있었다. 이 모듈은 조합을 뽑아주는게 아니라, 조합의 경우의 수를 ..

🐸 문제 정보 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 🤖 알고리즘 이분탐색 ⏱️ 풀이 시간 20.59 📝 풀이 간단한 조건이 추가된 이분탐색 문제였다. 크게 어려운 것 같진 않았는데 여전히 어느 상황에서 start와 end 값을 뭘로 바꾸어야하는지 헷갈린다. 사실 나무 길이를 구하는 과정 때문에 시간초과가 당연히 날거라고 생각했는데 이게 안나네...? 🧑‍💻 나의 답 # pypy3 import sys input = sys.stdin.readline n, m = ..

🐸 문제 정보 20920번: 영단어 암기는 괴로워 첫째 줄에는 영어 지문에 나오는 단어의 개수 $N$과 외울 단어의 길이 기준이 되는 $M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 100\,000$, $1 \leq M \leq 10$) 둘째 줄부터 $N+1$번째 줄까지 외울 단 www.acmicpc.net 🤖 알고리즘 정렬 ⏱️ 풀이 시간 05.38m 📝 풀이 이제 파이썬 정렬은 웬만하면 쉽게 풀 수 있다..! 단어를 딕셔너리로 관리하면서, 단순히 조건대로 정렬해줬다. 🧑‍💻 나의 답 # pypy3 import sys input = sys.stdin.readline n, m = list(map(int, input().rstrip().split())) words = {} for _ in..

🐸 문제 정보 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 🤖 알고리즘 백트래킹 ⏱️ 풀이 시간 60m+ 📝 풀이 예전에 한 번 풀었던 문제인데도 기억을 못해서 오래걸렸다.. 알파벳 26개에 대해, 가르쳤는지 여부를 알 수 있는 26개의 요소 리스트를 선언한다. 각 알파벳에 대해서 True(가르침)을 넣어보고 학생이 총 알 수 있는 단어의 개수를 파악한 뒤, 해당 알파벳을 False(가르치지 않음)으로 바꿔보면서 백트래킹을 실시한다. 🧑‍💻 나의 답 # pypy3 import sys input = ..

🐸 문제 정보 1174번: 줄어드는 수 음이 아닌 정수를 십진법으로 표기했을 때, 왼쪽에서부터 자리수가 감소할 때, 그 수를 줄어드는 수라고 한다. 예를 들어, 321와 950은 줄어드는 수이고, 322와 958은 아니다. N번째로 작은 줄어드는 www.acmicpc.net 🤖 알고리즘 백트래킹 ⏱️ 풀이 시간 60m+ 📝 풀이 백트래킹을 오랜만에 풀어서 그런가 생각보다 어렵게 느껴지는 문제였다. 임시 배열을 두고, 가장 마지막 숫자와 비교하여 넣을 수 있는 수 들을 하나씩 채워나가면 풀 수 있었다. 🧑‍💻 나의 답 # pypy3 import sys input = sys.stdin.readline n = int(input().rstrip()) temps = [] def bt(): if temps: res..

🐸 문제 정보 1166번: 선물 민식이는 아이들에게 선물할 같은 크기의 작은 박스를 N개 가지고 있다. 모든 작은 박스는 정육면체이고, 크기는 A × A × A 이다. 민식이는 이 작은 박스를 크기가 L × W × H 인 직육면체 박스에 www.acmicpc.net 🤖 알고리즘 이분탐색 ⏱️ 풀이 시간 26.04m 📝 풀이 처음에 수학 문제라고 확신하고 풀었다. 이유는 (L / A) * (W / A) * (H / A) = N인 경우의 A 값을 찾으면 되니까... 하고 풀었으나 실패. 결국 검색의 힘을 빌렸고, 이분탐색 문제인 것을 알았다. start는 0, end는 L, W, H 중 가장 큰 값을 선택 end의 최대 값과 비교했을 때 반복문 100번 정도 돌리기 가능 (2 ^ 100) 블럭 개수는 (L ..

🐸 문제 정보 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 🤖 알고리즘 이분탐색 (이지만 나는 그리디로 풀었..다) ⏱️ 풀이 시간 10.58m 📝 풀이 유형은 이분 탐색이었지만, 문제를 봤을 때 이분탐색보다 그리디가 먼저 떠올랐다. 이분탐색 풀이도 아래에 있다. 입력 값을 오름차순으로 정렬 (현재까지 남은 값 / 남은 인원)과 현재 보고있는 값을 비교한다 만약 현재 보고 있는 값이 더 작다면, 예산 최대 값에서 현재 보고 있는 값을 빼고 res와 뺀 값을 비교한다 반대의 경우, (현재까지 남은 값 ..

🐸 문제 정보 17266번: 어두운 굴다리 인하대학교 후문 뒤쪽에는 어두운 굴다리가 있다. 겁쟁이 상빈이는 길이 조금이라도 어둡다면 가지 않는다. 따라서 굴다리로 가면 최단거리로 집까지 갈수 있지만, 굴다리는 어둡기 때문에 빙 www.acmicpc.net 🤖 알고리즘 구현 ⏱️ 풀이 시간 29.04m 📝 풀이 실버 4 문제였음에도 초반에 구현 방법을 잘못 설정하여 시간이 오래 걸렸다. 왼쪽 가로등과 비교하는 형식으로 구현했다가, 이렇게 되면 오른쪽 가로등과의 최적의 길이를 구할 수 없었다. 고친 풀이 방법은 아래와 같다. 가로등 시작 위치와 끝 위치는 각각 0과 m과 차이를 비교해야함 두 번째 가로등부터는 이전 가로등과 사이의 중간 값을 올림하여, 현재 저장된 가로등과 최대값으로 갱신 🧑‍💻 나의 답 #..

🐸 문제 정보 3165번: 5 N과 K가 주어졌을 때, N보다 크면서 5가 적어도 K번 포함되는 가장 작은 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 🤖 알고리즘 그리디 백트래킹 ⏱️ 풀이 시간 60m+ 📝 풀이 사실 완벽하게 풀이하지 못한 문제이다. 질문이 엄청 깔끔하고, 이해하기 쉬운 반면... 정말 엄청나게 틀렸다. 사실 아직까지 틀린 이유를 모르겠다. 기존에 풀이 방식은 아래와 같았다. (num은 n + 1을 리스트로 바꾼 변수, idx는 -1) 백트래킹 함수 내에서 5가 k개 이상이면 멈추도록 함 num[idx]가 5라면 백트래킹 함수를 재귀하는데, idx 값을 -1 해줌 자리수를 넘겨주기 위해서 num[idx]가 5보다 작은 경우, 5로 만들고 idx 값을 -1 하여 재귀..

🐸 문제 정보 15724번: 주지수 네모 왕국의 왕인 진경대왕은 왕국의 영토를 편하게 통치하기 위해서 1X1의 단위 구역을 여러 개 묶어서 하나의 거대 행정구역인 주지수(州地數, 마을의 땅을 셈)를 만들 예정이다. 진경대왕은 www.acmicpc.net 🤖 알고리즘 DP ⏱️ 풀이 시간 43.56m 📝 풀이 처음에 당연히 BFS라고 생각하고 푸는 바람에 어마어마하게 시간이 소요됐다. 이후에 DP + 누적합인 것을 알았음에도 풀이 방법이 바로 떠오르지 않았다. 사실 DP 문제들 중에서는 점화식을 찾기 쉬운 편의 문제였음에도 이렇게 시간이 오래 걸린다는 것은... DP에 대한 연습이 부족하다는 것은 당연하고, DP는 연습해도 실전에서 못풀 가능성이 높다는게 무슨 소리인지 느낄 수 있었다. 누적합으로 (0,0..