반응형 컴퓨터 사이언스65 [c++] 백준 #14257 XOR 방정식 (190927) A+B = S, A^B = X를 만들 수 있는 (A, B) 쌍의 개수를 구하는 문제이다. 문제를 풀 때 집중해야 하는 것은 xor의 성질. xor 했을1이 되는 bit는 A나 B 둘 중 하나가 가지고 있을 것이다. 일단은 xor해서 0되는 bit는 A, B 둘 다 가지고 있지 않다고 가정하고 나머지 bit를 0으로 두자. 그러면 A^B = X가 되는 A, B의 경우의 수는 2^(켜진 비트 수) 만큼 된다. 이때 xor해서 0이 되는 경우는 모두 0으로 뒀으니 A, B는 모두 X의 각 비트를 나눠 가진 셈이니까 A + B = X이다. 그러면 이제 두 숫자 모두 켜져 있지 않은 비트를 하나씩 켜보면서 A + B = S를 만들 수 있으면(이 경우는 유일하게 하나 나온다) 가능한 모든 경우는 2^(.. 2019. 10. 8. [c++] 백준 #14458 소가 길을 건너 간 이유 10 교차점을 세는 방식이 생각하기 어려운 문제였다. 회전 시 생기는 교차의 수를 매번 새로 세줘야 하는데 naive 하게 구현하면 당연히 O(N^3)이라 시간 초과. 한 번 회전할 때마다 나름의 규칙성을 찾아보면, 회전 시 교차점의 수는 이전 교차의 수 – 현재 간선으로 생긴 교차의 수 + 새로 생기는 교차의 수가 된다. 이전 교차의 수는 회전할 노드보다 right가 더 큰 노드의 개수 (코드에서 N-right_idx[left_rev[i]) 새로 생기는 교차의 수는 회전할 노드보다 right가 작은 노드의 개수. (코드에서 right_idx[left_rev[i]) 이렇게 대략적으로 회전 시 교차선 수 개수 변화를 구할 수가 있는데, 관건은 맨 처음 상태에서 교차점 개수를 계산하는 것이다. 여기에.. 2019. 10. 8. [딥러닝 뉴비의 좌충우돌 일기] 개발환경 셋팅하기(introduction) 지난 번 글 이후로 한달의 시간이 지나갔다. 그동안 인턴 마무리하고 대학원 입시가 몰아쳐서 사실 딥러닝 공부를 거의 못했다. 막학기의 여유로 차근차근 딥러닝 공부를 다시 해보자. 오늘의 주제는 개발환경 셋팅하기이다. 그럼 시작해보자. 딥러닝에서는 왜 개발환경 셋팅하는 게 중요할까? 사실 C++로 PS 할 때는 개발환경 자체에 대해 별로 신경을 쓰지 않는다. 컴퓨터 포맷하고, VS Code 깔고 GNU 컴파일러 깔면 g++ boj_####.cpp ./a 이렇게만 해도 바로바로 프로그램 실행 결과가 나오기 때문이다. 핵편함. 반면 Python으로 딥러닝 코드를 짤 때는 수많은 모듈을 import한다. 다양한 모듈(패키지)을 설치하고 그 기능을 내 코드에서 적재적소에 사용할 수 있다는 게 Python의 장점이.. 2019. 9. 4. 190822 알고리즘 스터디 숙제 190822_백준 숙제 공부 BOJ #10775 (1-C) Disjoint set을 이용한 문제. 지난번에 세그먼트 트리로 푼 문제임. 자기 부모가 0(존재하지 않는 게이트, 1번까지 다 돌아도 더 이상 넣을 수가 없음)이 아니면, 게이트를 도킹하면 된다. 맨 처음에 자기 부모는 자기 자신을 해두고, 자기 부모가 0이 아니면 자기 부모랑 자기부모-1(아마 빈칸이겠지)을 union해서 그 앞에 빈칸이 아니면 자기부모-1의 부모를 또 찾으러 가니까 어쨌든 가장 마지막에 비어있는 1~N 사이의 칸을 찾아 주는 것. ==> 결국 부모-1과 union하는 이유는 결국 항상 부모 = 빈칸이 되도록 하기 위해서 뭔가 좀 생각하기 복잡하지만 코드는 그냥 disjoint set 쓰면 됨 스터디 오늘의 목표 1) H - .. 2019. 8. 22. 이전 1 ··· 10 11 12 13 14 15 16 17 다음 반응형