주어지는 값이 매우 크기 때문에 if - in 구문을 쓰는 순차 탐색을 이용하면 시간 초과가 난다 따라서 탐색시간을 획기적으로 줄여주는 이분 탐색을 이용해야 한다. 이분 탐색을 활용할 줄 안다면 간단한 문제이다. 아래는 원하는 원소의 위치를 알려주는 이분 탐색의 기본적인 코드이다. (재귀를 사용하는 방법도 있지만 이 코드가 제일 간단하고 이해하기 쉬운 것 같다.) def binary_search(array, target, start, end): while start target: end = mid - 1 else: start = mid + 1 return None 따라서 이 이분 탐색 함수를 이용해 문제를 풀어주면 아래의 답이 나온다. import sys n = int(input()) card = lis..

이 문제는 크게 어려울 것은 없지만 중요한 것은 중복을 방지하는 것이다. 아래와 같은 그림에서도 만약 중복을 생각하지 않고 푼다면 index가 2인 자리의 a부터 또다시 단어가 찾아져 원하는 답보다 더 크게 나올 것이다. 따라서 중요한 포인트는 start 기준점을 잡아서 한 칸씩 오른쪽으로 움직이면서 문서에서 단어를 검색하고 그 단어가 나왔다면 start 기준점을 단어의 길이만큼 올려주는 것이다. data = input() target = input() start = 0 count = 0 while start

여기서 중요한 것은 max함수에 key값을 부여하여 그 key를 기준으로 가장 큰 것을 구하는 것이다. 예를 들어 [apple, apple, banana, cloud] 이런 리스트가 있다고 해보자 이 때 여기서 바로 max함수를 이용한다면 각 문자열의 맨 앞 부분을 비교하고, 유니코드로 변환했을 때 큰 값을 출력할 것이다. (여기서는 cloud가 출력됨을 확인) 하지만 우리가 원하는 것은 가장 빈도수가 높은 apple을 출력하는 것이다. 이 때 사용할 수 있는 것이 max안에 key값을 넣어 key값을 기준으로 뽑아내는 것이다. (min도 마찬가지) # count 함수는 빈도수를 구하는 함수 # data를 value 즉 단어와 그 단어의 빈도수(data.count)를 key로 놓고 max값을 구한것 # ..

r과 c가 주어진다면 차례로 어느 사분면에 있는지를 확인하여 문제를 풀어나간다. (여기서 주의해야 할 점은 우리가 수학에서 흔히 배우는 오른쪽 위가 1 사분면인 사분면이 아니라 문제에서 주어진 순서대로의 사분면이다.) 만약 우리가 찾는 좌표가 4사분면에 있다면 그 좌표는 이미 1, 2, 3 사분면은 거친 좌표이니 그에 맞는 숫자를 더해주고 생각하면 된다. 예를 들어 n = 3이고 r과 c가 각각 7이라고 하자 그렇다면 n = 3일 때 r과 c는 4 사분면에 있으므로 3 사분면까지의 숫자는 이미 거친 것이다. 그 말은 (4**2) * 3을 더해주고 새롭게 n = 2인 경우로 시작하면 된다는 뜻이다. n = 2인 경우에도 r과 c는 3,3 즉 4 사분면에 존재한다. 아까와 같은 방식 즉 재귀의 방법으로 (2..

만약 이를 재귀 함수로만 문제를 풀게 된다면 아래 그림과 같이 재귀 함수가 n을 인자로 호출되면 그 함수는 n-1과 n-2를 인자로 함수를 호출하고, 호출된 각 함수가 계속해서 함수를 두 개씩 호출하게 되므로 만약 n이 100이라면 이 구조의 기반한 문제풀이라면 컴퓨터가 1초에 1억 번의 계산을 수행한다 해도 수백억 년이 걸린다. 이러한 문제를 다이나믹 프로그래밍(DP)을 이용하여 간단하게 해결할 수 있다. 다이나믹 프로그래밍이란 간단히 말해서 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다. n = int(input()) d = [0] * (n+1) #단순히 재귀적으로 풀 때 과도한 시간이 걸리는 것을 방지하기 위해 dp로 풀어준다. if n == 1..