본문 바로가기

분류 전체보기

 (22)
[파이썬] 백준 1354번 - 무한 수열 2 풀이 https://www.acmicpc.net/problem/1354 티어: 골드 5 로직 수열 A의 모든 값을 구할 필요가 없으므로 탑다운 방식을 사용합니다. 수열 A는 dp 변수에 딕셔너리 형태로 저장하며, 초기값으로 A[0] = 1이 되도록 설정해줍니다. 수열 A의 i번째 값을 구하는 A(i)라는 함수를 만들어봅시다. 맨 처음, dp[i]값이 이미 저장되어 있는지 확인하고, 저장되어 있다면 그 값을 반환합니다. A[i]에서 i가 0 이하의 값이라면 1이므로 i의 를 max(0, i)로 설정해줍니다. A(i//p - x)와 A(i//q - y)의 값을 재귀적으로 구하고, 둘을 더한 값을 dp[i]에 저장하고 반환합니다. 구하고, 둘을 더한 값을 dp[i]에 저장하고 반환합니다.
[파이썬] 백준 1351번 - 무한 수열 풀이 https://www.acmicpc.net/problem/1351 티어: 골드 5 로직 수열 A의 모든 값을 구할 필요가 없으므로 탑다운 방식을 사용합니다. 수열 A는 dp 변수에 딕셔너리 형태로 저장하며, 초기값으로 A[0] = 1이 되도록 설정해줍니다. 수열 A의 i번째 값을 구하는 A(i)라는 함수를 만들어봅시다. 맨 처음, dp[i]값이 이미 저장되어 있는지 확인하고, 저장되어 있다면 그 값을 반환합니다. A(i//p)와 A(i//q)의 값을 재귀적으로 구하고, 둘을 더한 값을 dp[i]에 저장하고 반환합니다.
[파이썬] 백준 3584번 - 가장 가까운 공통 조상 풀이 https://www.acmicpc.net/problem/3584 티어: 골드 4 로직 먼저, 그래프의 정보를 가져오고 부모 노드가 없는 노드를 찾아 루트 노드를 구해줍니다. dfs를 이용해 루트 노드부터 공통 조상을 찾고자 하는 두 노드까지의 경로를 구해줍니다. 경로가 A = [1, 3, 5, 4], B = [1, 3, 2] 와 같이 있다고 했을 때, index i를 0부터 증가시키며 A[i]와 B[i]의 값이 같은지 확인하고, 같다면 i += 1, 다르다면 A[i-1]의 값이 LCA가 됩니다.
파이썬 빠른 입출력과 str.strip() 함수 파이썬의 기본 입출력 함수인 print()와 input() 함수는 기타 여러 기능들이 들어가 있어 매우 느리다. sys 라이브러리의 stdin.readline() 함수와 stdout.write() 함수를 이용해 더 빠른 입출력이 가능하다. 빠른 입력 sys.stdin.readline() 함수를 이용한다. import sys dat = sys.stdin.readline().rstrip() sys.stdin.readline() 함수로 읽어온 데이터에는 개행 문자 (\n)이 포함되므로, str.rstrip() 메서드를 이용해 개행 문자를 제거해야 한다. str.rstrip() 메서드 str.strip() 메서드는 문자열의 왼쪽, 오른쪽 끝에 있는 공백, 개행 문자를 제거한다. 이와 비슷하게, rstrip() ..
코드를 이미지로 변환 - Carbon https://carbon.now.sh/ C, C++, C#, Python, Java 등 여러가지 언어들로 작성된 코드를 사진으로 변환해주는 사이트입니다. Material, Night Owl 등 여러 유명한 테마들도 사용 가능합니다.
[파이썬] 백준 17633번 - 제곱수의 합 (More Huge) 풀이 https://www.acmicpc.net/problem/17633 티어: 다이아몬드 3 로직 이 문제와 동일하지만 n의 범위가 작은 문제가 있습니다. (https://www.acmicpc.net/problem/1699) 여기선 n이 100000까지라 dp로 충분했었는데, 이 문제는 n의 범위가 심상치 않음 ( 10¹⁸... ) 문제 지문에 문제를 푸는 결정적인 힌트가 나와있습니다. 라그랑주의 네 제곱수 정리인데, 이와 비슷하게 르장드르의 세 제곱수 정리, 페르마의 두 제곱수 정리 또한 존재합니다. 르장드르 세 제곱수 정리 https://en.wikipedia.org/wiki/Legendre%27s_three-square_theorem 꼴이 아닌 모든 정수 는 3개 이하의 제곱수의 합으로 표현 가능하다...
[파이썬] 백준 28017번 - 게임을 클리어하자 풀이 https://www.acmicpc.net/problem/28017 티어: 골드 5 로직 딱봐도 DP 쓸거같이 생긴 문제입니다. 1. 각 회차, 무기별 클리어 시간을 times 2차원 배열에 저장합니다. - times[회차][무기] 2. times와 동일한 크기의 dp 배열을 생성하고, dp 배열의 첫번째 인덱스는 첫 회차이므로 times[0]과 동일하게 설정해줍니다. 3. n번째 회차에서 m번째 무기를 썼을 때의 dp값은 dp[n][m] = times[n][m] + min(dp[n-1][0], min[n-1][1], ... ) 으로 표현할 수 있습니다. 이 때 이전 회차에 썼던 무기를 연달아 쓸 수 없으므로 dp[n-1]의 최솟값을 구할 때 dp[n-1][m]을 제외한 최솟값을 구해야 합니다. 4. 1..
[파이썬] 백준 7501번 - Key 풀이 https://www.acmicpc.net/problem7501 티어: 플래티넘 1 로직 입력으로 주어지는 두 정수 A, B 사이에 있는 Key값을 전부 출력해주면 되는 간단한 문제입니다. Key의 조건 1. 홀수 정수 2. (K-1)! 가 K² 으로 나누어 떨어지지 않는다. A, B 사이의 모든 정수에 대해 팩토리얼 값을 구하고, 직접 나누어 보면 당연히 시간초과가 날겁니다. Key값의 조건을 조금 더 살펴보면 모든 홀수 소수가 Key에 해당된다는건 어렵지 않게 찾을 수 있습니다. K가 소수라면 (K-1)!에 K가 포함되어 있지 않으니, 나누어 떨어지지 않기 때문입니다. 그런데, 예제를 보면 소수가 아닌 9도 Key에 포함되어있는걸 볼 수 있습니다. 처음에는 조건을 잘못 찾은 줄 알았는데, 소수가 아닌..

티스토리툴바