알고리즘 2

[백준]수들의 합2

문제 출처: https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 오랜만에 알고리즘.. 빅리더 교육을 받은 9주 동안 못푼 문제들을 푸는 시간을 가졌다. 문제를 그냥 단순하게 이중 for문을 사용하면 끝날줄알았는데, 시간초과.. 이중 for문을 돌려도, index로 끊는다고 해도 시간초과가 났다.. 결론은 아이디어가 문제였는데, for문을 돌다가 숫자가 원하는 m보다 작으면 끝나는 index를 늘려야했고, m..

[파이썬] 리스트, 딕셔너리 시간 복잡도 체감하기

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 사실 list가 찾는데 시간이 오래걸린다고 듣긴 했어도 확 체감이 없었는데 이 문제 하나로 엄청나게 체감이 되서 블로그 글을 작성한다. 문제를 잘 살펴보자, 실버4 문제에 수찾기... 매우 간단해보인다. 근데.. 정답비율이 뭔가 이상한데? 29.997% 자그마치 30%가 안된다. 여기서 조건을 살펴보면 시간 제한 1초, 메모리 제한 128MB => ..