C - Sierpinski carpet (atcoder.jp) C - Sierpinski carpetAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp K = 0이면 1*1 검정색 사각형 K = 1이면 3*3 사각형에 가운데 1*1이 흰색인 사각형 K = N이면 .. $3^{K} * 3^{K}$인 사각형에서, $3^{K-1} * 3^{K-1}$로 9개 사각형을 나누고 K = N-1인 부분이 주위 8개 칸에 들어가고, 중간은 흰색 사각형으로만 K = 0이면 검정색 사각형 하나 def f(k): if k == 0..
1. 문제 11429번: Tree (acmicpc.net) 11429번: Tree The input file contains the description of the tree. The first line of the input file contains one integer N, 2
1. 문제 30414번: 투스타 춘배 (acmicpc.net) 30414번: 투스타 춘배 춘배 나라에는 $1$부터 $N$까지의 번호가 붙은 $N$개의 산, 그리고 두 산 사이를 이동할 수 있는 $N-1$개의 길이 있다. 게다가 임의의 두 산 사이를 항상 길을 통해 이동할 수 있다고 한다. 즉, 산을 www.acmicpc.net 2. 풀이 현재 산의 높이가 원하는 높이보다 작다면 흙을 차이만큼 구매하는게 좋고, 높다면 깎아내리는게 좋을 것이다. 근데 문제는 병사 1명이 u번에서 v번으로 내려갈때, 깎아내린 산 크기 X만큼을 가져가는데 u번에서 v번 경로가 아닌 다른 경로로 X만큼을 가져갈 수 없다는게 문제 트리 탐색은 DFS로 가능한데 v로 들어가기 전에 visited[v] = 1로 체크하고 나와서 vis..
1. 강한 연결 요소(strongly connected component) 방향그래프에서 임의의 정점 v1,v2를 골랐을때, 항상 v1과 v2를 서로 오갈 수 있는 경로가 존재한다면, 그러한 방향 그래프를 강한 연결 요소(SCC)라고 부른다. 이 정의에 의하면 무방향 그래프에서는 전체 그래프가 반드시 강한 연결 요소가 되므로 의미가 없다. 즉, 방향 그래프에서만 의미있는 정의가 된다. 아무튼 예를 들어 다음 그래프는 모든 정점 쌍 (v1,v2)에 대하여 서로 오가는 경로가 존재하는 강한 연결 요소이다. 하지만 다음 그래프는.. 2번에서 5번으로는 갈 수 있어도 5번에서 2번으로 올 수는 없다. 그러므로 강한 연결 요소가 아니다. 하지만 그래프를 다음과 같이 적당히 분할하면, 분할된 그룹들 [1,2,3,4..
1. counting inversion problem inversion이란 배열 A에 대하여 자기보다 뒤(index가 큰 쪽)에 있으면서 자기보다 값이 작은 A[j]를 뜻한다. 수학적으로 i A[j]를 만족하는 (i,j)의 개수를 세는 문제이다. 단순하게 세면 $O(N^{2})$이지만 실제 위치보다 전후 관계만 본다는 점을 관찰한다면, 2,X,X,X,X,X,X,X,X,1이더라도 2와 1은 inversion이고, 2,1,X,X,X,X,X,X,X,X,...더라도 2와 1은 inversion이다. 또한 다음 그림과 같이 화살표들의 교점의 개수와 동일하다. 두 수가 서로 inversion이면 교점이 하나 생기기 때문이다. 2. 해법 위 그림에서 볼 수 있는대로, 병합정렬을 하면 자연스럽게..
1. 분할 정복(divide and conquer) 분할 = 큰 문제를 여러 개의 작은 문제로 쪼갠 다음 정복 = 작은 문제들의 답을 이용해 큰 문제의 답을 구하는 방법 충분히 크기가 큰 문제를 쉽게 해결할 수 있는 부분 문제로 분할해 나가고, 분할된 하위 문제를 해결하여 이 결과를 조합하여 윗단계 문제에 대한 답으로 낸다 2. 방법 정답을 쉽게 도출할 수 있을 때까지 재귀적으로 분할된 단위로 자신을 호출하면서 범위를 조금씩 줄여나감(분할단계) 답을 쉽게 도출하는 단계까지 도달한다면 재귀함수는 정답을 return하고 이렇게 return하면서 이를 이용해 재귀 stack에 쌓인 윗단계 재귀함수의 값을 return해나가는 것이 정복단계 def f(x): if (f(x)가 간단함): return f(x) el..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
