백준에서 lower_bound, upper_bound는 정렬된 배열에서 상당히 많이 썼습니다. 파이썬에는 없을까요? bisect 모듈에는 bisect_right와, bisect_left가 있습니다. 쉽게 말해서 이 둘은 정렬된 list에서 upper_bound와 lower_bound에 대응되는데요. 어떻게 동작하는지 보겠습니다. 키가 정수인 경우에 대해서 생각해 보겠습니다. 먼저, 전자부터 보겠습니다. 일단 lo와 hi는 탐색 범위를 의미합니다. 배열 전체를 탐색하려는 경우에는 a와 x를 넣습니다. 여기서 a는 list이고 x는 기준 값을 의미해요. 여기서, 우리는 어떻게 범위를 좁히는지 볼 필요가 있는데요. a[mid]보다 x가 작으면 hi가 mid가 됩니다. 즉, 찾으려는 수 보다 a[mid]가 큰 ..
전체 글 검색 결과
c, c++에서 제가 꽤 많이 쓰던 것 중 하나는 삼항 연산자였습니다. 파이썬에는 없을까요? 예를 들어, a의 절댓값을 구하는 mabs 메서드를 생각해 보겠습니다. 이것은 아래와 같이 쓸 수 있습니다. a가 0보다 작으면, -a를 리턴합니다. 그렇지 않으면, if문에 걸리지 않으니 4번째 줄을 수행합니다. a를 돌려주는데요. 7번째 줄에 -1을 인자로 넣어서 mabs를 호출합니다. 실행 결과는 위와 같습니다. -1의 절댓값은 1이니, 의도한 결과대로 잘 나왔음을 볼 수 있어요. 이 링크를 보면, 중간에 이런 구문이 나옵니다. 이것은 C이면, x가 평가되고, 그렇지 않으면 y로 평가됩니다. 즉, C가 참이면, 노란색이 수행되고, 아니면 y가 수행됩니다. 이를 응용하면, mabs를 1줄로 바꿀 수 있습니다...
c언어를 공부하시다 보면, 한 번 쯤 막히는 부분이 있습니다. 배열 포인터. 쉽게 말해서 배열을 가리키는 무언가입니다. 나중에 행 우선 열 우선 방식을 할 때 다시 언급을 하고, 여기에서는 간단하게 언급을 하겠습니다. 이 글을 읽기 위해서 중요한 것은 배열은 배열 그 자체로 다루어야 한다는 점입니다. 4번째 줄을 보시면, 4 by 4짜리 배열이 선언되어 있습니다. 그리고 5번째 줄에, int (*p)[4] = &(a[0])이라 되어 있는데요. 좌항부터 해석해 보겠습니다. 시계 방향 rule에 따라서 보도록 하겠습니다. 먼저, 4번째 줄부터 해석되는데요. (*p)는 p가 포인터이다. 라는 의미입니다. 그런데, 어떤 포인터일까요? 돌려 보니까 [4]라고 되어 있습니다. 이것은 [4]개짜리의 원소를 가진다는 ..
java에서 computeifabsent랑, computeifpresent는 꽤 유용하게 쓸 수 있는 Map 메소드입니다. 이 중에서, 저는 후자를 위주로 설명하도록 하겠습니다. 먼저, computeifpresent 메서드에 대한 설명을 보겠습니다. 어려울 것은 없고요. key와 Bifunction을 받습니다. key가 이미 있는 경우에는, key와 value를 가지고 새롭게 mapping하는 것을 시도하는 함수입니다. 그런데 이 설명만 보아서는 어떤 일을 하는 지 알기가 쉽지 않아 보입니다. 예제를 작성해 보겠습니다. 먼저, 3가지 연산을 한 후에, map에 있는 내용을 출력하게끔 하였습니다. 결과를 보고 이야기 해 보겠습니다. 먼저, 처음에 맵은 비어 있었을 겁니다. 2를 추가하려고 하니 없었으므로,..
펜윅 트리는 구간합을 구할 때 상수를 줄이기 위해 이용할 수 있는 구조입니다. 유성 문제는 세그먼트 트리 대신에 펜윅을 써야 풀리는 문제로 유명한데요. 시간 복잡도의 특성상 상수를 줄여야 하는데, 레이지를 이용한 세그 트리는 느리기 때문입니다. 이게 어떤 식으로 동작하는지 보고, 간단하게 코드를 작성해 보도록 하겠습니다. 펜윅 트리는 다음과 같이 그릴 수 있습니다. 이들은 각각 [1], [3], [5], [7]을 담고 있는 노드입니다. 규칙을 찾아보면, 1, 3, 5, 7은 1의 배수이지만 2의 배수는 아닙니다. 다음에 1, 3, 5, 7과 비교했을 때 구간의 크기가 2배인 2와 6이 있습니다. 이들의 구간 크기는 2이고요. 각각 구간 [1, 2], [5, 6]을 담고 있습니다. 이 둘의 공통점은 2의 ..
최근댓글