백준 검색 결과
248 개의 검색 결과가 있습니다.
코딩/백준 (Python)

백준 4354번: 문자열 제곱 (Python)

접근 KMP 알고리즘을 이용하여 KMP table 구할 수 있다. 이 table 의 가장 마지막 숫자를 확인하고, 문자열 전체 길이를 이 수로 나누었을 때 나누어 떨어지지 않으면 반복이 0회, 즉 답이 1이고, 나누어 떨어진다면 그 몫이 답이다. 코드 import sys def kmptable(a): n = len(a) table = [0] * n j = 0 for i in range(1, n): while j > 0 and a[i] != a[j]: j = table[j - 1] if a[i] == a[j]: j += 1 table[i] = j return table while 1: p = sys.stdin.readline().rstrip() if p == '.': break table = kmptabl..

2021. 6. 19. 18:08
코딩/백준 (Python)

백준 1786번: 찾기 (Python)

접근 접근 방법은 문제에 주어져 있다. 주어진 방법대로 문제를 풀었는데 혼자서는 40% 시간초과를 넘기기가 힘들어 KMP 알고리즘에 대해 공부도 하고, 다른 분들의 코드를 참고하여 풀 수 있었다. KMP 알고리즘 개념: KMP 알고리즘 개념 커누스-모리스-프랫 알고리즘 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 컴퓨터 과학에서, 커누스-모리스-프랫 알고리즘(Knuth–Morris–Pratt algorithm, KMP)은 문자열 중에 특정 패턴을 찾아내는 문자열 검색 알고리즘의 하나이다. 문자열 ko.wikipedia.org 코드 import sys def kmptable(p): n = len(p) table = [0] * n j = 0 for i in range(1, n): w..

2021. 6. 18. 00:17
코딩/백준 (Python)

백준 2482번: 색상환 (Python)

접근 원형이 아닌 직선에서 선택하는 경우를 먼저 생각한 후, 이를 원형으로 확장하였다. dp[i][j] = i개의 색 중에 j 개의 색을 선택하는 경우의 수 라고 지정하고 dp 문제를 풀어보았다. dp[i][j] 에서 i 번째 색을 선택하면 i - 1 번째 색을 선택하지 못하므로 i - 2 개의 색 중에서 j - 1 개의 색을 선택하는 경우의 수와 같다. i 번째 색을 선택하지 않으면 i - 1 개의 색 중에서 j 개의 색을 선택하는 경우의 수와 같다. 이를 더하면 다음과 같은 점화식을 얻을 수 있다. $$ dp[i][j] = dp[i - 2][j - 1] + dp[i - 1][j] $$ 하지만 i == n 일 경우, n 번째 색을 고른다면, n - 1 번째 뿐만 아니라 1번째 색도 선택하지 못하므로 i..

2021. 6. 17. 22:53
코딩/백준 (Python)

백준 17404번: RGB 거리 2 (Python)

접근 단계별 문제 '동적계획법3' 이전 문제들에서 비트마스크를 이용한 문제들을 푸느라 이 문제도 비트마스크 문제인 줄 알고 억지로 비트마스크를 쓰려고 했던 것이 발목을 잡아 결국 문제 해결을 늦추었다. 앞으로 이런 실수는 없어야겠다. 오히려 이전에 풀었던 RGB 거리 DP 문제와 매우 유사했던 문제였다. RGB 거리 기본 문제: 2021.03.27 - [코딩/백준 (Python)] - 백준 1149번: RGB 거리 (Python) 백준 1149번: RGB 거리 (Python) 접근 [0, 0, 0] 리스트 N + 1개를 요소로 갖는 리스트(코드에서는 min_price)를 작성하여, 각 요소를 다음과 같은 의미를 갖도록 채운다. min_price[i][j] = i 번째 집에 j를 선택했을 때 채색 비용의 ..

2021. 6. 16. 23:23
코딩/백준 (Python)

백준 1086번: 박성원 (Python, PyPy3)

접근 다른 개인적인 코딩공부를 하다가 오랜만에 알고리즘 문제를 다시 풀려고 하니 역시 머리가 굳어서 잘 생각이 나지도 않고, 심지어 익숙하지 않은 비트마스크를 이용한 DP 문제여서 푸는데 시간이 더 많이 걸렸다. 비트마스크 DP 문제 : 2021.05.10 - [코딩/백준 (Python)] - 백준 1311번: 할 일 정하기 1 (Python, PyPy3) 백준 1311번: 할 일 정하기 1 (Python, PyPy3) 접근 이번 문제를 풀면서 비트마스크, 비트연산이 무엇인지 공부해보는 계기가 되었다. 비트란 컴퓨터에서 다루는 최소 단위이며, 0과 1이 하나의 비트가 될 수 있다. 0과 1이 각각 False 와 True 를 ca.ramel.be 아직 개념이 익숙치 않아 좀 더 공부한 후 다시 설명 예정 ..

2021. 6. 14. 22:39
코딩/백준 (Python)

백준 2098번: 외판원 순회 (Python)

접근 이전 문제에서 사용했던 비트마스크를 이용한 dp 문제였다. 2021.05.10 - [코딩/백준 (Python)] - 백준 1311번: 할 일 정하기 1 (Python, PyPy3) 백준 1311번: 할 일 정하기 1 (Python, PyPy3) 접근 이번 문제를 풀면서 비트마스크, 비트연산이 무엇인지 공부해보는 계기가 되었다. 비트란 컴퓨터에서 다루는 최소 단위이며, 0과 1이 하나의 비트가 될 수 있다. 0과 1이 각각 False 와 True 를 ca.ramel.be 이전 문제와 다른 점은 한 도시에서 다른 도시로 가는 길에 가중치가 있다는 것과, 경로가 없을 수 있다는 것, 그리고 처음 지점으로 돌아와야 한다는 것이다. 조금만 생각해보면 처음 지점으로 돌아와야 한다는 것은 즉 순환을 이룬다는 것..

2021. 5. 10. 02:01
반응형