전체 글 검색 결과

해당 글 904건
백준 배열 돌리기 4 : 요소별로 나누면 어렵지 않다.

오늘은 어떤 것을 배워볼까요? 시계처럼 x칸씩 회전하는 연산을 배워보겠습니다. 17406번 배열 돌리기 문제를 보겠습니다. 문제가 요구하는 것은 간단합니다. 그 중에서 가장 중요한 것은 rotate 연산입니다. 이것은 정사각형을 시계방향으로 1칸씩 돌린다는 의미입니다. 문제가 다소 복잡하니, 분할해서 생각해 보도록 하겠습니다. 먼저, 돌아가는 단위를 기준으로 나누면, 기준점을 하나 잡을 수 있습니다. 이 기준점들을 먼저 잡아보겠습니다. 먼저 회전 반경이 1이라고 해 보겠습니다. 0번만 있는 요소, 그리고 1 ~ 8까지 있는 요소 둘로 나눠보겠습니다. 그러면, 제가 보라색으로 칠한 것은 각각의 요소들의 기준점으로 볼 수 있습니다. 그리고, 1번은 1 ~ 8은 하나의 요소로 볼 수 있습니다. 이들이 1칸씩 ..
구현 2020. 4. 14. 00:25
linux grep 명령어 : 패턴만 잘 작성하면 꽤 강력하다.

패턴이 일치하는 내용을 빠르게 찾으려고 할 때, grep 명령어는 자주 쓰는 편입니다. 패턴이라 하면, regex가 들어갈 거 같은데.. 네. 사실 그것을 조금이라도 알면 꿀은 먹을 수 있다는 장점이 있습니다. 작업 속도가 중요한 환경에서는. 눈치 안 보이게 하려면 익혀두는 수밖에 없는 듯 싶어요. file에서 패턴과 일치하는 부분이 있는 행을 결과값으로 내보냅니다. 그런데, 사실 이런 패턴을 생각보다 많이 씁니다. 명령어 1의 결과를 input으로 받아서, grep option pattern을 수행합니다. 예를 들어, ls -ail이 명령어 1이였다면, ls -ail의 결과에, pattern과 일치하는 행을 리턴합니다. 생각보다, 이는 매우 강력한 도구가 될 수 있습니다. 예를 들자면, 프로세스들 중에..
OS/리눅스 2020. 4. 12. 16:52
java synchronizedmap : 데이터가 포장된 잠금 객체

Collection 중에는, SynchronizedMap이 있습니다. 대충 Synchronizedxxx라고 해 보겠습니다. 이것들은 어떠한 구조로 되어 있을까요? 먼저 Collcetions.Synchronizedxxx로 호출하는 것을 보아서는, 내부 class로 선언이 되어 있는 것을 알 수 있습니다. 이들은, Map 꼴의 맵 객체와, Object 객체인 mutex를 가지고 있습니다. 생성자 안에는, 인자로 넘겨받은 Map을 대입하는 부분이 있습니다. HashMap도 있고, TreeMap도 있을 텐데. 이렇게 해도 문제가 없나요? 고양이는 동물이고, 개도 동물이잖아요. 그러니 이들을 동물이라고 하는 것은 크게 무리는 없습니다. 다만, 넘겨받은 객체를 가지고 bark를 호출할 때에는 이야기가 달라지는데요...
레퍼런스/분석 2020. 4. 11. 21:09
항등식으로 구현체를 외울 수 있는 확장 유클리드 알고리즘

안녕하세요. 백준 chogahui05입니다. RSA 알고리즘을 알기 위해서, 알아야 하는 것이 몇 가지 있는데요. 그 중 하나인 확장 유클리드 알고리즘을 알아보겠습니다. 사실 CRT라던지, 페르마의 소정리도 알아두면 좋기는 합니다. 이게 무엇을 구하는 것인지 알아보겠습니다. a와 b가 매우 큰 수일 때, 이 값은 어떻게 구하는 것이 좋을까요? 일단, gcd(a,b)의 값이 k이고, k값이 1이 아니라고 해 봅시다. 그러면, a = ka', b = kb'으로 다시 쓸 수 있습니다. gcd(a,b)값이 k이므로, a'과 b'도 정수입니다. x와 y가 정수라면 a'x + b'y도 정수입니다. 그러면, 1은 k의 배수여야 합니다. 그렇지 않습니다. 따라서, a와 b의 최대 공약수가 1이 아니라면, ax + by..
자료알고/알고리즘 2020. 4. 9. 23:42
랜덤 접근이 가능한 deque 자료구조를 chunk로 구현하면 어떤 이점이 있을까요?

deque를 공식 레퍼런스 사이트에서 보면, Chunk로도 구현이 된다고 되어 있습니다. 그러면, Chunk로 구현했을 때, 장점이 무엇일까요? 일단, deque가 Random 접근이 되려면, 기본적으로 연속적이여야 합니다. List는 Random access를 지원하지 않습니다. 더 정확히 이야기 하면, base 주소가 있고, 그것을 통해서 i번째 index에 접근할 수 있어야 합니다. 1차 구조의 덱을 생각해 보겠습니다. 원래 4개의 원소가 있었고, 5를 어딘가에 추가한다고 해 보겠습니다. 원래 capacity가 4였다면, 하나를 추가하려는 순간 추가하지 못하게 될 겁니다. 그러므로 확장 연산이 수행이 될 겁니다. 그러면 확장된 후에 기존의 원소가 어떻게 들어가는 것이 좋을까요? 이렇게 들어가는 것이..
자료알고/자료구조 2020. 4. 7. 01:08