전체 글 검색 결과

해당 글 904건
큰 수를 어떻게 좌표 압축하면 좋을까요?

안녕하세요. 오늘은 큰 수를 어떻게 좌표 압축을 하는지 알아보도록 하겠습니다. 대소 비교하는 방법도 익힐 겸. 백준 17126을 보면, 일반적인 그냥 쿼리 문제인 것 같아 보입니다. key의 조건을 보기 전 까지는요. 여기서, 모든 key 값의 범위는 1이상 (10^99)-1 이하입니다. 여기서 좌표 압축을 한다는 것은, 들어오는 Key나, 중요한 수에 대해서 순서를 재정렬 하는 것을 의미하는데요. 그러려면, sort가 되어야 할 거에요. 정렬을 하기 위해서는 두 큰 수를 compare 해야 합니다. 이것을 어떻게 해야 할까요? 일단 long long 형이나, int형, 그리고 __int128로는 cover가 되지 않음은 자명합니다. 먼저 어떤 수 A가 B보다 작다면 무엇을 만족해야 하는지 생각해 봅시다..
구현 2020. 3. 4. 02:10
플로이드 알고리즘 : 어떻게 최단거리가 갱신되는가?

안녕하세요. 백준 chogahui05입니다. 플로이드 알고리즘은, 알고리즘 수업 시간에 많이 배우실 거에요. 음의 사이클이 없는 경우에, 이 알고리즘이 어떻게 동작하는지 알아보도록 하겠습니다. 이 코드는 몇 줄 안 되니 외우시는 분들도 많으실 거라 생각이 듭니다만. 그래도 보도록 하겠습니다. 9번째 줄의 for loop를 보면 n번 loop를 돌린다는 것을 알 수 있어요. 다음에 11번째 줄에 있는 for loop, 13번째 줄에 있는 for loop, 15번째 줄에 있는 if문 안을 보시면, 조건이 맞으면 dist[i][j]를 업데이트 한다는 것을 알 수 있어요. 음의 사이클이 없다면, a에서 a로 오는 비용은 0보다 크거나 같습니다. 따라서, 같은 장소를 2번 이상 방문하는 것은 손해라는 것을 알 수..
자료알고/알고리즘 2020. 3. 3. 05:20
java thread stop : 왜 권장하지 않는 함수가 되었을까요?

All or nothing. 원자성이라고 이야기를 합니다. 어떠한 연산이 들어왔을 때, 실행이 되거나, 그렇지 않거나. 둘 중 하나의 상태가 되어야 합니다. 데이터 베이스에서 '트랜잭션' 이라는 것을 배우면 ACID라 해서 나오는 용어이기도 합니다. 아마, 그것을 배우시면 이런 그림도 많이 보셨을 거라 생각합니다. Commit은 Q가 반영이 된 상태를, Abort는 Q가 반영이 되지 않은 상태를 의미합니다. 만약에 Q를 execute 하라는 명령이 들어왔는데, 잘 수행하다가 실패한 경우에는 Fail로 가야 할 겁니다. 이 경우에는, 부분적으로 수행했던 명령들이 결과에 반영되면 안 됩니다. 잘 수행이 된 경우에는 둘 중 하나입니다. 취소를 하던지, 반영을 하던지. 그러면, 위에서 말하는 '원자성'이 깨지는..
OS/이론 2020. 3. 1. 23:58
누적된 변환과 lazy propagation 알고리즘

안녕하세요. 2 ~ 3편에 걸쳐서, 레이지 프로퍼게이션을 적용한 세그먼트 트리를 쓰도록 하겠습니다. 세그먼트 트리에 쓰이는 lazy 기법을 1줄로 요약하면 아래와 같습니다. 네. 앞으로 쓸 2 ~ 3편 글에 대한 핵심입니다. 이것만 정확하게 이해하시면 됩니다. 정말 중요한 키워드는 굵게 강조 표시까지 했는데요. 변환, 흡수, 전파. 이 셋입니다. 변환, 흡수, 전파? 이게 대체 무엇을 의미할까요? 이번 시간에는 이 중에 첫 번째 키워드와 두 번째 키워드인 변환과 흡수에 대해 알아보도록 하겠습니다. 왜 자식에 전파하는지는 다음 포스트에서 이야기 해 보도록 하겠습니다. 1번 변환을 생각해 봅시다. 이 변환을 함수 f(v)로 표현해 봅시다. 그러면, f(v) = v + a가 됩니다. 다음에, 2번 변환을 생각..
자료알고/자료구조 2020. 2. 29. 22:37
c언어 getc fgetc 함수 : 문자 하나를 읽어봅시다.

다음 코드를 봅시다. FOO(x)는 ((x)*(x))로 define이 된 매크로입니다. 그리고 6번째 줄에 FOO(p(0)); 이 있어요. 이것은 어떻게 대치가 될까요? 만약에 위와 같이 대치가 된다면, 어떻게 될까요? p가 2번 호출됩니다. 이것만 보면 이게 굳이 왜. 라는 생각이 드실 수도 있을 거에요. 자. 그러면 질문을 바꿔 봅시다. FOO(u = p(0))은 어떻게 대치가 될까요? 만약에, 이렇게 대치가 된다면 어떨까요? 봐도 모르겠으니, wandbox에서 돌려보겠습니다. operation on 'u' may be undefined. 라고 나옵니다. 음.. 뭔 이야기인지는 모르겠지만, u에 대한 연산이 정의되지 않는다. 정도로 해석을 하면 됩니다. 사이드 이펙트가 있다고 생각해도 무난합니다. 그..
코딩/C 2020. 2. 26. 17:37