[ 알고리즘 ]/오답노트25 [ BOJ 오답노트 ] 2231 파이썬 : 분해합 2022 02 07 1. 틀린 기록 2. 원인 분석 - 아주 다채롭게 오류가 났다^_^ (1) 런타임에러 (IndexError) 나는 처음에 이 문제를 1부터 n까지의 모든 수에 대해서 생성자의 분해합을 구해서 리스트에 저장하는 오류를 저질렀다. 근데 내가 리스트의 크기를 (입력받을 수 있는 가장 큰 값 + 1)을 했는데, 당연히 분해합은 그 값보다 크기 때문에 indexError가 났던 것이다. lst = [[] for _ in range(1000053)] n = int(input()) lstIdx = 0 for i in range(1, n+1): num = i sum = num while num // 10 != 0: sum += num % 10 num //= 10 sum += num lst[sum]... 2022. 2. 7. [ BOJ 오답노트 ] 1929 파이썬 : 소수 구하기 2022 01 29 1. 틀린 기록 2. 원인 분석 - 시간 초과는 항상 힘들게 한다~! 시간 초과 코드로 일반적인 소수 구하듯이 주어진 범위 내의 숫자들을 하나씩 검토해서 출력했다. - for문 안에 while문까지 있다보니까 시간 초과 판정이 난 것 같다. - 도저히 해결하는 방법이 생각이 안나서 문제의 서브 주제를 봤더니 '에라토스테네스의 체'라는 알고리즘으로 풀어야 한다고 써있었다. 3. 해결 - 에라토스테네스의 체 : 특정 숫자의 배수는 소수가 아니라는 법칙에 착안하여 2부터 N까지의 숫자에서 숫자들의 배수를 모두 제거한 뒤 제거되지 않은 숫자를 소수로 판별하는 방식 - 하나씩 다 검토하면서 제거한다고 하면 시간 복잡도가 크다고 생각할 수 있지만, 2부터 배수들을 다 지워나가면서 점점 더 검토할.. 2022. 1. 29. [ BOJ 오답노트 ] 2869 파이썬 : 달팽이는 올라가고 싶다 2022 01 28 1. 틀린 기록 2. 원인 분석 - 일단 시간 제한이 0.15초인 것을 보고, 단순히 while문으로 값을 하나씩 증가해가면서 구하는 문제가 절대 아닐 것이라고 생각했다. - 그러면서 계속해서 식을 만드려고 노력했는데 도저히 일반화가 안돼서... 여러가지 경우를 생각해보았는데 내가 가장 생각하지 못했던 부분은 바로 몫과 나머지에만 집착했던 것이었다. - '//'와 '%' 연산만을 가지고 식을 만드려다 보니까 계속 생각이 안 났던 것 같다. 3. 해결 - 높이에서 올라가는 높이를 빼주고 그 나머지 값에 대해서 올라갔다가 내려가는 값으로 나누어서 얼만큼 올라가야 하는지 구했다. - 그 값이 만약에 4.1번이 나온다면 네번을 올라갔다 내려갔다 한 후에 올라가는 작업을 했다는 것을 의미한다... 2022. 1. 28. [ BOJ 오답노트 ] 2839 파이썬 : 설탕 배달 2022 01 26 1. 틀린 기록 2. 원인 분석 - 이번에도 역시 "맞.왜.틀"이었다. 분명히 모든 예제에서 정답이 나왔는데 BOJ에서는 틀렸다고 판정이 났다. - 동적 프로그래밍으로 문제를 풀었는데, dp 리스트를 초기화하는 과정에서 생각하지 못한 오류가 났던 것 같다. - for문 안에서 if문이 있는 이유는 목표 무게에서 3을 뺀 무게와 5를 뺀 무게 모두 다 만들 수 없는 경우일 수도 있기 때문이다. 3. 해결 - from math import inf를 해서 무한 값을 아예 라이브러리에서 가져왔다. - 그랬더니 굳이 for문 안에서 if문으로 검사해 줄 필요도 없어졌다. - 너어무 궁금해서 백준에 질문을 올려놨는데 아직 댓글이 없다. 댓글 내용을 아래에 첨부할 예정이다. ▶ 감사합니다 선생님... 2022. 1. 26. 이전 1 2 3 4 5 6 7 다음
