본문 바로가기

코드103

The Grid Search https://www.hackerrank.com/challenges/the-grid-search/problem 빠른 탐색을 위해 2차원 부분합을 사용했는데... 오히려 문제가 있었다. 예를 들면 다음이 같은 결과로 나와서 그랬다. sum([1,0,0]) == sum([0,0,1]) 결국 부분합은 빠른 인덱스 탐색을 위해서만 사용하고, 부분합이 서로 같은 곳을 발견하면 거기서는 문자열 매칭을 통해 일치 여부를 조사했다. 선배들의 사례를 보니 루프만 돌려도 충분한 것 같다... def gridSearch(G, P): grid_sum = [0] * len(G) for i in range(len(grid_sum)): grid_sum[i] = [0] * len(G[0]) for y, row in enumerate.. 2021. 10. 28.
Non-Divisible Subset https://www.hackerrank.com/challenges/non-divisible-subset/problem 이거 실패하고 선배들의 풀이를 봤는데도 이해가 안되어서 3일 끙끙되었는데 예제를 직접 풀어보며 관계를 파악해보니 금방 되었다.... 역시 내 두뇌와 손을 사용해야 한다... import collections def foo(nums, k): ''' 이것은 나머지의 관계를 파악하는 문제이다. 문제에서 k는 나누는수로 주어진다. nums의 숫자들은 k로 나누어 나머지가 같은 것끼리 집합을 만들 수 있다. 이들 중 두 집합을 p, q라고 하자. 집합을 구성한 나머지들은 어떤 관계를 갖고 있다. 각각의 집합을 만들게 한 나머지를 P, Q라 하자. 이들은 P + Q = k라는 관계를 가진다. 이것.. 2021. 10. 25.
2110번: 공유기 설치 (acmicpc.net) 2110번: 공유기 설치 (acmicpc.net) 쉬운 문제로 생각했지만 문제 자체를 잘못 이해했다... 잘못 이해한 내용을 쓰는 건 불필요한 일일 것이다. 0,1개의 공유기는 조건에 없다. 2개의 공유기는 무조건 양극단에 배치된다. 그래야 문제의 조건대로 "가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다"를 만족할 수 있다. 3개의 공유기는 예제를 살펴보자. 3개의 공유기를 수평선 위치한 집에 설치한다고 하자. [1] [2] [4] [8] [9] 3개의 공유기 간의 거리가 비슷하게 배치하는 방법은 1,4,8일 것이다. 1,4,9는 일종의 함정이다... 따라서 답은 3이 된다. 이 문제에 실패한 이유는 다음과 같다. 첫째 해석의 실패, 둘째 이진 탐색으로 얻은 값을 맹신한 점이다... 2021. 9. 14.
하노이의 탑 11729번: 하노이 탑 이동 순서 (acmicpc.net) def hanoi(n, frm, to, aux) -> int: if n == 1: print(f'{frm} {to}') return 1 hanoi(n - 1, frm, aux, to) print(f'{frm} {to}') hanoi(n - 1, aux, to, frm) K = int(input()) # K = 20 print(2 ** K - 1) hanoi(K, 1, 3, 2) 재귀는 큰 문제를 분할해서 처리하는 특성 상 작은 문제를 해결하면 큰 문제도 해결된다. 수학적 귀납법처럼 k = 1, 2인 경우만 해결하면 자동으로 처리가 된다. 그를 위해서는 움직이는 방법을 재연할 수 있어야 한다. 일단 k = 1인 경우를 보자. 간단히 from ->.. 2021. 8. 4.
터렛 1002번: 터렛 (acmicpc.net) 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net 두 원의 교점이 2개인 경우를 구하는 것만 따져보자. 삼각형 세 변의 길이를 알면 제 2 코사인 법칙으로 모서리의 코사인 값을 얻을 수 있다. 코사인 역함수로 라디안 값을 얻으면 이걸로 삼각함수를 실행해서 다른 변의 길이를 구하여 교점을 얻을 수 있다. 한편 두 원의 중심을 잇는 직선의 각도 탄젠트 역함수로 얻어낼 수 있다. 이를 기준으로 라디안 값을 더하거나 빼서 두 개의 각을 얻는다. 이것이 두 원의 교점이 된다. import math T = int(input()) f.. 2021. 8. 3.
연역 가이드 템플릿 클래스의 인자 연역은 가끔 퍼즐을 푸는 것 같은 느낌을 받을 때가 있다. 처음 본격적으로 템플릿 클래스를 작성했을 때 lvalue 참조가 넘어가는 것을 모르고 며칠을 낑낑댄 적이 있었다. 그래서 타입의 한정자를 제거하기 위해 std::decay_t를 즐겨 사용했다. 그래도 잘 안될 때면 또 다른 템플릿 클래스를 만들어 몸체가 되는 클래스로 유도했다. 허나 이제 연역 가이드의 힘을 빌리면 그런 것을 아주 쉽게 해결할 수 있다. template struct List { template List( ITER&& begin, ITER&& end ) : _list{ begin, end } {} List( std::initializer_list&& v ) : _list{ v } {} private: std::.. 2021. 5. 22.
GPUView를 위한 log.cmd가 실행되지 않을 때 일단 관리자 모드로 콘솔을 실행시킨다. 그리고 log.cmd를 실행시키면 이런 오류가 생길 수 있다. C:\Program Files (x86)\Windows Kits\10\Windows Performance Toolkit\gpuview>log.cmd 4000은(는) 예상되지 않았습니다 배치 스크립트 내부를 보면 오류 원인은 다음에 있다. findstr /sipn /C:"Total Physical Memory" me.txt > me2.txt 더 보면 systeminfo.exe를 실행시켜 메모리 정보를 얻는데 로케일이 한국으로 되어 있을 경우 해당 문자열이 없다. 따라서 오류가 발생한다. 따라서 코드 페이지를 바꿔주고 log.cmd를 실행하면 해결이 된다. chcp 437 2021. 5. 13.
Game Server Performance on Tom Clancy's The Division 2 https://www.youtube.com/watch?v=bcXxyKqgV0c 주제: 서버에서 대규모 사용자 유지하기 코드 아키텍처 퍼포먼스 문제 디버깅, 모니터링위한 툴 프로세스 케이스 스터디 소개 3차원 클라이언트, 서버, 권한 서버 1000명 이상 수용, 20000 NPC 20fps이며, PVP만 30fps로 처리 플레이어가 존에 도달할 때만 로딩 처리 다크존: 플레이어가 집결할 것으로 예상되는 지점 서버 역할 월드 업데이트: AI, 플레이어, 미션, 스킬 싱글 스레드 천개 이상의 월드가 존재 병렬화 작업 짧은 작업: 높은 순위, 월드 업데이트 긴 작업: 저장, 백그라운드 데이터 업데이트 월드는 플레이어가 있을 때만 존재 최대한 병렬화 처리 40 코어 36: 짧은 작업 위해 할당 2: 긴 작업 위해.. 2021. 4. 20.
std::tuple<Ts...> ➔ std::tuple<U<Ts>...> 최근의 즐거움은 템플릿 프로그래밍이다. 템플릿 프로그래밍은 지적 호기심을 자극시키는 것이 있다. 어떤 문제에 대한 결정적이고 순수한 해결 방법을 찾아야한다. 변수를 조작하거나 동적 분기를 허락하지 않는다. 오로지 컴파일 타임에 해결해야한다. 어떤 로직을 템플릿 프로그래밍으로 해결했을 때의 즐거움은 이루 말할 수 없다. C++을 그저 객체지향언어로 사용한다면 C#이 더 좋은 선택이라고 생각한다. C++은 템플릿 프로그래밍을 통해 무한의 개념에 접근한다. 당신은 로직을 추상화시켜야 한다. 도구가 그것을 강제한다. 컴파일 시간이 길어지고 쓸데없이 템플릿 처리가 많아져 메모리를 많이 차지하는 부작용도 있다. 허나 동적 분기의 제거로 인한 최적화 가능성 무엇보다 지적 즐거움 때문에 포기할 수 없다. 최근에 맞닥뜨.. 2021. 3. 25.
위치 지정 new 이 방법은 이렇다. 힙에서 할당하는 대신 인자로 건네진 포인터를 기점으로 할당하고 생성자를 호출한다. 영어로는 placement new라고 불린다. #include #include struct Test { int v0{}; Test() { std::cout 2021. 2. 17.
메모리 컴퓨터에서 메모리는 CPU에게 있어 책상과 같은 역할이다. 우리가 공부를 할 때 책상에 필요한 것을 늘어놓는 것처럼 CPU도 그러하다. 우리가 손에 닿는 거리 만큼이 주소 공간이 된다. 팔이 길면 길수록 멀리 떨어질 건 잡을 수 있는 것처럼 더 많은 정보에 접근할 수 있다. CPU는 메모리와 데이터를 주고 받을 때 버스라는 시스템을 이용한다. 이것은 도로와 같은 개념이다. 도로가 넓을 수록 교통량을 많이 수용할 수 있는 것처럼 버스의 대역폭이 클 수록 더 많은 데이터를 한꺼번에 읽을 수 있다. alignas에서 본 것처럼 정렬된 데이터는 - 즉 버스에 폭맞춤되면 전송 속도는 더 빨라진다. 추가의 패딩 바이트가 필요없기 때문이다. 운영체제는 어플리케이션를 실행할 때 로더를 이용해서 파일시스템에 있는 데이터.. 2021. 2. 15.
alignas 컴퓨터는 버스라는 전송 장치가 있다. 이는 물리 메모리에서 다른 장치(CPU, 다른 메모리 등)로 데이터를 전송하는데 쓰이는 선로이다. 도로와 비견되며 버스의 대역폭-한꺼번에 전송 가능한 크기-이 클수록 정보를 더 빠르게 전달할 수 있다. 그렇다면 대역폭보다 전송할 데이터의 크기가 작다면 어떻게 될까? 유감스럽게도 그렇더라도 그대로 전송한다. 이렇게 대역폭에서 쓰지 않는 만큼을 패딩이라고 한다. 대역폭과 자료형을 맞추면 추가적인 처리가 필요없어 더 빠르게 전송할 수 있다. C11부터 포함된 alignas는 구조체가 효율적인 크기를 갖도록 컴파일러 차원에서 강제해준다. // C11 struct alignas(16) float4 { float r; float g; float b; float a; }; // .. 2021. 2. 3.
make_index_sequence 구현 tuple 출력에 이어 또 다시 과제를 풀어보았다. 이번에는 std::make_index_sequence를 구현해보는 것이었다. 이걸 처음 썼을 때는 왜 std::make_index_sequence로 만든 인스턴스를 넘겨줘야 하는지 이해하지 못했다. 왜냐하면 템플릿 인자로도 충분하다고 생각했기 때문이다. 그러나 구현해보니 이해가 되었다. 템플릿 함수의 템플릿 인자여도 가능할 것이다. 템플릿 인자로 넘겨줄 경우 안에 들어있는 파라미터 팩을 꺼내려면 조금 까다로운 코딩이 필요할 것이다. 즉 make_index_sequence의 로직이 반복될 것이다. 별도로 분리한 결과 [0 ... n] 인자를 넘기는 방식에 대해 더 간단하고 쉬운 해결책을 표준은 제시했다. 이제 다시 강의를 들어야겠다. template st.. 2021. 1. 27.
tuple 출력 #include #include template std::ostream& print_tuple_element( std::ostream& os, TUPLE& t, char const* sep ) { if constexpr (INDEX > 1) { print_tuple_element( os, t, sep ); } if constexpr (INDEX == 1) { sep = ""; } return os 2021. 1. 22.
std::remove_if 조건에 일치하는 반복자를 일치하는 않은 반복자 위치에 덮어씀. 따라서 조건을 만족한 컬렉션을 확인하면 중복된 데이터가 존재함 template ForwardIt remove_if(ForwardIt first, ForwardIt last, UnaryPredicate p) { first = std::find_if(first, last, p); if (first != last) for(ForwardIt i = first; ++i != last; ) if (!p(*i)) // first 위치에 부합되지 않는 정보가 덮어씌워짐 *first++ = std::move(*i); return first; } 결과 값으로 검사를 끝낸 마지막 반복자가 나옴 따라서 반드시 정리가 필요 auto iter = std::remove.. 2021. 1. 21.
instance in underlying array class copy_unable { public: copy_unable() {} copy_unable(copy_unable&) = delete; }; int main() { copy_unable c, d; // C2280: 'copy_unable::copy_unable(copy_unable &)': 삭제된 함수를 참조하려고 합니다. // std::initialize_list auto cc = { c, d }; return 0; } c++에서 여러 인스턴스들에게 반복된 로직을 실행시키기 위해 for 문을 사용할 수 있다. 이 때 반복시키기 위해 initialize_list나 array 등 기본 배열에 담는 경우에 복사가 생긴다. 이는 분명한 오버헤드이므로 회피해야 한다. 다만 언급한 사례처럼 불가피하게 중.. 2021. 1. 21.
forward declaration of unique_ptr<T> // A.h class A { A(); std::unique_ptr _b; } // A.cpp A::A() : _b{ std::make_unique() } {} 포인터나 참조를 헤더에 정의한 경우 전방 선언은 필수로 요구된다. 컴파일보다 링킹이 빠르기 때문이다. 허나 이것을 컴파일하면 C2027 오류를 받게 된다. 오류를 살펴보면 unique_ptr의 소멸자에서 T를 실체화하려고 시도하다가 났다는 것을 알 수 있다. 소멸자를 선언하면 오류가 나지 않는다. 이때 인라인이어서는 안된다. 그러나 왜 이럴까? 이는 사용자 정의 소멸자가 없으면 컴파일러가 암시적으로 삽입하기 때문이다. 이걸 인라인으로 처리한다. 이는 헤더에 삽입된다는 의미가 된다. 헤더에는 전방 선언 뿐이므로 해당 오류가 발생한다. 따라서 소멸자.. 2021. 1. 21.
최신 STL 배우는 방법 Q: 최신 STL 기능을 배우는 가장 좋은 방법은 뭘까요? 온라인 쿡북이 있나요? 함수형 스타일? 팀에 책을 쓰는 전문가가 있나요? A: 구현해보는 게 최고의 방법입니다. STL 유지보수하는 사람 중 아무도 책을 쓸 시간이 없습니다. 하지만 우린 마이크로소프트 Docs 팀에서 온 타일러 화이트니와 지난 몇년간 구현했던 여러가지 것들을 문서로 정리하고 있습니다. cppreference.com은 커뮤니티에서 모인 정보를 보기 좋은 곳이죠. 제 생각에 기능을 배우는 좋은 방법은, 구현도 아니고 장난감같이 갖고 놀면서, 아주 단순한 환경에서 기초에 익숙해지고, 실제 환경에서 간단히 사용해보면서, 점차 고급 영역으로 나아가는 겁니다. 실제 개발 환경에서 새 기능을 바로 써보려하는 건 두통거리가 될 건데요, 기능을.. 2020. 12. 15.
C++ 명언 너를 미워하고 싶지 않거든 소멸자에 특별한 코드를 넣지 마시오 devblogs.microsoft.com/oldnewthing/20201112-00/?p=104444devblogs.microsoft.com/oldnewthing/20201112-00/?p=104444#comment-137422 2020. 12. 15.
테트리스 테트리스를 세번째 만드는 것 같다. 첫번째는 콘솔로, 두번째는 임베디드로 했다. 이번에는 유니티로 만들었다. 유니티 학습 사이트에서 초급 강좌를 따라한 후 기념삼아 해봤다. 만드는데 2주쯤 걸린 것 같다. 완성해서 기쁘다. 가끔 블록이 파묻히는데 그냥 놔두었다. 지금은 중급 강좌를 진행하고 있다. 이게 끝나면 또 다시 시도해볼 생각이다. 소스: https://github.com/ehei1/Tetris 다운로드: http://ehei.itch.io/tetris 잘한 점 꾸준히 해서 완성시킴 나름 플레이 루프를 완성 아쉬운 점 즉흥적으로 만들어서 모델링이 좋지 못함 변수가 의존적임. 잘못 설정하면 로직이 망가짐 2020. 4. 13.
django 과제 전환 배치 기간 동안 이것저것 공부를 해보았다. 한가지만 팔 것 그랬나 생각도 들지만... 암튼 그 중에 웹 백엔드 프로그래밍을 시도해봤다. 장고는 파이썬 기반이기에 무척 익숙하다. 물론 백엔드는 낯설지만. 그런데 너무 늦게 이걸 보았고, 지원한 다른 곳에서도 nodejs 기반의 코드 과제를 주었다. 게다가 아이는 입원... 다행히 부인님이 도와줘서 밤 늦게 집에 온 뒤 새벽까지 짰다. 다음 날 오전 중에 수정해서 제출했다. 역시 이런 쪽의 학습 없이 도전해서 그런지 탈락했다. 면접 제의는 없었으니까. 점수가 무척 낮은데 상위라서 조금 놀랐다. 아마 지원하고 완성하지 않은 이가 많았으리라 짐작한다. 조금 더 열심히 해봤으면 어땠을까. 뭐 이미 지난 일이고... 일단 너무 늦게 과제를 보았다. 무엇보다 내.. 2020. 2. 22.
Valid Parentheses https://leetcode.com/problems/valid-parentheses/ 괄호가 잘 닫혔는지 검사하는 문제 class Solution: def isValid(self, s: str) -> bool: stack = [] pairs = { ')' : '(', ']' : '[', '}' : '{', } for ch in s: if ch in ( '(', '[', '{' ): stack.insert( 0, ch ) else: if not stack: return False else: openBracket = stack.pop( 0 ) if pairs[ ch ] != openBracket: return False return not stack 2020. 2. 12.
Min Stack https://leetcode.com/problems/min-stack/ 스택을 구현하는 문제. 쉽다. class MinStack: def __init__(self): """ initialize your data structure here. """ self.__min = float( 'inf' ) self.__stack = [] def push(self, x: int) -> None: self.__min = min( self.__min, x ) self.__stack.insert( 0, x ) def pop(self) -> None: stack = self.__stack value = stack[ 0 ] self.__stack = stack[ 1 : ] if value == self.__min: self.. 2020. 2. 12.
Target Sum https://leetcode.com/problems/target-sum/ 주어진 값 S가 되도록 제시된 정수 집합으로 조합을 찾는 문제. 부호가 +,-가 될 수 있다. 어차피 모든 조합을 검사해야 하므로, 동적 프로그래밍 기법을 써서 반복 계산을 피해야 한다. import collections class Solution: def findTargetSumWays( self, nums, S: int ) -> int: if not nums: return 0 # key: remain nums, value: sum cases caches = collections.defaultdict( lambda : collections.defaultdict( int ) ) count, _ = self.__findTargetS.. 2019. 12. 4.
Clone Graph https://leetcode.com/problems/clone-graph/ 그래프를 복사하는 문제. 결국은 모든 노드를 방문하므로, 이미 가본 곳만 가지 않도록 주의한다. """ # Definition for a Node. class Node: def __init__(self, val, neighbors): self.val = val self.neighbors = neighbors """ class Solution: def cloneGraph(self, node: 'Node') -> 'Node': visited = {} return self.__cloneGraph( node, visited ) def __cloneGraph( self, node, visited ): if node.val in visit.. 2019. 11. 26.
Perfect Squares 어떤 정수가 주어졌을 때, 제곱이 되는 수로 어떤 합이 결정되는지 구하는 문제 https://leetcode.com/problems/perfect-squares/ import math class Solution: def numSquares(self, n: int) -> int: currentValues = { n } count = 0 while currentValues: nextValues = set() for currentValue in currentValues: for i in range( 1, int( math.sqrt( currentValue ) ) + 1 ): remainValue = currentValue - i * i if not remainValue: return count + 1 elif.. 2019. 11. 25.
Open the Lock 숫자 네 개가 달린 자물쇠를 특정 숫자로 만드는 문제. 각 숫자는 한번에 한 칸만 옮겨진다. 난점은 막다른 골목(deadend)의 존재. 깊이 우선 탐색으로 해결하면 된다. https://leetcode.com/problems/open-the-lock/ class Solution: def openLock( self, deadends, target: str ) -> int: deadends = set( deadends ) currentNumbers = { '0000' } count = 0 visitedNumbers = set() while currentNumbers: visitingNumbers = set() for currentNumber in currentNumbers - deadends: if tar.. 2019. 11. 4.

티스토리툴바