본문 바로가기

분류 전체보기91

[백준 2336] 굉장한 학생 (Platinum II) https://www.acmicpc.net/problem/2336 일단 등수대로 적혀 있던 것을 나름대로 잘 해석해서 함수 개개인에게 점수를 부여한다. 점수는 Student 구조체 하나를 만들어서, 거기다 저장할 수 있다. 이제 문제를 단순화해서 만약 시험 결과가 2개만 주어진다면 문제를 어떻게 풀지 생각해보자. 나라면 아마 다음과 같은 그림을 그려서 풀 것이다. 그림의 화살표가 나타내는 것은 알고리즘의 흐름이다. 우선 x좌표가 가장 큰 점에서부터 출발해, x좌표가 점점 작아지는 순으로 각 점들을 방문해 나간다. 이렇게 하기 위해서는 당연하지만 정렬이 필요하다. 이렇게 하면 x좌표에 대한 비교가 이미 끝났으므로 y좌표에 대한 비교만 하면 된다는 사실을 알 수 있다. 점 하나를 방문할 때마다 그 점이 이전.. 2023. 3. 31.
[백준 11717] Wall Making Game [Platinum II] https://www.acmicpc.net/problem/11717 11717번: Wall Making Game The first line of the input consists of two integers H and W (1 ≤ H, W ≤ 20), where H and W are the height and the width of the board respectively. The following H lines represent the initial board. Each of the H lines consists of W characters. The j-t www.acmicpc.net 다각형 게임과 비슷하게, 행동을 하나 하면 게임판이 여러 개로 나뉘는 문제기 때문에 스프라그-그런디 정리로 문제를 해결.. 2023. 3. 27.
[백준 25952] Rectangles (ICPC 2022 Seoul Internet; Diamond V) https://www.acmicpc.net/problem/25952 25952번: Rectangles Your program is to read from standard input. The input starts with a line containing an integer $n$ ($1 ≤ n ≤ 70\,000$), where $n$ is the number of points given in the plane. In the following $n$ lines, each line contains two integers that represent, r www.acmicpc.net n = 70 000이라는 제약조건이 상당히 생소한 문제다. 보통 n = 100 000 정도를 주면 O(n log n) ~ O(n).. 2023. 3. 2.
[백준 16998] It's a Mod, Mod, Mod, Mod World [Diamond IV] https://www.acmicpc.net/problem/16998 16998번: It’s a Mod, Mod, Mod, Mod World You are given multiple problems with three integers p, q, and n. Find \(\displaystyle\sum_{i=1}^{n}{((p \cdot i) \text{ mod } q)}\). That is, the first n multiples of p, modulo q, summed. Note that the overall sum has no modulus. www.acmicpc.net \( \sum_1^n {\left( pi \bmod q \right)} \)의 값을 구하는 문제. 50만 개 정도의 쿼리가 주어지는데.. 2023. 2. 19.
라빈-카프 알고리즘 구현 꿀팁 라빈-카프의 전체적인 동작 원리를 설명하는 글은 아니다. 문자열 s = a0a1a2...를 해싱으로 f(s)로 보내버릴 때, 다항식을 f = a0 + a1 * c + a2 * c^2 + ... 이렇게 인덱스를 맞춰서 잡기보다는 거꾸로 f = an + a_(n-1) * c + ... 이렇게 잡는 게 더 구현이 쉽다. hashval = (hashval * c + s[i]) % M을 재귀적으로 반복해서 구현할 수 있기 때문. c의 모든 거듭제곱을 전처리하지 않아도 된다. C = c ^ k만 전처리해서 어디다가 저장해 두고 있어도 된다. 첫 번째 해시값을 구했으면 한 칸씩 옮기면서 다음 해시값을 hashval = (hashval * c + s[i] - C * s[i - k]) % M으로 O(1)에 구할 수 있다.. 2023. 2. 7.
Heap과 Priority Queue의 차이, 그리고 Abstract Data Type이란 무엇인가 얼마 전까지만 해도 나도 헷갈렸던 부분이다. 일단 배경지식이 어느 정도 필요하다. C++에서 스택(std::stack)은 어떻게 구현되어 있을까? std::vector 구현체처럼 그냥 공간을 뭉탱이로 할당해 놓고 공간 부족해지면 늘려서 할당하고 그런 식으로 구현되어 있지 않을까? 대부분의 자료 구조 강의에서도 stack을 그런 식으로 구현하니 말이다. 하지만 실제로는 이렇게 생겼다. 왜 이렇게 끔찍하게 생긴 방식으로 구현되었을까? 사실 이 구현은 양쪽에서 모두 원소를 뽑아 쓸 수 있는 큐인 deque(double-ended queue)에서 한쪽을 막아놓는다는 이상한(?) 방식이다. std::queue 구현도 마찬가지다. 대체 왜 그냥 자료 구조 교과서에 있는 스택을 안 만들고 굳이 deque를 만든 다음.. 2023. 2. 7.
[백준 21117] Number of Colorful Matchings [Ruby III] https://www.acmicpc.net/problem/21117 21117번: Number of Colorful Matchings Output $n + 1$ lines containing your answers for $k = 0, 1, 2, \ldots, n$ respectively. Remember that you only need to output the answer modulo $2$. www.acmicpc.net 알아두어야 할 배경지식이 몇 개 있다. 자세한 사항은 https://en.wikipedia.org/wiki/Permanent_(mathematics) 여기를 참고했다. 1. 이분 그래프 G의 adjoint matrix는 \( \begin{bmatrix} O & A \\ A^T & O.. 2023. 2. 6.
충격!) 파이썬에서 오버로딩(overloading)이 가능하다?? 파이썬은 원래 오버로딩이 안 되는 언어라고 알려져 있었다. 왜냐하면 오버로딩을 하려면 타입이 필요한데 파이썬의 각 변수들은 타입이 지정되어 있지 않기 때문이다. 3.4 이후로 typing 모듈이 생기면서 파이썬에서도 타입 지정이라는 개념이 생기기는 했지만 여전히 optional 요소일 뿐이다. 그런데... 언제부터인지는 모르겠는데, 파이썬에도 타입에 따른 오버로딩이라는 개념이 생겼다. 예제 코드는 다음과 같이 생겼다. import functools as ft @ft.singledispatch def hello(arg) -> None: print("arg type not implemented") @hello.register def _(arg: int) -> None: print("Integer: {}".f.. 2023. 2. 4.
[백준 18292] NM과 K (2) (Platinum IV) https://www.acmicpc.net/problem/18292 18292번: NM과 K (2) 크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택할 것이고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접 www.acmicpc.net 1014번 컨닝과 비슷한 Bitmask DP 문제다. 티어도 컨닝과 똑같은 티어가 찍혔다. 3차원 dp로 해결 가능한데 for문은 4중첩으로 돌려야 한다. dp[i][j_bits][k]를 다음과 같이 정의하자 : i번째 행까지 봤고, i번째 행에서 선택을 j_bits와 같이 했으며, 0..i행 통틀어서 k개의 선택을 했을 때, 점수의 최댓값 그 다음 dp[i]에서 dp[i+1]로 가는 .. 2023. 1. 29.
[백준 1915] 가장 큰 정사각형 (Gold IV) https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net DP로 풀린다는 사실이 꽤 유명하다. dp[i][j]를 grid[0..i][0..j]에 존재하고 [i][j] 좌표를 차지하는 가장 큰 정사각형이라고 정의하자. 그러면 DP 식은 dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1이다. 이 점화식은 LCS나 knapsack 문제 풀 때처럼 테이블을 순차적으로 방문하면서 칸 채워넣기가 좋은 점화식이다. 시간복잡도는 O(mn)이다. 또한 dp 저장공간 토글링 .. 2023. 1. 24.
[백준 9658] 돌 게임 4 (Python 풀이, Silver II) https://www.acmicpc.net/problem/9658 9658번: 돌 게임 4 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 흔한 DP 문제다. n이 작을 때는 직접 손으로 처리해주고, 점화식 f(n) = not (f(n-4) and f(n-3) and f(n-1))을 넣어주면 끝. @cache 데코레이터를 써서 DP를 자동으로 할 수 있다. 그러나 hashmap을 쓰기 때문에 handwritten DP가 속도가 더 빠를 듯하다. from functools import cache @cache def game(n: int) -> bool: if n 2023. 1. 22.
[백준 9252] LCS 2 (Python 풀이, Gold IV) https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net DP 테이블을 만든 뒤, 테이블 역추적으로 LCS 문자열을 복원하는 문제다. 일단 LCS 문제를 푸는 점화식은 잘 알려져 있다. memo[i][j] = memo[i - 1][j - 1] + 1 (if a[i] == b[j]) memo[i][j] = max(memo[i - 1][j], memo[i][j - 1]) (otherwise) DP 역추적은 이.. 2023. 1. 18.
[백준 1238] 파티 (Python 풀이, Gold III) https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net dijkstra로 푸는 문제다. 일단 잘 구현된 dijkstra 함수 하나를 갖고 오자. 숙련자는 7분 만에 짤 수 있다. 어떤 그래프 G의 한 노드 v에 대해서 v로부터 모든 노드로 가는 최단경로의 거리를 각각 구해주는 것은 쉽다. 그러나 모든 노드에 대해서 모든 노드로부터 v로 가는 최단경로의 거리를 각각 구해주는 것은 약간의 생각이 더 필요하다. 간선의 방향을 .. 2023. 1. 17.
파이썬 튜플에 대한 충격적인 사실 튜플은 () 괄호 때문에 만들어지는 게 아니라 쉼표 때문에 만들어지는 거임 2023. 1. 14.
[백준 3904] The Teacher's Side of Math (Diamond IV) https://www.acmicpc.net/problem/3904 3904번: The Teacher's Side of Math One of the tasks students routinely carry out in their mathematics classes is to solve a polynomial equation. It is, given a polynomial, say \(X^2 − 4X + 1\), to find its roots \((2\pm \sqrt{3})\). If the students’ task is to find the roots of a giv www.acmicpc.net \( \sqrt[m]{a} + \sqrt[n]{b} \)를 근으로 갖는 정수 계수 mn차 다항식을 찾는 문제.. 2023. 1. 12.
[백준 16224] Path Equality (Diamond III) https://www.acmicpc.net/problem/16224 16224번: Path Equality $N$, $M$이 한 줄에 차례대로 입력된다. 입력은 $1 \le N \le 500$, $1 \le M \le 5000$를 만족한다. www.acmicpc.net 선형대수학 D3 문제치고는 굉장히 어려웠다. 구현이 쉬워서 난이도가 약간 깎인 듯싶다. 일단 결론은 \( m \leq n \)이고 \( \sqrt{mn} \)이 자연수라는 조건이 필요충분조건이다. () 방향 증명은 어렵다. n = 9이고 m = 1인 경우로 사례연구를 해 보자. tr(A) = 3이므로 9개의 노드 중 3개는 자기 자신을 향하는 loop를 갖고, 나머지 6개는 그렇지 않다. 일단 자기 자신을 향하는 loop를 갖는 3개의 노.. 2023. 1. 11.
C++ 버전이 바뀌면서 의미가 달라진 키워드들 C++에는 이렇게 많은 키워드가 있다. C++은 C에서 처음 시작했지만 시대가 발전하면서 Python, Haskell 등 프로그래밍의 패러다임을 바꾼 수많은 언어가 튀어나왔고 C++는 30년 동안 그 수많은 패러다임을 다 먹어치울 기세로 커졌기 때문이다. 그 과정에서 C++의 몇몇 키워드는 의미가 바뀌기도 했다. 가장 대표적인 키워드가 inline으로, 이 키워드는 C++에서 함수 실행 오버헤드를 줄이기 위해 함수 호출하는 부분을 그냥 함수 본문으로 대체하는 것과는 전혀 관련이 없다. 모든 C++ 개발자들은 바뀐 키워드의 내용을 숙지하여 모던한 프로그래밍 습관을 기르도록 하자. auto (C에서) storage duration을 auto로 설정함 (C++11부터) 정의된 변수의 타입을 컴파일러가 알아서 .. 2023. 1. 9.
고속 푸리에 변환, 이론부터 구현까지 1. 구현하기 전에 필요한 지식 고속 푸리에 변환(Fast Fourier Transform; FFT)은 어떤 벡터의 이산 푸리에 변환을 \( O(n \log n) \) 안에 구할 수 있게 해주는 쉬우면서도 강력한 알고리즘이다. 푸리에 변환이라고 하니 굉장히 생소해 보이고, 신호 처리나 미분방정식 푸는 데 외에는 쓸데가 없어 보이지만, 사실 이걸 갖고 상당히 많은 일을 할 수가 있다. 예를 들자면 차수가 n인 두 다항식을 \( O(n \log n) \)에 곱한다. (가장 직관적인 방법으로 계산하면 \( O(n^2) \)이 나오게 된다.) 크기가 \( 10^n \) 정도인 두 자연수를 \( O(n \log n) \)에 곱한다. (마찬가지로 직관적으로 곱하면 \( O(n^2) \)이다.) 자연수 집합의 두 부.. 2023. 1. 2.
ply 공식문서 6.8절 번역 (번역기 돌림) 불특정 다수에게 공유하려고 번역한 건 아닙니다. 프로젝트 하느라 읽어야 되는데 시간이 없어서 빨리 읽어야 하기 때문에... 만약 필요하다면 최대한 원본과 대조해서 읽으시길 바랍니다. 잘못된 번역이 있을 가능성이 높습니다. 프로덕션에서 사용할 파서를 생성하는 경우 구문 오류를 처리하는 것이 중요합니다. 일반적으로 파서가 단순히 손을 들고 문제의 첫 신호에서 멈추는 것을 원하지 않습니다.프로덕션에서 사용할 파서를 생성하는 경우 구문 오류를 처리하는 것이 중요합니다. 일반적으로 파서가 문제의 징후가 나타나면 손을 들고 멈추기를 원하지 않습니다. 대신 오류를 보고하고 가능한 경우 복구한 다음 구문 분석을 계속하여 입력의 모든 오류가 사용자에게 한 번에 보고되도록 합니다. 이것은 C, C++, Java와 같은 언.. 2022. 11. 30.
2022 ICPC 서울 리저널 후기 (짧) 나중에 각 잡고 긴 글로 쓸게요. 최종 결과 6솔, #28 J. 보자마자 실버 5따리 스택 문제인 거 알았다 I. 난 뭔 문제인지도 모르지만, 팀원 선배가 보자마자 한 3분 만에 바로 키보드 잡고 구현 시작함;; 근데 답이 제대로 안 나와서 내가 J 구현하던 중에 우연히 문제가 뭔지 알았다. input 파일 저장 안 해서 계속 같은 답이 나오는 거였음;; I, J 한 번에 솔브. K. 아마 DP인 것 같다. 마찬가지로 팀원 선배가 풀었다. F. 그냥 스위핑한 다음 누적 합을 적절한 배열에 저장해 주고 계속 움직이면서 더해 주면 된다. 이 문제는 심지어 정렬을 미리 해 주기 때문에 더 쉬웠음. // 여기까지 아마 골드인 것 같음 E. 일단 무조건 다익스트라를 써야 한다는 건 알았다. 선배랑 풀이법 의논하던.. 2022. 11. 19.
2022 아주대학교 프로그래밍 경시대회 (APC) 참가 후기 사실 그렇게 많은 시간을 들이지는 않았다(자고 일어나니까 시험은 이미 시작했는데 저녁 먹어야 했음). 그래도 많이 풀었으니 다행. 전반적으로 문제가 쉬웠는지, 문제를 풀 때 어떤 어려움도 닥치지 않았으므로(...) 그냥 풀이 방법만 나열하겠다. A. O(N) 안에 풀리긴 할 텐데 귀찮으니 정렬 돌려서 O(NlogN)으로 풀 수 있다. B. {index, depth, value} 3개의 항목을 관리해주는 struct를 만들고, 그걸 저장하는 스택을 만들자. depth가 1 늘어날 때마다 스택에 쌓아 주고, depth가 줄어들면 줄어든 만큼 pop해주면 끝. 마지막에 스택 비우는 것 잊지 말자. C. 지문에 장난질 치지 말자. 외국인 학생이 시험 보는 거였으면 어쩌려고... 물론 아니었으니 그렇게 했겠지만... 2022. 11. 13.
KMP 그림 그리면서 구현 KMP의 Motivation이 무엇인지는 다른 곳에서 쉽게 찾아볼 수 있으니 여기에 굳이 설명을 적지는 않는다. KMP의 까다로운 점은 저 Motivation을 다 알아도 수많은 edge case들 때문에 구현하기가 상당히 까다롭다는 것이다. 유한 오토마타의 개념을 알고 있으면 KMP를 상당히 직관적으로 구현할 수 있다. 일단 ABABCABAC에 대응되는 실패 함수 배열을 살펴보자. A B A B C A B A C pi 0 0 1 2 0 1 2 3 0 실패 함수 := 문자열 s[0:i] 2개를 얼마나 겹치게 놓을 수 있느냐를 숫자로 나타낸 값. 예) i = 7일 때 문자열은 ABABCABA인데 이걸 카피 떠서 하나 더 만들면 ABABCABA ABABCABA임. 그런데 앞 문자열의 뒤 3개랑 뒤 문자열의 .. 2022. 11. 5.
아름다운 함수형 프로그래밍 정보) 사실 전 함수형 프로그래밍을 이렇게 하는 게 맞는 건지는 잘 모릅니다. 그리고 사실 중간 대체과제의 일부분이라 함수형 프로그래밍 환경도 제대로 구축 못하고 시작했는데, 아마 제대로 짜면 이런 모습이 나올 겁니다. like_data = Flatlist(data) >> find_like >> to_str >> drop(4) >> int print(like_data) 그러니까 결국, 주석이 없어도 이 코드가 "아 대충 전체 데이터에서 좋아요 데이터 찾고 string으로 바꾼 다음에 앞부분 4글자 자르고 int로 바꾸는구나" 정도로 읽힐 수 있다는 게 함수형 프로그래밍의 가장 큰 장점인 것 같음. 2022. 11. 2.
[C++] TMP로 컨테이너 내부 타입 정보 얻어오기 [템플릿 메타프로그래밍] Motivation 제네릭 프로그래밍을 하고 싶다고 하자. std::vector와 같은 컨테이너 내부의 타입이 몇 바이트인지 확인할 일이 생겼다고 가정해 보자. 컨테이너로 std::vector를 사용한다는 사실을 미리 알고 있다면, 다음과 같이 짜는 것으로 충분하다. sizeof(typename std::vector::value_type) 사실은 이렇게 할 필요도 없으며, 이걸로도 충분하다. sizeof(T) 문제는 우리가 컨테이너로 std::vector가 들어온다는 사실을 모를 때 발생한다. 이렇게 가정해보자. "어떤 타입 X가 들어오는데, 우리는 X가 std::vector 꼴인지 (some custom container) 꼴인지도 모르고 사실 컨테이너인지도 모른다." 이럴 때는 다음의 해결 방법이 우.. 2022. 10. 22.
[백준 14427] 수열과 쿼리 15 (Gold II) https://www.acmicpc.net/problem/14427 14427번: 수열과 쿼리 15 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 : 수열에서 크기가 가장 작은 값의 인덱스를 www.acmicpc.net 세그먼트 트리 풀이가 정해라고 알려져 있다. 이 글에서는 Tree set 풀이를 다룬다. Tree set 풀이는 Red-black Tree로 구현한 set/map 자료구조가 O(log n) 속도로 최솟값 또는 최댓값을 찾아줄 수 있다는 성질을 이용한다. Red-black Tree는 max height O(log n)을 보장하기는 하지만 세그먼.. 2022. 10. 18.
PS, 코테 입문자들을 위한 백준 가이드 (시간복잡도, 언어별 추가 시간, solved.ac) (수정 중...) 원래 동아리 활동용으로 남들이 안 알려주는 정보만 모아놨었지만, 생각보다 유입이 많아 보다 더 일반적인 정보도 다룰 수 있게 수정 중입니다 1. 시간복잡도 거의 모든 백준 문제들은 시간복잡도를 명시하지 않습니다. 코드 내용과 실행 시간만 보고 시간복잡도를 100% 정확히 결정하는 일이 불가능하기 때문입니다. 따라서 백준 문제들은 데이터의 크기와 개수를 통해 문제가 요구하는 시간복잡도를 암시하고 있습니다. 예를 들어 지문에서 "시간 제한 : 1초" "첫째 줄에 수열의 길이 n이 주어진다. n은 5,000 이하의 자연수이다." 라고 하면, 문제가 요구하는 시간복잡도는 \( O(n^2) \)입니다. 다음은 상황에 따라 문제가 요구하는 시간복잡도를 간단히 정리한 표입니다. 시간복잡도 대표 알고.. 2022. 10. 11.
[C++] 표준 라이브러리 클래스 상속받기 (feat. Maybe 모나드 구현) 나도 몰랐던 사실인데, 표준 라이브러리 클래스를 상속받을 수 있다. 생각해 보면 당연하긴 하다. 표준 라이브러리 클래스도 결국엔 클래스일 테니까... 하지만 그렇게 하는 데는 애로사항이 조금 있을 수 있다. 내부 변수들이 private으로 선언되어 있을 수 있기 때문이다. 이 변수들은 상속받아도 접근할 수 없다. (사실 private이 아니어도 접근하기 어려울 것이다. 어차피 이름을 모르거든...) 하지만 방법은 있다. 이 글에서 C++17 표준 라이브러리 중 하나인 std::optional 클래스를 상속받이 maybe 모나드로 만들어 보자. 일단 std::optional는 값이 있을 수도 없고 없을 수도 있는 객체를 나타내는 클래스이다. 예를 들어 std::string을 int로 바꿔주는 to_inte.. 2022. 9. 27.
[C++] class Matrix 구현 내가 class Matrix를 아직도 이 블로그에 안 올려놨다니,,, 덧셈, 뺄셈, 곱셈, 스칼라배, 기본행/기본열 연산 등의 기능을 지원한다. 근데 뭐 이거 구현한다고 250줄을 잡아먹냐. template class Matrix { private: T** p; unsigned int n; // size public: explicit Matrix(int _n) : n(_n) { this->init(); } ~Matrix() { if (p) { for (int i = 0; i init(); for (int i = 0; i < n; ++i) { fo.. 2022. 9. 24.
[C++] 프록시(Proxy) 디자인 패턴 (feat. bitset) 프록시(Proxy)는 대리자라는 뜻을 갖고 있다. 즉 어떤 객체가 하는 일을 그대로 흉내내는 객체이다. C++에서 프록시의 가장 유명한 예시는 바로 스마트 포인터(Smart Pointer)일 것이다. 스마트 포인터는 자신이 소멸될 때 delete 연산자를 알아서 호출해서 메모리 누수를 막는 똑똑한 객체인데, 당연하지만 스마트 포인터 그 자체는 포인터가 아니라 객체이다. 그럼에도 스마트 포인터는 일단 포인터가 할 수 있는 모든 일을 할 수 있도록 설계되어 있다(unique_ptr 같은 경우 복사 연산과 복사 대입 연산이 안 되기는 하지만). 특히 * 연산자와 -> 연산자를 제공하므로 사용자는 스마트 포인터를 그냥 포인터 쓰듯이 쾌적하게 사용할 수 있을 것이다. 이 글에서는 비트셋(bitset)에서 프록시 .. 2022. 9. 18.
[대학생 수학경시대회] 2011년 제2분야 2번 2. 임의의 \( n \times n \) 행렬 \( A \)에 대하여, $$ \det \begin{pmatrix} A & A^2 \\ A^3 & A^4 \end{pmatrix} = 0 $$ 임을 보여라. (단, \( A \)의 모든 성분은 실수이다.) Sol) 주어진 행렬을 다음과 같이 다시 쓸 수 있다. $$ \begin{pmatrix} A & A^2 \\ A^3 & A^4 \end{pmatrix} = \begin{pmatrix} I \\ A^2 \end{pmatrix} \begin{pmatrix} A & A^2 \end{pmatrix} $$ 따라서 주어진 행렬은 \( 2n \times 2n \) 행렬이지만 그 rank가 \( n \) 이하이므로 행렬식이 \( 0 \)이다. 2022. 9. 14.

티스토리툴바