본문 바로가기

백준 & 알고리즘

 (17)
[파이썬] 백준 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가 됩니다.
[파이썬] 백준 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에 포함되어있는걸 볼 수 있습니다. 처음에는 조건을 잘못 찾은 줄 알았는데, 소수가 아닌..
[파이썬] 백준 16236번 - 아기 상어 풀이 https://www.acmicpc.net/problem16236 티어: 골드 3 로직먼저, bfs를 이용해 가장 가깝고 먹을 수 있는 물고기를 구하는 함수를 생각해봅시다. 함수의 로직은 대략적으로 다음과 같습니다. 1. 함수 파라미터로 아기상어의 현재 좌표와 크기를 가져옵니다. 2. deque를 만들고, (x좌표, y좌표, 0)인 튜플을 덱에 넣습니다. 여기서 0은 이동 거리입니다. 3. 정점을 방문했는지 확인하는 visited 2차원 배열을 생성합니다. 4. 물고기에 도달했는지 여부를 나타내며, 가장 가까운 물고기의 거리를 나타내는 m 변수와, 찾은 가까운 물고기들의 좌표를 담을 배열 fishes를 생성합니다. 5. 덱이 비어있지 않은 동안, 6번부터 9번을 계속 반복합니다. 6. 덱의 popleft..
[파이썬] 백준 1904번 - 01타일 풀이 https://www.acmicpc.net/problem/1904 티어: 실버 3 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 로직 문제에 맞는 점화식을 세우고, dp를 이용해 풀었습니다. 점화식 크기가 n인 이진 수열의 개수를 An이라 했을 때의 점화식입니다. 피보나치 수열과 같은 형태입니다.
[파이썬] 백준 9461번 - 파도반 수열 풀이 https://www.acmicpc.net/problem/9461 티어: 실버 3 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 로직 문제에 맞는 점화식을 세우고, dp를 이용해 풀었습니다. 점화식 P(n) 의 값을 Pn이라 했을 때의 점화식입니다. P_n-5 값을 구해야하므로 1~5까지는 직접 값을 넣어줬습니다. 질문이나 오타 등은 댓글로 남겨주시면 참고하겠습니다.

티스토리툴바