문제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)으로 절댓값의 기준과 원 숫자를 넣어주면절댓값 기준으로 정렬하고 동일한 경우 음수를 먼저 정렬하게 되어있다.처음에는 이 성질을 몰라 튜플로 넣어도 앞에 기준으..

문제https://www.acmicpc.net/problem/2108 사용 알고리즘수학, 구 풀이고려사항1. 최빈값의 경우 여러 개 존재 시 두 번째로 작은 값 출력 후기1. 이 문제의 keypoint는 최빈값을 관리하는 것이다.2. 나머지 풀이는 간단하다.산술 평균은 모두 합친 값을 N으로 나누면 구할 수 있고,중앙값의 경우 받은 숫자 리스트를 정렬 후 N // 2 위치의 값은 구하면 된다.범위의 경우는 이미 정렬된 리스트를 사용하여 가장 큰 수에서 작은 수를 빼서 구하면 된다. 3. 최빈값의 경우 최빈값이 하나라고 주어진다면 매번 갱신하며 구하면 되지만,빈도가 동일한 값들이 존재할 수 있기 때문에 따로 관리하여야 한다.때문에 숫자와 횟수를 관리하는 dict를 만들어 관리하였고숫자를 입력받을 때 횟수를..

문제https://school.programmers.co.kr/learn/courses/30/lessons/81302 사용 알고리즘DFS 풀이고려사항1. 현재 사람의 위치에서 맨해튼 거리가 2 이내 사람 존재 여부- O(빈 책상)인 경우 계속 탐색- X(파티션)는 갈 수 없음 후기1. 이 문제의 keypoint는 재귀 관리이다.재귀의 경우 하위 호출에서 결과가 나왔더라도다시 빠져나오는 과정 중에 상위 호출에서 다시 값이 갱신 될 수 있기 때문에 처리에 주의가 필요하다.재귀, DFS에서는 매번 이 과정이 까다롭다. 2. 이번 문제 역시 맨해튼 거리가 2이기 때문에 깊이가 깊진  않지만 그래도 재귀 방식이기 때문에 2번째 깊이에서 나온 결과가 빠져나오면서 첫번째 깊이에서초기화 되는 것을 방지하기 위해 시간이..

문제https://www.acmicpc.net/problem/4195 사용 알고리즘Union-Find 풀이고려사항1. 친구 리스트에 존재 여부2. 친구 연결 후기1. 이 문제의 keypoint는 union-find를 딕셔너리를 통해 진행하는 것이다.보통은 숫자로 진행했지만, 이 문제의 경우 문자열로 받기 때문에 딕셔너리를 통해 진행했다. 2. 우선 친구 딕셔너리(parents)에 존재 여부를 확인 후 존재하지 않는다면root를 자신으로 친구 딕셔너리에 등록, size 딕셔너리에 1로 세팅한다. 3. 이후 기존 union-find 알고리즘을 진행한다.- 현재 분리 집합의 root를 find 함수를 통해 구해준 후- 서로 같은 집합이 아닐 경우 union을 통해 서로 분리 집합을 합쳐준다.4. 이때 실시간으..

문제https://www.acmicpc.net/problem/1043 사용 알고리즘Union-Find 풀이고려사항1. 해당 파티에 진실을 아는 사람이 존재하는지- 기존 진실을 아는 사람- 기존 진실을 아는 사람이 참여한 파티에 참여한 사람들 후기1. 이 문제의 keypoint는 리스트 형태를 Union-Find 진행하는 것이다.이런 형태는 기준이 있으면 좋겠다고 판단했다.때문에 기준(root)을 진실을 알고있는 가장 첫번째 사람으로 정하고 시작했다. 2. 진실을 알고 있는 사람이 0명일 경우 모든 파티에서 거짓말을 할 수 있다.하지만, 1명 이상일 경우 Union-Find를 시작한다.3. 우선 진실을 알고 있는 사람들을 하나의 집합으로 묶는다.이때 위의 기준을 정한대로 가장 첫번째 사람을 기준으로 나머지..