Dev_Diary

https://www.acmicpc.net/problem/22021해당 문제는 크게 두 부분으로 나누어 생각할 수 있습니다.종류에 상관없이 분무기의 위치를 알아내는 부분 / 위치를 알아낸 뒤 종류를 파악하는 부분 우선 분무기의 위치를 알아내는 부분은 생각하기 쉽습니다.어느 부분에 분무기가 존재한다고 가정하겠습니다.분무기는 십자 형태로 내용물을 살포할텐데, 살포되는 칸의 수는 15칸이 됩니다.그렇다면 자연스럽게 특정 위치에서 자신의 십자범위로 더해지거나 빼진 값의 합을 구하면 홀수가 나오게 됩니다.다른 위치에서의 분무기가 영향을 줄 수 있다고 생각할 수 있는데, 어느 위치에 다른 분무기가 존재하던 십자합에는 짝수만큼의 영향을 주므로 특정 위치의 더해지거나 빼진 값들의 십자합이 홀수라면 해당 위치는 종류에 ..

https://www.acmicpc.net/problem/15558BFS 를 사용하면 풀 수 있는 문제입니다.이동 가능한 모든 위치에 대하여 큐에 넣어주고 큐가 빌때까지 순회하면 됩니다.다만 발판이 하나씩 없어지는 점을 생각해 이동 횟수 - 1 의 인덱스를 갖는 발판을 지워주면 해결됩니다.import sysfrom collections import dequefrom copy import deepcopyinput = sys.stdin.readlinedef solution(N, K, data_list):    # 큐 / 인덱스, 이동 횟수    dq = deque([[[0, 0], 0]])    # 방문 목록    visited = deepcopy(data_list)    # 순회    while dq:  ..

https://www.acmicpc.net/problem/1516단순한 위상정렬 문제입니다. 연결 관계를 정리해준 뒤 선행 노드가 없는 노드를 시작 노드로 잡습니다.시작 노드부터 BFS 로 순회하며 걸리는 최대 시간을 기록해줍니다. 다만 큐에 다음 노드를 넣을 때는 선행 노드가 모두 방문되어야 모든 건설 시간을 고려할 수 있습니다.import sysfrom collections import dequeinput = sys.stdin.readlinedef solution(N, time_list, topol_list, graph):    # 큐    dq = deque([])    # 방문 기록    visited = [False for _ in range(N+1)]    # 필요한 시간 리스트    max_..

https://www.acmicpc.net/problem/1867이분매칭 알고리즘을 사용하는 문제입니다. 정확하게는 이 문제는 단순한 이분매칭 문제가 아닌 '최소 버텍스 커버(Minimum Vertex Cover)' 문제입니다. 최소 버텍스 커버란 무엇인지 먼저 짚고 넘어가겠습니다.어떠한 그래프가 있습니다.해당 그래프에서 몇 개의 정점을 고르겠습니다. 과연 몇 개의 정점을 골라야 그래프에 존재하는 모든 간선이 고른 정점과 연결되어 있을까요?해당 문제의 답을 찾는 것이 바로 최소 버텍스 커버 문제입니다. 그렇다면 문제는 왜 최소 버텍스 커버 문제일까요?행과 열을 나누어 각각 노드 그룹으로 쪼갠 뒤 돌이 있는 위치의 행 노드와 열 노드를 연결해 그래프를 만든다면 각 간선의 양 끝중 하나의 정점만 선택되어도..

https://www.acmicpc.net/problem/2696입력 가운데 여러번 중앙값을 구하는 문제는 일반적으로 최대힙과 최소힙을 연결해 푸는 경우가 대부분입니다. 하지만 단순히 정렬이 여러 번 이루어지기 때문에 정렬의 속도가 문제라면 이분탐색을 이용한 정렬을 통해 해결할 수 있습니다. 이런 방식은 매번 모든 데이터를 정렬하지 않기 때문에 보다 빠르게 문제를 해결할 수 있습니다. bisect.insort 함수를 사용해 새로운 데이터가 추가될 때 마다 해당 데이터가 들어갈 수 있는 위치를 이분탐색으로 찾아 삽입했습니다.import sysfrom bisect import insortinput = sys.stdin.readlinedef solution(M, data_list):    # 결과 리스트   ..

https://www.acmicpc.net/problem/2143부분합 문제입니다. 단순히 부분합 리스트를 만들고 부분합 / 부분합 쌍을 찾으면 간단히 생각해도 최악의 경우 1000개의 데이터에서 4중 반복문을 돌아야 하기 때문에 다른 방법을 찾아야 합니다. 우선 각 부분합 리스트에서 2중 반복문을 통해 모든 부 배열 합을 기록해줍니다. 데이터 기록을 할 때 딕셔너리와 리스트 중 선택할 수 있는데, 딕셔너리는 일반적으로 시간을 위해 공간을 포기한 경우로 해당 문제에서 딕셔너리에 모든 부 배열 합을 기록하면 메모리초과가 발생합니다. 그러므로 리스트에 기록하도록 합니다. 기록 중 이분 탐색을 통한 빠른 검색을 위해 정렬을 해주어야 하는데, 이분탐색을 활용한 정렬인 bisect.insort 함수를 사용할 수 ..

https://www.acmicpc.net/problem/3673우선 리스트를 부분합 리스트로 치환해줍니다. 연산 시 걸리는 시간을 줄이기 위함입니다.그 뒤에 'd 로 나누어 떨어진다' 의 부분을 쉽게 풀어 볼 생각을 해야합니다.조건에서 데이터의 크기는 최대 50000 개인데 해당 데이터를 2중 반복문으로 순회하면 시간 초과가 발생하기 때문입니다. 결론적으로, 어떠한 두 수 A, B의 차가 d 로 나누어 떨어지려면 A 를 d 로 나눈 나머지와 B 를 d 로 나눈 나머지가 같으면 됩니다. A = ad + q, B = bd + p 라고 가정하겠습니다.A - B = d(a-b) + (q - p) 입니다.A - B 가 d 로 나누어 떨어지려면 모든 인수가 d 로 나누어떨어지면 됩니다.d(a-b) 는 이미 d 의..

DFS(Depth First Search) / 깊이 우선 탐색DFS 는 후에 설명될 BFS 와 함께 대표적이고 가장 기초적인 길찾기 알고리즘입니다.깊이 우선 탐색이라는 이름에 걸맞게 우선 깊게 파고들어가고 보는 알고리즘이라고 볼 수 있는데, 일반적으로 복잡하지 않은 길 찾기 문제나 어떤 그래프가 몇 개의 그룹으로 존재하는지 찾는데 많이 사용하곤 합니다. 또 스택(Stack) 이라는 자료구조를 사용하는 것이 특징이며 후입선출이라는 스택의 특징을 잘 이용한 알고리즘입니다. 혹은 재귀 함수로 스택을 사용하지 않고 구현할 수 있지만 후입선출이라는 특징은 여전히 사용됩니다. DFS 를 사용하는 상황에서의 단계를 크게 나누자면 아래와 같습니다. 1. 데이터를 입력2. 데이터에서 그래프 혹은 트리를 생성 ( 특정 노..

Call By Value 개념 함수에서 변수를 호출할 때 값을 직접 호출하는 방식입니다. 호출되는 순간 메모리 공간에 이를 위한 임시 공간이 생성되고 변수의 값을 복사하여 바로 전달합니다. 복사된 값은 함수 안에서 로컬 변수의 특성을 가지게 되며 함수 안에서 값이 변경되어도 외부 변수의 값은 변경되지 않습니다. def add_int(a, b): a += b return a a = 10 b = 15 sum_ab = add_int(a, b) 위와 같은 방식으로 함수를 정의했다고 생각하겠습니다. a 의 값에 b 를 더한 뒤 a 를 리턴해주는 방식으로 구성되어있는데, 단순히 a 와 b 의 값을 불러와서 함수에 사용했으므로 함수 안에서 a 가 변경되어도 변경사항이 외부의 a 에 적용되지 않습니다. Call By ..