티스토리

mangu
검색하기

블로그 홈

mangu

mangu.tistory.com/m

잘못된 정보가 있다면 댓글 달아주세요.

구독자
5
방명록 방문하기
공지 👨🏻‍💻Who am I? 모두보기

주요 글 목록

  • 2022 ICPC 서울 리저널 인터넷예선 6솔로 본선 간당 교내 3등, 전체 38등 A번 파일 잘못 제출해서 패널티 두 번 먹었다.. 공감수 0 댓글수 0 2022. 10. 24.
  • [vscode] tensorflow.keras 자동완성 안됨 pycharm에선 되는데 vscode에서는 tensorflow.keras내의 메소드들이 자동완성이 안된다. 자동완성이 안 되는 환경에서 개발은 정말 열받는다. 정말 너무 짜증 나서 이것저것 깔아보고 지워보고 찾아보고 하면서 겨우 방법을 알아내서 정리한다. https://stackoverflow.com/questions/68860879/vscode-keras-intellisensesuggestion-not-working-properly Vscode keras intellisense(suggestion) not working properly Intellisense works fine on importing phrase But when it comes with chaining method, it shows d.. 공감수 2 댓글수 2 2022. 9. 11.
  • 풀스택 웹사이트 개발기 (feat. FastAPI, Vue.js, TensorFlow, Docker) Intro https://whatisbreed.com/ What is breed? whatisbreed.com 견종 분류 모델 개발기에서 개발한 모델이 아깝기도 하고, 그동안 풀스택을 해보고 싶던 생각도 있어서 분류 모델 + LIME을 적용한 웹사이트를 개발했다. 2022.08.20부터 개발을 시작했고 글을 쓰는 현재(2022.09.03) 배포를 한 상태이며 꾸준히 업데이트를 할 예정이다. 기술 스택 개강을 하기 전까지 개발을 해서 배포하고 싶은 마음이 있어, 기술 스택들을 선택할 때 배우는 비용이 낮은 것에 중점을 뒀다. 그리고 이전에 유튜브에서만 보던 해보고 싶은 신기술들을 사용해보고 싶은 마음도 컸다. Frontend - Vue.js 카카오가 리액트 냅두고 왜 Vue 쓰는지 알려드림 - 코딩애플 온.. 공감수 3 댓글수 0 2022. 9. 3.
  • [C++20] auto로 template를 대체해보자 C++20부터 함수 파라미터로 auto를 허용한다. C++20부터는 template를 이용하여 구현해야 했던걸 auto를 이용해 구현할 수 있다. 코드를 통해 살펴보자 template T1 f(T2 a, T3 b) { return a + b; } int main() { cout 공감수 0 댓글수 0 2022. 7. 14.
  • [C/C++] 잡기술 이곳저곳에서 남의 코드 구경하다 발견한 잡기술들이다. C/C++가 아닌 다른 언어들에서도 응용할 수 있는 것들이 많이 있다. 이런 잡기술들이 가독성을 안 좋게 만드는 것도 있지만 더 좋을 때도 있다고 생각한다. 상황에 따라 잘 사용하면 될 것 같다. 잡기술들을 발견하면 하나씩 추가할 예정이다. (최종 수정 2022/07/07) char을 if문으로 여러 개 걸어야 할 때 if (c == 'A' || c == 'B' || c == 'C' || c == 'D') 위와 같은 코드를 아래와 같이 줄일 수 있다 if (strchr("ABCD", c)) 나눗셈 올림 std::ceil(x / n) 위의 함수는 리턴 값이 실수이다. 1. x / n + !!(x % n) 2. (x + n - 1) / n 위의 두 방법으.. 공감수 2 댓글수 0 2022. 7. 7.
  • [백준] 23245 Similarity 문제 링크 http://icpc.me/23245 23245번: Similarity In modern application systems, a recommendation system is very widely used to recommend books, music, ads, items, etc. The recommendation system needs to attract other users by providing the most interested items to each user. One way of recommendation is www.acmicpc.net 문제 출처는 2021 icpc 온라인 예선이다. 풀이 (pi < pj < pk)&& (qi < qj < qk) 인 (i, j, k)를 구하면 되.. 공감수 0 댓글수 0 2022. 7. 5.
  • 2022 모비스 대회 후기 학생부 1233명 중 123등을 했다. 거의 정확히 상위 10%다. 50등까지 본선인데 정말 아쉽다. 채점을 해주지 않는 대회에 익숙하지 않다. 코드에 실수가 많은 편이라 이런 대회나 코테에서 성적이 많이 떨어지는 거 같다. 4번이 제일 쉬운 문제라고 생각됐는데 그걸 틀려서 점수가 많이 깎였다. 쉬운 문제 안틀리게 빠르게 푸는 연습을 해야겠다. 근데 이걸 어떻게 연습하지... 마지막 문제가 가장 어려운 문제였는데, 최소컷 문제라는 것까지 파악하고 O(N^2E) 짜리 dinic을 써야 하는 걸 알았지만 dinic을 아직 공부하지 않아서 에드몬드 카프 알고리즘으로 O(NE^2)짜리 코드로 부분점수만 긁었다. 나중에 알고 보니 풀이도 약간 틀린 풀이였다. 그래프 모델링을 약간 다르게 했다. 아무튼 부분점수는 .. 공감수 0 댓글수 0 2022. 7. 5.
  • 2022 중간 점검 벌써 6월이다. 2021년 회고를 다시 읽어보니 생각보다 이룬 것이 많아 중간 점검을 써야겠다. 목표는 3가지였다. 하나하나 뭘 했는지 적어보며 중간점검을 해야겠다. AI 분야 경험 웹 백엔드 경험 솔브닥 다이아 & 코포 블루 AI 분야 경험 & 깊이 있는 공부 이번 연도 초에 학교에서 하는 머신러닝 특강을 들었다. 5일 동안 하는 40시간짜리 특강이었다. 이때 머신러닝이 뭔지 큰 그림만 잡고 넘어갔다. 비전공자들도 들을 수 있는 수업이어서 깊이 있게 다루진 않았다. 전공으로 지능형 시스템 수강을 하며 머신러닝에 대해 조금 더 깊게 공부를 했고, 배운 것을 기반으로 데이콘 콘테스트에 하나 제출해봤는데 600명 정도 참여한 콘테스트에 최종 165등을 했다. 아예 처음 한 것 치고는 잘한 것 같아 만족한다... 공감수 1 댓글수 1 2022. 6. 25.
  • [백준] 2679 맨체스터의 도로 문제 링크 http://icpc.me/2679 2679번: 맨체스터의 도로 맨체스터에 있는 도로는 모두 일방 통행이다. 또한 이 도로는 모두 1시간에 지나갈 수 있는 차의 개수 제한이 있다. 길(경로)에도 차의 개수 제한이 있는데, 이것은 이 길에 있는 도로의 제한 중 www.acmicpc.net 풀이 네트워크 플로우를 기반으로 하고, 우선순위 큐를 이용한 풀이와 이분 탐색을 이용한 풀이가 있다. 차의 개수는 네트워크 플로우를 이용하면 쉽게 구할 수 있지만, 길 1개를 이용할 때의 최대 개수는 구하기 어렵다. 일반적인 네트워크 플로우처럼 경로를 고른다면, 경로를 고르는 순서에 따라 어떤 길에 한 번에 보낼 수 있는 최대를 보내지 않을 수 있다. 그렇기 때문에 다른 처리를 해줘야 한다. 우선순위 큐 풀이 .. 공감수 0 댓글수 0 2022. 6. 5.
  • [백준] 8916 이진 검색 트리 문제 링크 http://icpc.me/8916 8916번: 이진 검색 트리 각 테스트 케이스에 대해서, 입력으로 주어진 순열과 같은 트리를 만드는 순열의 개수를 9,999,991로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 3 2 5 4 1 6라는 예제가 있을 때 가장 앞에 나오는 3은 루트 노드로 순서가 바뀔 수 없다는 사실은 조금만 생각해본다면 알 수 있다. 그럼 2 5 4 1 6를 3의 왼쪽 트리와 3의 오른쪽 트리로 나눌 수 있다. 3보다 작은 2 1은 왼쪽 트리가 3보다 큰 5 4 6은 오른쪽 트리가 될 것이다. 그렇다면 재귀적으로 2 1과 5 4 6은 각각 트리가 되고, 첫 번째 수는 루트가 될 것이다. 여기서 조금 더 관찰해 본다면, 같은 모양의 트리가 나오기 위해서는 작은 .. 공감수 0 댓글수 0 2022. 5. 19.
  • [Python3] GIL (Global Interpreter Lock) GIL 이란? Global Interpreter Lock의 약자로 전역 인터프리터 락이다. 여러 개의 쓰레드가 파이썬 코드를 동시에 실행하지 못하도록 하는 것이다. 한 프로세스 내에서, Python 인터프리터는 한 시점에 하나의 쓰레드에 의해서만 실행될 수 있다. 멀티 쓰레딩이 불가능하다는 것이 아니다. 원래 멀티 코어라면 멀티 쓰레딩 시에 여러 개의 쓰레드가 여러 코어 상에서 병렬(Parallel) 실행될 수 있는데, Python에서는 그러한 병렬 실행이 불가능하다. GIL이 있는 이유 파이썬에서 모든 것은 객체이고 이것들은 Reference Count가 관리가 된다. Reference Count가 0이 되면 Garbage collector가 객체를 메모리 해제시킨다. 그러나 여러개의 쓰레드가 동시에 .. 공감수 0 댓글수 0 2022. 5. 15.
  • [C/C++] Sequencing (Sequence Point) Sequencing / Sequence Point란? c++11부터 Sequence Point가 Sequencing으로 말이 바뀌었다고 한다. 이 글에선 sequence point란 말을 쓰겠다. 모든 연산의 결과가 완료되는 시점 쉽게 말하면, 한 시퀀스 포인트에서 다음 시퀀스 포인트로 가기 전에 이전의 모든 연산이 완료된다는 의미다. Sequence Point 1. ; (세미콜론) 2. ||, &&, ? : 와 같은 논리 연산 예를 들어, a || b에서 b가 되기 전에 a의 연산이 모두 완료된다. (a) ? (b) : 는 ?가 sequence point로 무조건 a가 먼저 완료된다. 3. , (쉼표) a = f1(), b = f2()와 같이 , 로 연결된 표현 4. 함수의 리턴 함수가 return.. 공감수 0 댓글수 0 2022. 5. 1.
  • [Python3] local, global 변수 규칙 아래 두 코드 중 하나는 에러가 발생한다. 정답을 보지 말고 생각을 해보자! 1번 코드 x = 1 def f(): y = x return y print(f()) 2번 코드 x = 1 def f(): y = x x = 2 return y print(f()) 정답은 2번 코드가 에러가 발생한다. 거의 동일한 코든데 왜 하나는 에러가 발생하고 하나는 정상 동작할까? 그 이유는 파이썬의 local, global 변수 규칙에서 찾을 수 있다. 파이썬에서는 함수 전체를 보고 global 변수인지 local 변수인지 결정을 한다. 함수 전체에서 reference만 일어난다면 이는 암묵적으로 global이라 판단한다. 그러나 assign이 한 번이라도 일어난다면 이는 local 변수로 판단을 한다. 위의 1번 코드에선.. 공감수 0 댓글수 0 2022. 5. 1.
  • 못생긴 vscode 터미널 색을 바꿔보자 테마가 다 마음에 드는데 터미널 색만 맘에 안들 때 이 방법을 써보자. 1. vscode setting창 연다 2. 중간쯤에 보이는 Color Customizations 누른다 3. 여기서 맘에 드는 폰트 컬러 복사 4. 복붙 에디터 부분 색이랑 맞추고 싶으면 background 부분만 지우면 폰트 색깔만 바뀐다. 공감수 3 댓글수 0 2022. 5. 1.
  • [C/C++] printf에 float만을 위한 변환 명세가 없는 이유 printf("%f", 1.0f)와 같이 printf에 float형을 넘겨줘도 절대 printf 함수에 float형을 넘겨줄 수 없다는 재밌는 사실을 알게 됐다. double lf = 1.0; printf("%lf\n", lf); // double lf 사용 printf("%f\n", lf); // double에 f도 가능 위와 같이 double을 출력할 땐 %lf와 %f 둘 다 사용할 수 있는데 이건 C99에 생긴 기능으로 scanf에서 double형을 %lf로 받기 때문에 편의성?을 위해 생긴 기능이라고 한다. 종종 float은 %f, double은 %lf로 출력해야 한다는 사람들이 있는데 이건 완전한 오개념이다. 아래 사진을 봐도 f는 명확히 double을 위한 변환 명세다. 그런데 float형을 .. 공감수 0 댓글수 0 2022. 4. 28.
  • [백준] 3878 점 분리 문제 링크 http://icpc.me/3878 3878번: 점 분리 평면 위에 여러 개의 검정 점과 흰 점이 있다. 이때, 길이가 무한대인 직선을 그어 흰 점과 검은 점을 분리하려고 한다. 직선은 어떤 점과도 만나면 안 된다. 직선으로 인해서 나누어지는 두 그룹 www.acmicpc.net 풀이 두 컨벡스 헐이 서로 만나지 않게 하면 된다. 검정 컨벡스헐을 구성하는 점을 A, 흰색 컨벡스 헐을 B라 하자. 두 컨벡스 헐이 만나지 않기 위해선 A의 점들 중 어떤 점도 B 내부에 있으면 안 된다. 또한 B의 점들도 A에 있으면 안 된다. 또한 두 컨벡스 헐을 이루는 모든 직선들끼리 서로 만나면 안 된다. 코드 #include using namespace std; using ll = long long; #de.. 공감수 0 댓글수 0 2022. 4. 27.
  • 원티드 쇼미더코드 후기 대회라고 했지만 코테 느낌이었고, 가볍게 풀었는데 금뱃지 받았다. 문제 설명은 저작권이 어떻게 걸린지 몰라서 하지 않겠다. 공감수 0 댓글수 0 2022. 4. 15.
  • Docker로 M1맥에서 Ubuntu 돌리기 M1에서 Ubuntu 돌리려면 무조건 서버 or 패럴럴즈만 알고 있었는데 최근에 Ubuntu를 사용해야 해서 알아보던 중 도커라는 걸 알게 됐다. 도커 컨테이너는 격리된 공간에서 프로세스가 동작하는 기술이다. 도커에는 우분투뿐만 아니라 다양한 종류의 컨테이너를 올릴 수 있다. 또한 M1 맥이 아니라 다른 운영체제에서도 아래와 같은 방법으로 사용할 수 있는 것으로 알고 있다. 자세한 도커에 대한 지식은 여기를 참고하자.​ 우선 아래 링크에서 Docker desktop을 설치한다. https://www.docker.com/products/docker-desktop/ Docker Desktop - Docker DockerCon 2022 Don’t miss it – register now for May 10th.. 공감수 1 댓글수 0 2022. 4. 15.
  • [백준] 1377 버블 소트 문제 링크 http://icpc.me/1377 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 풀이 개인적으로 알고 나면 쉽지만 아이디어가 많이 어려운 문제인 것 같다. 문제를 잘 관찰을 해본다면 출력을 하는 수는 정렬이 끝난 다음 시점의 i값이다. 편의상 인덱스가 작은 방향을 왼쪽, 큰 방향을 오른쪽이라 하겠다. 정렬이 모두 끝난 시점을 알기 위해서는 왼쪽으로 밀려난 수 중 가장 많이 밀려난 수가 몇 번 왼쪽으로 밀려났는지를 알면 된다. 그 이유는 왼쪽으로 가야 하는 어떤 수는 한번 .. 공감수 0 댓글수 0 2022. 4. 12.
  • 2022 구글 코드잼 Qualification Round 후기 4솔을 하고 71점을 먹었다. A번만 풀고 과제하다가 자고 일어나면 시간이 끝날 거 같아서 3시까지 풀다 잤다.. 피곤해 죽을 뻔.. 30점만 먹고 자려했는데 4번 풀이가 보여서 이것만 풀고 자야지하다가 맞왜틀 박으면서 늦게까지 풀었다. 마지막 문제는 쓰윽 보고 문제가 이상하길래 그냥 안 풀고 맘 편히 잤다. A. Punched Cards 이쁘게 출력만 하면 되는 간단한 구현문제다. #include using namespace std; char arr[100][100]; void f1(int r, int c) { char cc[2] = {'+', '-'}; for (int i = 0; i < 2 * c + 1; i++) arr[r][i] = cc[i % 2]; } void f2(int r, int c) .. 공감수 0 댓글수 0 2022. 4. 3.
  • [백준] 2449 전구 문제 링크 http://icpc.me/2449 2449번: 전구 입력의 첫 번째 줄에는 전구의 수를 나타내는 양의 정수 N과 전구가 표현할 수 있는 색의 수 K가 주어진다. 단, N은 1이상 200이하의 정수이며, K는 1이상 20이하의 정수이다. 두 번째 줄에는 N개 전 www.acmicpc.net 풀이 오랜만에 되게 재밌게 푼 dp문제다. 3차원 dp로 풀었는데 다른 사람 코드 구경하면서 2차원 dp로 내 풀이보다 훨씬 쉽게 풀 수 있는 걸 발견했다. 이 글에선 3차원 풀이를 작성하겠다. 시간 복잡도는 O(N^3 * K)에 해결할 수 있다. dp[l][r][i] : 구간 [l, r]을 i로 만들었을 때 최소 경우의 수 a[i] : a번째 전구의 색 위와 같이 정의를 하면 세 가지 케이스로 점화식을 세.. 공감수 0 댓글수 0 2022. 4. 1.
  • [백준] 7620 편집 거리 문제 링크 http://icpc.me/7620 7620번: 편집 거리 가장 짧은 편집 스크립트를 출력한다. 한 명령을 한 줄에 하나씩 출력하며, 문제의 괄호에 나와있는 (a, d, m, c)중 하나를 출력하고, 그 명령을 수행하는데 사용한 글자를 출력한다. (출력할 글자 www.acmicpc.net 풀이 dp 역추적을 하는 문제다. 하지만 메모리를 특이하게 관리해야 하는 처음 보는 문제다. 역추적을 하기 위해서 dp테이블을 모두 가지고 있기엔 테이블의 크기가 17000 * 17000 * 4byte로 너무 크다. 그렇기 때문에 역추적을 위한 테이블을 17000 * 17000 * 2bit로 만들어 메모리를 최적화시켜야 한다. 역추적 테이블은 unsigned char 한 칸에 비트 연산을 이용하여 정보를 4개.. 공감수 0 댓글수 0 2022. 3. 24.
  • 구글 푸바 챌린지 후기 ​구글엔 되게 재밌는 이스터 에그인 푸바 챌린지라는 게 있다. 구글에서 다양한 개발자를 채용하기 위해 만들어놨다고 한다. 개발자스러운 검색을 하다 보면 뜬다고 하는데 이런 게 나한테 떠버렸다. 어쩌다 알고리즘에 걸려버렸나 보다. 마지막으로 검색한 게 "python list comprehension"이었던 걸로 기억한다. 이게 뭔지 몰라서 뜨는 창은 캡처를 못했지만 개발자라면 흥미롭게 생각할만한 문구로 확인 버튼을 누르라고 꼬신다ㅋㅎ 버튼을 누르면 아래 같은 창이 뜬다. 여기서 이것저것 누르다 보면 help를 쳐보라는 말이 나오고 문제를 풀 수 있게 해 준다. 문제는 파이썬과 자바로만 풀 수 있다. 레벨별로 문제가 있는데 점점 레벨별로 난이도 차가 꽤 크다. 문제당 시간을 부족하지 않게 줘서 시간제한 상관.. 공감수 1 댓글수 0 2022. 3. 16.
  • [백준] 1368 물대기 문제 링크 http://icpc.me/1368 1368번: 물대기 첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다. 다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어 www.acmicpc.net 풀이 MST를 이용하여 풀 수 있다. 가상의 루트 노드를 하나 만들고, 어떤 물을 킬 때, 루트 노드에서 물을 끌어온다고 생각하면 쉽게 풀 수 있다. 물은 키는 행위는 루트 노드와 킬 노드를 연결시키는 것으로 매핑시키면 된다. 코드 #include using namespace std; struct T { int x, y, z; }; vector arr; int mat[302][302];.. 공감수 0 댓글수 0 2022. 3. 16.
  • [백준] 1126 같은 탑 문제 링크 http://icpc.me/1126 1126번: 같은 탑 첫째 줄에 조각의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에 각 조각의 높이가 주어진다. 높이는 500,000보다 작거나 같은 자연수이고, 모든 조각의 높이의 합은 500,000을 넘 www.acmicpc.net 풀이 dp문제다. dp인 것을 못 알아차리고 고민하다가 알고리즘 분류를 봤다. 처음 생각했던 점화식은 dp[i][a_size][b_size] : i번째 까지 봤을 때 a기둥의 사이즈와 b기둥의 사이즈로 dp를 정의하는 것이었다. 그러나 이 풀이는 52 * 5e5 * 5e5로 시간초과가 발생할 것이다. 그래서 a기둥과 b기둥의 높이를 더 컴팩트하게 정의할 수 있는 방법을 생각했다. 결론은 더 큰 기둥의.. 공감수 0 댓글수 0 2022. 2. 26.
  • [백준] 2662 기업투자 문제 링크 http://icpc.me/2662 2662번: 기업투자 어떤 투자가가 여러 기업들에게 돈을 투자해서 최대의 이익을 얻고자 한다. 단, 투자는 만원 단위로 할 수 있으며 각 기업은 많이 투자할수록 많은 이익을 투자가에게 돌려준다. 돈을 투자하지 www.acmicpc.net 풀이 배낭 문제라고도 불리는 웰노운인 knapsack문제다. dp를 이용하여 풀 수 있다. dp[i][j] = max(dp[i - 1][j - k] + arr[k][i]) (0 공감수 0 댓글수 0 2022. 2. 23.
  • [백준] 2481 해밍 경로 문제 링크 http://icpc.me/2481 2481번: 해밍 경로 길이가 같은 두 개의 이진수 코드 w1과 w2가 있다고 하자. 이 두 코드 사이의 해밍 거리(Hamming distance)는 w1과 w2의 각 비트를 왼쪽부터 오른쪽으로 차례대로 비교할 때 서로 다른 값을 가진 비트의 www.acmicpc.net 풀이 해밍 거리가 1인 경우는 비트 하나만 다른 것을 의미하기 때문에 비트가 하나만 다른 것들을 모두 그래프로 만든 후에 bfs를 돌리면 된다. 비트 하나만 바꿀 때는 XOR연산을 하면 된다. 그래프를 만들 때는 N개의 수에 k번 비트 연산을 하고 그 수가 존재하는지 map으로 확인하면 O(NKlogN)에 만들 수 있다. cf) 입력을 int형으로 받아서 2시간 가까이 뇌절을 했다. 30자리.. 공감수 0 댓글수 0 2022. 2. 17.
  • [백준] 1533 길의 개수 문제 링크 http://icpc.me/1533 1533번: 길의 개수 첫째 줄에 교차점의 개수 N이 주어진다. N은 10보다 작거나 같고, 시작점의 위치 S와 끝점의 위치 E, 그리고 정문이가 늦는 시간 T도 주어진다. S와 E는 N보다 작거나 같은 자연수이다. T는 1,000,000,000 www.acmicpc.net 풀이 본대 산책 2과 비슷한데 가중치가 있는 문제다. 가중치가 5 이하이기 때문에 정점을 늘려서 풀 수 있다. 정정 하나를 v0 v1 v2 v3 v4로 나누고 각 정점별 가중치를 1로 둔다. 이때 만약 u -> v의 가중치가 3이라면 u0 -> v2 -> v1 -> v0과 같은 방식으로 u -> v의 간선을 연결할 수 있다. 이렇게 그래프를 약간 변경하여 행렬제곱을 T제곱을 하면 O((5.. 공감수 0 댓글수 0 2022. 2. 3.
  • [백준] 12850 본대 산책 2 문제 링크 http://icpc.me/12850 12850번: 본대 산책2 가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 유배당한 불쌍한 정보대생을 위한 문제다.. 분할 정복을 이용한 O(logN) 행렬 제곱을 이용하여 풀었다. 이 글을 참고하여 풀었다. 행렬 곱셈식을 곱씹어본다면 왜 이렇게 풀이할 수 있는지 알 수 있다. Counting source to destination path of k length HERE author discusses three methods to count source to destination path of k length. I am not able to get the last method which is base.. 공감수 0 댓글수 0 2022. 1. 27.
  • [백준] 13977 이항 계수와 쿼리 문제 링크 http://icpc.me/13977 13977번: 이항 계수와 쿼리 \(M\)개의 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 모듈러 역원에 대해 알아야 하는 문제다. 모듈러 역원에 대한 내용은 여기를 참고하자. n!을 전처리하여 미리 구해두고, 각 쿼리마다 n! * ((n-r)! * r!)^(mod-2)을 구하면 된다. 이때 제곱은 분할정복을 이용하여 계산한다. 코드 #include using namespace std; using ll = long long; const ll mod = 1e9 + 7; const int N = 4e6 + 6.. 공감수 0 댓글수 0 2022. 1. 25.
    문의안내
    • 티스토리
    • 로그인
    • 고객센터

    티스토리는 카카오에서 사랑을 담아 만듭니다.

    © Kakao Corp.