나를 위한 기록

https://www.acmicpc.net/problem/2749 문제 접근 지금까지 피보나치 수열을 구하는 문제를 풀었을 때는 다음과 같은 방법으로 풀었다. 1. 재귀를 이용한 방법 def fibonacci(N): if N

문제 설명 자연수 N이 주어지면, N의 각 자릿수의 합을 구해서 return 하는 solution 함수를 만들어 주세요. 예를들어 N = 123이면 1 + 2 + 3 = 6을 return 하면 됩니다. 제한사항 N의 범위 : 100,000,000 이하의 자연수 입출력 예시 N answer 123 6 987 24 나의 풀이 123 -> "123" -> 1 + 2 + 3 파이썬은 int형 변수의 각 자리 숫자를 str 타입으로 변환하면 아주 간단하게 구할 수 있다. 자릿수를 구하고 싶다면 len(str(n))과 같이 한줄 코딩으로 가능하다. def solution(n): return sum(list(map(int, str(n))))

https://www.acmicpc.net/problem/10830 문제 접근 N x N 행렬의 곱셈을 구하는 코드는 보통 아래처럼 구현할 것이다. for i in range(N): for j in range(N): for k in range(N): matrix[i][j] += a[i][k] * b[k][j] 시간 복잡도는 O(N^3)이고 N x N 행렬의 B 제곱을 구하는 것이니 O(BN^3)이 될 것이다. 당연히 시간 초과가 날 것이다... 그렇다면 어떻게 효율적으로 행렬의 제곱을 할 수 있을까? 행렬 제곱은 N x N x N... x N처럼 순서대로 처리할 필요는 없다. N x N x N = N x N^2 N x N x N x N x N = N^2 x N^3 와 같이 전체 제곱 수를 반으로 분할하여..

문제 설명 정수 n을 입력받아 n의 약수를 모두 더한 값을 리턴하는 함수, solution을 완성해주세요. 제한사항 n은 0 이상 3000이하인 정수입니다. 입출력 예시 n return 12 28 5 6 나의 풀이 전형적인 약수를 구하는 문제이다. 약수를 구하는 문제는 항상 시간초과에 대비하여 그 수의 제곱근까지만 계산하도록 하자. def solution(n): answer = 0 for i in range(1, int(n ** 0.5) + 1): if n % i != 0: continue answer += i if i == n // i else sum([i, n // i]) return answer

문제 설명 String형 배열 seoul의 element중 "Kim"의 위치 x를 찾아, "김서방은 x에 있다"는 String을 반환하는 함수, solution을 완성하세요. seoul에 "Kim"은 오직 한 번만 나타나며 잘못된 값이 입력되는 경우는 없습니다. 제한사항 seoul은 길이 1 이상, 1000 이하인 배열입니다. seoul의 원소는 길이 1 이상, 20 이하인 문자열입니다. "Kim"은 반드시 seoul 안에 포함되어 있습니다. 입출력 예시 seoul return ["Jane", "Kim"] "김서방은 1에 있다" 나의 풀이 def solution(seoul): answer = seoul.index("Kim") return f"김서방은 {answer}에 있다"

https://www.acmicpc.net/problem/3197 문제 접근 아주 단순한 구현문제인 줄 알았다. 그래서 백조끼리 만날 수 있는지 검사하는 함수와 물의 가장자리에 붙어있는 얼음을 녹이는 함수 두 개만 짜면 되는 줄 알았다. 문제에 테스트케이스가 모두 정답이 되어 제출해봤는데 역시는 역시인가.. 처음 문제를 풀었던 방식은 이렇다. 1) 백조끼리 만날 수 있는지 BFS를 통해 검사 2) lake 배열을 매번 체크하면서 물의 가장자리에 있는 얼음을 녹임 def is_can_meet_swan(): visited = [[False] * C for _ in range(R)] start_x, start_y = swans[0] end_x, end_y = swans[1] q = deque() q.appen..

https://www.acmicpc.net/problem/1655 문제 접근 이 문제를 접근할 때 가장 단순하게 생각하면 리스트에 숫자를 넣으면서 Sorting 후 중간값을 출력하면 된다고 생각할 것이다. 하지만 제한 시간은 0.1초이고 파이썬 정렬의 시간 복잡도는 O(NlogN)이므로 시간 초과가 나올 것이다. 또 생각했던 방법은 중간값을 저장하는 변수 Center를 두고 Left, Right라는 리스트를 통해 Center보다 작으면 Left에 크면 Right에 넣는 방법을 생각했었다. 하지만 그렇게 되면 중간값을 갱신할 방법이 없었고 다른 사람의 풀이를 통해 Left와 Right를 단순 리스트가 아닌 Heap을 이용하면 중간값을 갱신할 수 있는 솔루션이 될 수 있었다. 따라서 Left를 Max Hea..

https://www.acmicpc.net/problem/12865 문제 접근 처음 이 문제를 봤을 때는 BackTracking을 이용해 해당 물건을 넣는 경우와 안 넣는 경우를 모두 구하려고 시도했다. 그렇게 되면 시간 복잡도가 O(2^N)이 되므로 최대 2^100번 연산을 해야 하므로 시간 초과가 날 수 밖에 없었다. 검색을 통해 이 문제는 다이나믹 프로그래밍을 통해 해결해야 했고 Knapsack 문제라고 불리는 아주 유명한 문제였다. 풀이 과정 N은 물품의 수이고 K는 배낭 무게이다. 물건을 하나씩 넣는 경우와 안 넣는 경우를 배열에 저장하면서 처리하면 된다. 그렇게 되면 O(NK)이 되고 최대 연산량은 10,000,000이므로 제한 시간을 통과할 수 있다. DP 점화식을 표현하면, dp[i][j]..

문제 설명 문자열 s를 숫자로 변환한 결과를 반환하는 함수, solution을 완성하세요. 제한사항 s의 길이는 1 이상 5이하입니다. s의 맨앞에는 부호(+, -)가 올 수 있습니다. s는 부호와 숫자로만 이루어져있습니다. s는 "0"으로 시작하지 않습니다. 입출력 예시 s answer "1234" 1234 "-1234" -1234 나의 풀이 def solution(s): return int(s)

문제 설명 대문자와 소문자가 섞여있는 문자열 s가 주어집니다. s에 'p'의 개수와 'y'의 개수를 비교해 같으면 True, 다르면 False를 return 하는 solution를 완성하세요. 'p', 'y' 모두 하나도 없는 경우는 항상 True를 리턴합니다. 단, 개수를 비교할 때 대문자와 소문자는 구별하지 않습니다. 예를 들어 s가 "pPoooyY"면 true를 return하고 "Pyy"라면 false를 return합니다. 제한사항 문자열 s의 길이 : 50 이하의 자연수 문자열 s는 알파벳으로만 이루어져 있습니다. 입출력 예시 s answer "pPoooyY" true "Pyy" false 나의 풀이 이 문제는 아주 간단하게 풀 수 있는 손에 꼽는 문제이다. 대소문자 구분없이 문자열 안에서 p와 ..