전체 글 검색 결과

해당 글 904건
등차수열에서 중간에 빠진 수 구하기 : binary search 기법으로 풀면 된다.

오늘 새벽에 들어온 문제 하나 보겠습니다. 당연하게도, brr은 오름차순으로 sort가 된 상태입니다. 쉬운 문제는 아닙니다. 다만, 아이디어를 얻을 수 있는 것 중 하나는 이진 검색이라는 것이 있어요. 링크 들어가셔도 좋을 듯 싶어요. 이것을 아신다는 전제하에 설명을 드리도록 하겠습니다. 먼저, 등차 수열 {a(1), a(2), ... , a(n)}이 있다면 임의의 1= 0일 때, a = 0이고 b = 1이거나, 혹은 a = 1이고 b = 0이여야 합니다. 그러면, 좌측에서 수가 빠지지 않았다면, 우측에서 탐색을 해야 하고, 반대로, 좌측에서 수가 빠졌다면, 왼쪽 구간을 탐색해야 할 거에요. 데이터를 볼까요? 문제를 보면, arr[mid] - arr[le]의 값은 8입니다. ..
자료알고/알고리즘 2019. 12. 10. 03:43
소코반 구현해 보기 : 맵 상태를 쪼개면 답이 보인다.

구현 8번째 시간입니다. 실전 문제 하나를 풀면서, 여러 가지 기법들을 다뤄보겠습니다. 소코반 게임은 캐릭터와 박스가 있습니다. 이 박스들을 적절히 목표 지점에 이동시켜야 하는 게임입니다. 아. 옛날에 많이 있었던 게임 중 하나입니다. 그냥, 우리는 캐릭터를 명령에 맞게 이동시킨 다음에 맵의 상태를 출력하는 것이 목표라면 목표라고 할 수 있겠네요. 그런데, 맵의 상태를 보니까, 목표 지점에 있는 ~가 눈에 보입니다. 즉, 목표 지점이면서 박스가 있는 곳이라던지, 목표 지점이면서 캐릭터가 있는 곳이라던지. 즉, A and B 조건이 눈에 밟힙니다. 이렇게 되어버리면 경우의 수를 처리해야 할 것이 상당히 많아집니다. 이것을 적절히 분해를 해서 처리를 하는 방법을 고민해 봅시다. 물론, 제 코드를 조금 더 응..
구현 2019. 12. 9. 20:29
java this : 현재 객체를 참조한다.

인스턴스를 생성했습니다. 예를 들어, MyCar 객체라면 MyCar a = new MyCar(); 이런 식으로 생성했을 거에요. 그러면, 우리는, a.run()과 같은 메소드를 호출할 수 있을 거에요. 그런데, a.run 메서드 안에서, 자기 자신을 참조하려면 어떻게 해야 할까요? 영어 시간으로 돌아가 봅시다. 지시 대명사 중에서 this, that. 이런 것들이 있어요. 이 중에 this는 이것 이라는 뜻을 가져요. Mycar a = new MyCar(); 를 호출하면, 힙에 인스턴스 변수들이 생성이 됩니다. 그리고 a는 힙에 생성된 무언가를 가리키고 있을 겁니다. 여기서 차 이름에 맞게 부속품들을 setting 한다고 생각해 봅시다. 이 일을 MyCar 클래스가 다 해버리면 힘들 거에요. 차는 달리고..
코딩/Java 2019. 12. 8. 20:27
인트로 정렬 : c++의 sort는 왜 최악의 경우에도 빠르게 동작하는가?

C++의 sort는 어떻게 O(nlogn)의 복잡도가 보장될 수 있을까요? 저번에 compare 함수가 항상 True를 리턴할 때에 어떤 일이 일어나는가? 편에서 이 함수를 뜯은 적이 있었습니다. 그 기억을 되살려서 보도록 하겠습니다. Quick sort는 pivot을 어떻게 선택하느냐가 중요하다고 했어요. 저번에 median 값을 가지고 pivot값을 생성한다는 것을 알 수 있는데요. 이 방법을 저격하는 데이터가 있다는 것이 알려져 있어요. 그러면 이 방법을 어떻게 해결할까요? nth_element에도 적용되는 기법 중 하나인데요. 호출 깊이의 제한을 둡니다. first와 last가 다른 경우, __introsort_loop를 호출합니다. 그런데, 이것은, 3번째 인자에 이상한 __lg(__last -..
레퍼런스/분석 2019. 12. 7. 21:25
java yield 메서드 : 양보한다는 힌트를 준다.

이번 시간에는 Java의 yield 메서드에 대해서 알아보도록 하겠습니다. 사실, 이것은 백준 사이트에서 yield 관련한 질문이 들어와서 레퍼런스 보면서 조금이나마 알게 되었습니다. 물론, 그 질문에 대한 답은 pc 레지스터와 쓰레드가 어떤 영역을 독립적으로 가지는지에 대해서 찾아보세요. 였지만요. 일단 이 함수는, 설명부터 보는 게 중요할 듯 싶어요. 레퍼런스 사이트에 있는 설명 중 일부만 보도록 하겠습니다. current thread와 스케쥴러가 나오고, 힌트가 나옵니다. 정확하게 해석은 못 하겠지만, 현재 돌고 있는 쓰레드에 대한 무언가의 힌트인 것으로 보여요. 계속 보면 is willing to yield가 나오는데, 양보를 한다는 것이에요. 무엇을? 그것의 current use를. 쓰레드가 프..
OS/이론 2019. 12. 6. 06:10