문제https://www.acmicpc.net/problem/20500 사용 알고리즘DP 풀이고려사항1. 1과 5로만 구성된 수인지2. 15의 배수인지 후기1. 이 문제의 경우 가능한 수의 범위가 크기 때문에 DP로 진행하였다.2. 우선, dp배열에는 digit 자리 숫자 중에서 각 자리 수가 1 또는 5로만 구성되며,    15로 나눈 나머지가 mod15인 경우의 수를 저장한다.    dp[0][0]을 1로 초기 세팅을 진행한다.3. 이후 자리수를 늘리며 이전 자리 수까지의 숫자들에서    15로 나눈 나머지 값을 기반으로 새로운 자리 수를 추가했을 때 나머지를 계산한다.    - 현재 나머지 mod15에 1 또는 5의 숫자를 추가하여 새로운 나머지를 계산한다.    - 이전 자리 수까지 mod15였던..

문제https://www.acmicpc.net/problem/1309 사용 알고리즘DP 풀이고려사항1. 현재 위치에서 상하좌우에 사자가 존재하는지2. 상하좌우에 사자가 존재하지 않는다면 사자를 놓을 것인지 후기1. 이 문제의 keypoint는 점화식을 찾는 것이다.우선 한 줄씩 늘려보면n = 1인 경우 아래와 같은 방법으로 3가지 경우의 수가 존재한다.n = 2인 경우  - 아무것도 없는 경우에 n = 1과 같이 3가지 경우 - 한 마리가 있는 경우에 사자를 놓지 않거나 반대편에 놓는 경우    즉, 2 * 2 = 4가지 경우의 수가 존재하므로 - 총 7가지 경우의 수가 존재한다. 이런 방법으로 점화식을 찾다보면두 쪽 모두 비어 있는 경우 * 3 + 사자가 한 쪽에 존재하는 경우 * 2의 규칙을 발견할 ..

문제https://www.acmicpc.net/problem/2110 사용 알고리즘이분탐색 풀이고려사항1. 가장 인접한 거리 확인하기 후기1. 이 문제의 keypoint는 이미 설치 후 거리를 확인하는 것이 아니라,거리를 먼저 설정하고 그 거리보다 멀리 몇 개의 공유기가 설치 될 수 있는지를 확인하는 것이다.먼저 공유기를 설치 후 진행하게 되면 확인 해야 할 범위가 큰 경우 시간초과가 발생한다.때문에 이분탐색을 통해 거리를 먼저 설정 후 공유기 설치 가능 갯수를 확인하며거리의 범위를 조절해 가는 것이 효율적이다.2. 이때 최대한 최적화를 시키기 위해 end의 범위도 변경해주었다.원래는 max값을 기준으로 설정하여 진행하지만,여기서의 max 값은 마지막 집이 아니라 마지막 집에서 첫 집의 거리를 뺀 총 거..

문제https://www.acmicpc.net/problem/1654 사용 알고리즘이분탐색 풀이고려사항1. N개 이상을 만들 수 있는 '최대' 길이인지 후기1. 이분탐색의 기본 유형이다.이분 탐색을 통해 랜선을 자를 길이를 계속 좁혀가며 탐색한다.- 가능한 랜선의 길이는 1 ~ ($2^{31}$ - 1)으로 단순 모든 길이를 확인하면 약 $2^{31}$ 번 연산이 필요하다.- 이진 탐색의 경우 $log_{2} {(max cable)}$으로 설정 후 K만큼 랜선 갯수 연산을 진행한다.  따라서 시간 복잡도는 $O(K log_{2} {(max cable)}) $로 효율적이다. 코드흐름1. 기준 길이를 통해 N개 이상의 랜선이 만들어 질 수 있는지 확인한다.- N개 이상이 가능하다면, 기준 길이를 높인다.- ..

문제https://www.acmicpc.net/problem/1920 사용 알고리즘이분탐색, 해시 맵https://www.acmicpc.net/blog/view/109 풀이고려사항1. target의 존재 여부 - 이분 탐색으로 정렬 리스트 탐색을 통한 찾기 - 해시 맵의 키를 통한 찾기 후기1. 이 문제의 keypoint는 조건의 수 범위가 크다는 것이다.리스트에 들어올 수 있는 정수의 범위는 -2^31보다 크거나 같고 2^31보다 작다.N과 M 역시 100,000으로 크기가 크기 때문에 하나하나 탐색하는 것은 시간 초과가 발생한다. 2. 이 문제를 두가지 방식으로 풀이했다.2-1. 이분 탐색을 통한 풀이인덱스를 기준으로 left와 right를 설정하고그 가운데 값으로 기준을 삼아 이분탐색을 진행한다.이..

문제https://www.acmicpc.net/problem/11286 사용 알고리즘우선순위 큐(heapq)https://docs.python.org/ko/3/library/heapq.html 풀이고려사항1. 현재 절댓값이 가장 작은 숫자의 음수 여부 후기1. 우선순위 큐(heapq)의 성질에 대해 자세히 알고 있었으면 더욱 쉬운 문제였다.heapq.heappush(heap, item)파이썬의 우선순위 큐에서 가중치 부분(item)을 튜플 형태로 제공한다면 튜플 내의 위치 순서대로 정렬기준을 잡는다.때문에 item 부분에 (abs(num), num)으로 절댓값의 기준과 원 숫자를 넣어주면절댓값 기준으로 정렬하고 동일한 경우 음수를 먼저 정렬하게 되어있다.처음에는 이 성질을 몰라 튜플로 넣어도 앞에 기준으..