기록

문제 보기 [사용한 알고리즘] 크루스칼(kruskal) [문제 접근] 모든 행성은 연결되어 있기 때문에 x, y, z 좌표별로 정렬한 후 각 행성 사이의 거리를 구합니다. 거리를 모두 구한 후 가장 작은 거리부터 하나씩 연결하는 크루스칼 알고리즘을 사용하여 최소 스패닝 트리를 구하였습니다. 만약 정렬을 통해 각 행성 사이의 거리를 구하지 않고 모든 행성 사이의 거리를 구하면 시간 초과가 발생할 것이라 생각합니다. [알고리즘] 1. 행성 좌표를 입력받습니다. 2. x, y, z 좌표별로 각각 정렬한 후 각 행성 사이의 거리를 구합니다. 3. 가장 작은 거리부터 사이클을 확인한 후 연결하는 크루스칼 알고리즘을 사용하여 최소 스패닝 트리를 구합니다. [코드] import sys def find_parent(x..

문제 보기 [사용한 알고리즘] 스택(stack) [문제 접근] 후위 표기식은 중위 표기식과 달리 괄호가 없는 식이기 때문에 연산자들의 우선순위와 스택을 활용하면 구현하고자 하였습니다. [알고리즘] 1. 중위 표기식을 입력받습니다. 2. 첫 번째 문자부터 순서대로 탐색합니다. - 연산자가 아니면 postfix에 더합니다. (postfix -> 최종 식) - '(' 연산자는 s에 삽입합니다. (s -> 연산자 저장 스택) - ')' 연산자는 '(' 연산자를 만날 때까지 스택에 있는 값들을 pop 한 후 postfix에 더합니다. - '+' 혹은 '-' 연산자는 '(' 연산자를 만날 때까지 스택에 있는 값을 pop 한 후 postfix에 더합니다. - '*' 혹은 '/' 연산자는 '*' 혹은 '/' 연산자를 ..

문제 보기 [사용한 알고리즘] 구현 [문제 접근] 1. x, y 범위가 -10억 ~ 10억이고 입력 값의 개수가 최대 10만 개이기 때문에 O(n^2) 시간 복잡도로 구현하면 시간제한 2초를 초과합니다. 따라서 O(n) 시간 복잡도로 문제를 구현하고자 하였습니다. 2. x가 증가하는 순으로 좌표가 주어지기 때문에 기존에 주어진 좌표와 새로 들어온 좌표가 모두 겹치는 경우, x만 겹치는 경우, 둘 다 겹치지 않는 경우 3가지가 존재합니다. 따라서 각각의 경우에 따라서 기존의 좌표 값과 결괏값을 저장하는 변수를 관리하면 O(n) 시간 복잡도로 문제를 구현할 수 있다고 생각하였습니다. [알고리즘] 1. 첫 번째 x, y 좌표를 입력받습니다. 2. 새로 들어온 temp_x, temp_y 좌표와 기존의 좌표의 포..

문제 보기 [사용한 알고리즘] 우선순위 큐(Priority Queue) [문제 접근] 두 개의 heap을 이용하여 중간값을 관리하였습니다. 왼쪽 힙을 left(max heap), 오른쪽 힙을 right(min heap)라고 가정하면 left와 right의 보유 원소 개수(길이)가 같으면 left에 무조건 삽입합니다. 이외에는 right에 삽입합니다. 그리고 만약 left의 가장 큰 값과 right의 가장 작은 값을 비교해서 left의 가장 큰 값이 더 크면 left의 가장 큰 값과 right의 가장 작은 값을 바꿔줍니다. 그러면 right의 가장 큰 값은 중간값이기 때문에 효율적으로 중간값을 관리할 수 있습니다. [알고리즘] 1. 두 개의 heap을 선언합니다. left(max heap), right(m..

문제 보기 [사용한 알고리즘] 구현 [문제 접근] 애벌레가 자라는 날짜 한 줄마다 정보를 업데이트하면 시간 초과가 발생하였다. 따라서 애벌레가 각 날마다 자라는 정도를 모두 더한 후 한 번에 처리하였습니다. [알고리즘] 1. 각 날마다 애벌레가 자라는 정도를 모두 더해서 저장합니다. 2. 나머지 애벌레들의 자라는 정도를 계산합니다. * 제일 왼쪽 아래 칸에서 시작해서 위쪽으로 올라가서 제일 오른쪽에 도착하는 애벌레 증가 정보는 감소하지 않으므로 현재 칸에서 0행에 있는 값 - 1 만큼 현재 칸의 애벌레 크기를 증가시키면 됩니다. [코드] import sys def around_grow(array): for i in range(1, m): for j in range(1, m): array[i][j] += ..

문제 보기 [사용한 알고리즘] 정렬, 그리디 [문제 접근] 양수 가장 큰 수 두 개, 음수 절댓값 가장 큰 수 두 개씩 묶는 것이 최종 합을 최대로 나오게 할 수 있다고 생각하였다. 추가적으로 1은 묶지 않는 것이 좋고, 0의 경우 음수 1개가 남은 상황에서는 묶는 것이 좋다고 생각하였다. [알고리즘] 1. 입력받은 숫자를 오름차순 정렬한다. 2. 1보다 큰 수를 따로 저장한다. 3. 0 이하의 수를 따로 저장한다. 4. 2, 3의 과정에서 따로 구한 수를 2개씩 묶고 곱한다. 묶이지 않는 숫자는 그대로 더한다. 5. 2, 3 과정에서 묶이지 않은 숫자를 더해서 최종 합을 출력한다. [코드] from collections import deque if __name__ == "__main__": n = in..

문제 보기 [사용한 알고리즘] 구현 [문제 접근] a값과 b값은 수식을 통해서 구할 수 있습니다. 만약 a, b값이 주어진 N개의 숫자를 모두 만족시키면 다음 수를 출력하고, 만족시키지 못하면 B를 출력합니다. 모든 숫자가 동일한 경우에는 동일한 숫자를 출력하고, N이 2보다 작은데 두 숫자가 다른 경우는 A를 출력하였습니다. [알고리즘] 1. (array[2] - array[1]) // (array[1] - array[0]) 식으로 a 값을 구합니다. array[1] - array[0] * a 식으로 b값을 구합니다 2. a, b값으로 주어진 N개의 숫자를 모두 만족시키는지 확인합니다. 3. 모두 만족시키면 다음 수를 출력하고, 만족시키지 못하면 B를 출력합니다. * N이 1이면 A, N이 2이고 두 ..

문제 보기 [사용한 알고리즘] BFS(너비 우선 탐색), 구현 [문제 접근] 세 단계 과정을 통해 문제를 구현하고자 하였습니다. 첫째, 주어진 N x M 모눈종이에서 외부 공기 위치를 구합니다. 둘째, 각 치즈 상, 하, 좌, 우에 인접한 외부 공기 위치 개수를 파악합니다. 셋째, 외부 공기가 2개 이상인 치즈를 녹입니다. 위 과정을 모든 치즈가 녹을 때까지 진행합니다. [알고리즘] 1. 외부 공기 위치를 구합니다. (맨 가장자리를 출발점으로 BFS 탐색을 하여 외부 공기를 파악합니다) 2. 각 치즈의 인접한 외부 공기 위치 개수를 구합니다. 3. 외부 공기가 2개 이상인 치즈를 녹입니다. 4. 위 과정을 모든 치즈가 녹을 때까지 반복합니다. [코드] from collections import deque..

문제 보기 [사용한 알고리즘] 브루트 포스, 조합 [문제 접근] 배양액을 놓을 수 있는 공간에 초록색 배양액과 빨간색 배양액을 놓는 모든 경우에 대해서 시뮬레이션하였습니다. 배양액을 놓고 시간에 따라 퍼지는 동작을 실행해야만 꽃의 개수를 파악할 수 있기 때문에 모든 경우의 수를 확인하였습니다. [알고리즘] 1. 배양액을 놓을 수 있는 공간 중 초록색 배양액을 놓을 공간을 구합니다. 2. 배양액을 놓을 수 있는 공간 중 빨간색 배양액을 놓을 공간을 구합니다. 3. 1, 2 과정을 거친 후 시간에 따라 배양액이 퍼지는 과정을 시뮬레이션합니다. 4. 1~3 과정을 모든 경우의 수에 대해 적용해보고 피울 수 있는 꽃의 최대 개수를 출력합니다. [코드] from itertools import combination..

문제 보기 [사용한 알고리즘] BFS(너비 우선 탐색) [문제 접근] 집합 배정 정보를 관리하는 리스트를 선언한 후, 1번 정점부터 차례대로 연결된 정점들의 정보를 이용해서 집합을 배정합니다. 이후 2번 정점, 3번 정점... 마지막 정점까지 진행하면서 오류가 발생하면 NO를 출력, 끝까지 진행하면 YES를 출력하였습니다. [알고리즘] 1. 1번 정점부터 집합 배정을 시작합니다.2. 해당 정점을 처음 방문하는 경우 1을 대입합니다. 이후 해당 정점과 연결된 정점들은 2를 배정하고, 그 정점들과 연결된 정점들은 1을 배정하는 BFS 탐색을 하였습니다. (만약 해당 정점을 방문한 적이 있다면 해당 정점의 값을 통해 연결된 정점들의 값을 대입하면 됩니다. 예를 들어 해당 정점이 1의 값을 가지면 연결된 정점들..