나름 개발자의 IT블로그

문제가 그렇게 어렵지 않고 재미있는 문제들이 많아 남겨보고자 한다. (푸는대로 업데이트 할 예정..) A. 2의 보수 정수를 하나 입력받아 그 수의 2의 보수를 출력하면 된다. 입력받은 정수를 $a$라고 하면 $a \oplus (2^{32}-1) + 1$ 이 정답이다. (지난 코드포스 768에서 영감받음) B. 조커 찾기 카드 27장을 섞는 방법이 주어졌을 때 $n$번 섞고 난 후 조커($1$번 카드)가 어디있는지 찾는 문제이다. - 덱 위에서 13장을 왼쪽, 14장을 오른쪽으로 보낸다. - 배열 $a$가 있을 때 $i$가 홀수이면 오른쪽, 짝수이면 왼쪽에서 $a_i$장을 가져와 새 덱 밑에 추가한다. 문제에서 나타낸대로 구현하면 된다. 파이썬으로 큐를 사용해봤는데 시간초과가 나서 리스트 전체를 조작하는..

배열에서 특정한 수를 찾으려면 어떻게 할까? 앞에서부터 하나씩 찾아보면 될 것이다. arr = [9,3,7,5,6,2,0] x = 3 for i in arr: if x == i: print("찾았다") 최악의 경우는 배열 끝에서 찾은 경우이므로 $O(n)$만큼 시간이 걸릴 것이다. 만약 배열이 정렬되어 있다면 더 빠른 시간 안에 찾을 수 있다. 만약 배열이 arr = [1,3,5,7,8,9,10]이 있다고 하자. 이 배열에서 8이 있는지 찾고 싶다. 그럼 위 코드를 사용하여 찾는다면 찾는데 5번의 탐색이 필요하다. 하지만 정렬이 되어 있으니 다른 방법을 사용해보자. 우선 배열의 가운데 값을 선택한다. 만약 선택한 값이 찾는 값이라면 그대로 반환하고 아니라면 찾는 수보다 큰지 작은지 판별한다. 정렬이 되어..