최소 편집 거리(edit distance)를 구하는 알고리즘

1. 문제 두 문자열 S1, S2가 주어질때, 다음과 같은 3가지 연산을 임의의 횟수만큼 실행할 수 있다. 1) 임의의 위치에 원하는 문자 하나를 삽입 예: banana >>> banacna 2) 임의의 위치에 있는 문자 하나를 삭제 예: banana >>> banna 3) 임의의 위치에 있는 문자 하나를 원하는 문자로 대체 예: banana >>> canana  2. 재귀를 이용한 해법 문자열의 왼쪽이나 오른쪽 끝에서부터 한문자씩 처리한다. 왼쪽부터 처리해서, 첫번째 문자가 서로 일치하는 경우, 나머지 문자에 대해 재귀적으로 처리 첫번째 문자가 서로 일치하지 않는다면, 여기에 3가지 작업으로 삽입, 제거, 대체 작업을 수행할 수 있다. 그리고 나머지 부분에 대해 재귀적으로 계산  첫번째 문자가 일치하면..

• format_list_bulleted 다이나믹 프로그래밍
• · 2024. 12. 11.
• textsms

재귀적으로 점화식 세우는 다이나믹 프로그래밍 연습1

6096번: Bulls and Cows 총 n마리의 암소와 황소를 한줄로 세울때, 두 마리의 황소 사이에 최소 k마리의 암소가 있도록 줄을 세운다고 할 때, 그러한 방법의 수를 5000011로 나눈 나머지를 구한다. 이때 각 소는 구분할 수 없어서 서로 다르게 세워진 경우만 다른 경우의 수로 센다 n  2마리 황소 사이에 k마리 암소 세우고.. 어떻게 순열 돌리고 흠... dp[i][j]를 i마리 소 세우는데 마지막에 황소가 오는 경우가 j = 0, 아닌 경우가 j = 1인데  마지막에 황소가 온다고 하더라도 그 전 정보를 알수가 없으니 이건 흠... --------------------------------------------------------------------------------------..

• format_list_bulleted 다이나믹 프로그래밍
• · 2024. 11. 23.
• textsms

ABC 357 C번 복기 - 시에르핀스키 패턴 그리는 재귀 연습

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..

• format_list_bulleted Atcoder
• · 2024. 6. 11.
• textsms

트리 필수 테크닉3 - 모든 정점들 각각 가장 먼 거리를 2번의 DFS로 구하는 방법

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

• format_list_bulleted DFS BFS 정복기
• · 2023. 12. 21.
• textsms

트리 탐색 필수 테크닉 - 자식 노드로 내려가서 얻은 value를 부모 정점으로 value 보내는 DFS 테크닉

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..

• format_list_bulleted DFS BFS 정복기
• · 2023. 12. 13.
• textsms

강한 연결 요소(Strongly connected component)를 구하는 코사라주 알고리즘(kosaraju's algorithm) 배우기

1. 강한 연결 요소(strongly connected component) 방향그래프에서 임의의 정점 v1,v2를 골랐을때, 항상 v1과 v2를 서로 오갈 수 있는 경로가 존재한다면, 그러한 방향 그래프를 강한 연결 요소(SCC)라고 부른다. 이 정의에 의하면 무방향 그래프에서는 전체 그래프가 반드시 강한 연결 요소가 되므로 의미가 없다. 즉, 방향 그래프에서만 의미있는 정의가 된다. 아무튼 예를 들어 다음 그래프는 모든 정점 쌍 (v1,v2)에 대하여 서로 오가는 경로가 존재하는 강한 연결 요소이다. 하지만 다음 그래프는.. 2번에서 5번으로는 갈 수 있어도 5번에서 2번으로 올 수는 없다. 그러므로 강한 연결 요소가 아니다. 하지만 그래프를 다음과 같이 적당히 분할하면, 분할된 그룹들 [1,2,3,4..

• format_list_bulleted 그래프 이론 정복기
• · 2023. 9. 2.
• textsms